• Pattern-avoiding permutations.
  [Vince Vatter's notes given in class]
  • Motivation. Sorting using stacks and queues.
  • Closed classes of permutations. Separable permutations.
  • Asymptotics and growth rates.
  • The Stanley-Wilf Conjecture and the Marcus-Tardos proof.
  [Bona, Combinatorics of permutations, Chapman Hall-CRC, 2004]
  • Exact enumeration of patterns of length 4.
  • Packing densities.
  [Elizalde, Deutsch, A simple and unusual bijection for Dyck paths and its consequences, Ann. Comb. 7 (2003), 281–297]
  [Elizalde, Pak, Bijections for refined restricted permutations, J. Combin. Theory Ser. A 105 (2004), 207-219]
  • Statistics on pattern-avoiding permutations.
  
  
• Generating trees, functional equations, and the kernel method.
  [West, Generating trees and the Catalan and Schröder numbers, Discrete Math. 146 (1995), 247–262]
  [Bousquet-Melou, Four Classes of Pattern-Avoiding Permutations Under One Roof: Generating Trees with Two Labels, Electron. J. Combin. 9 (2002-3), #19]
  [Flajolet, Sedgewick, Analytic Combinatorics, Section VII.8.1]
  [Bousquet-Melou, Mishna, Walks with small steps in the quarter plane, Contemp. Math. 520 (2010), 1-40]
  • Constructing generating trees with one label.
  • From generating trees to functional equations.
  • The kernel method for generating trees with one label, and for one-dimensional walks.
  • Generating trees with two labels.
  • Examples of the kernel method for generating trees with two labels: Baxter permutations, 1234-avoiding permutations.
  • Walks with small steps in the quarter plane.
  • Generalized paterns.
    [Babson, Steingrimsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sem. Loth. Comb. 44 (2000), B44b]
    [Steingrimsson, Generalized permutation patterns - a short survey, in Permutation Patterns, LMS Lecture Notes Cambridge Univ. Press (2010), 137–152]
    [Claesson, Generalized pattern avoidance, Europ. J. Combinatorics 22 (2001), 961-971]
  
  
• Student presentations.

Last updated June 17, 2015 12:56:59 EDT