Table of Contents

Combinatorics

Sommer Term 2015
Stefan Felsner

Content of individual lectures: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 25 , 26

1. lecture, 13.4.2015 

   What is Combinatorics - introductory examples
     Derangements
       Aspects of counting derangements (fixed point free permutations) P.R.de Montmort
       sequence A000166 in OEIS
       recurrence - summation - asymptotics - generating function
2. lecture, 13.4.2015 
     Orthogonal Latin Squares 
       (Euler's 36 officers problem)
       Orthogonal Latin squares of odd order from groups
       MOLS (mutually orthogonal Latin squares)
       There are at most n-1 MOLS of order n
       MOLS and projective planes
3. lecture, 20.4.2015 
   Basic Counting
      Basic rules for counting
      Binomial coefficients
        Models and identities
        Extending binomial coefficients 
        Extending binomial identities to polynomial identities
      The binomial theorem
4. lecture, 20.4.2015 
   Fibonacci numbers
      Basic models
      Identities
      Number system (Zeckendorf)
      Binet's formula via generating function
5. lecture, 27.4.2015 
  The twelvefold way
      Partitions of a set
        Stirling numbers of 2nd kind
        Stirling inversion 
      Partitions on an integer
6. lecture, 27.4.2015 
        Generating function of partitions
        The Hardy-Ramanujan-Rademacher formula
        Distinct and odd are equinumerous
        Euler's Pentagonal Number Theorem
7. lecture, 4.5.2015 
  Solving linear recurrences
      The general approach (partial fraction decomposition)
      The matrix approach (companion matrix)
    Exponential generation function for Fibonacci numbers
8. lecture, 4.5.2015 
  Formal power series
     Basic operations
     Bernoulli numbers and sums
     Composition of FPS
     Catalan numbers and their generating function
9. lecture, 11.5.2015 
  q-Enumeration
     Permutations and inversions
       Mac Mahon's maj-index and the equidistribution theorem
       Eulerian numbers 
       Equidistribution of des and exc
10. lecture, 11.5.2015 
       Worpitzky's identity
       01-words and inversions
         A first q-binomial theorem
       Subspaces of q-vectorspaces
         A second q-binomial theorem
11. lecture, 18.5.2015 
   Finite sets and posets
      Intersecting families of subsets
      Posets and lattices
      Sperner's Theorem - LYM inequality
12. lecture, 18.5.2015 
     Erdös-Ko-Rado Theorem - cyclic permutations
     Small maximal k-intersecting families
     Shadows and a second proof of Sperner's
     The Kruskal-Katona Theorem
13. lecture, 1.6.2015 
       The Lovasz version of Kruskal-Katona
       Erdös-Ko-Rado from LKK
   Symmetric chain decompositins
14. lecture, 1.6.2015 
 
      Symmetric chain decompositions for multisets
      Symmetric chain decomp. and pairing brackets
      An application to Dedekind's problem
    Duality theorems
      Dilworth's Theorem
15. lecture, 8.6.2015 
      König-Egervary matching theorem
        Equivalence with Dilworth's
      Hall's Theorem (Marriage Theorem)
      Applications 
      A quantified Hall's Theorem
16. lecture, 8.6.2015 
    Linear extensions
       generic algorithm
       dimension of posets
         Boolean lattices and standard examples
         bounds for dimension 
         characterizations of 2-dimensional posets
17. lecture, 15.6.2015 
   Polya Theorie: Counting with symmetries
      Necklaces and colored cubes - two introductory examples
      Permutation groups and the cycle index
      The Lemma of Cauchy-Frobenius-Burnside
18. lecture, 15.6.2015 
        Applications of the lemma, e.g. Stirling numbers of 2nd kind
      Polya's first theorem: counting orbits of RD
      Weights on R and the induced weight on RD
      Polya's second theorem: counting orbits with weights
19. lecture, 22.6.2015 
   Design Theory
     Sλ(t,k,v) designs
     Some examples and constructions 
     Arithmetic conditions
20. lecture, 22.6.2015 
     Fisher's inequality
     Kirkman's problem
     Resolvable designs
     Solutions to Kirkman's problem
     3-Designs from PGL(2,q)
21. lecture, 29.6.2015 
   Möbius inversion
      Incidence algebra of a poset
      Zeta function and  Möbius function
      Möbius function of chains and products
      Applications
22. lecture, 29.6.2015 
   Involutions
      Vandermonde determinant and tournaments
      Lemma of Lindström, Gessel-Viennot
23. lecture, 6.7.2015 
     Derangements and a determinant
     Derangements and a permanent
  The permanent
     Basic facts
24. lecture, 6.7.2015 
     The number of perfect matchings of 3-regular bip. graphs 
     Using determinants to evaluate permanents
     Determinants to count matchings of planar bipartite graphs
     Matchings and some tiling problems
25. lecture, 13.7.2015 
   Catalan numbers
      Ten Catalan families
        some bijections
        Determining the numbers
           path reflection
           cycle lemma
26. lecture, 13.7.2015 
           symmetric chain decompositions
        Narayana numbers via LGV Lemma 
      Orders on Catalan families
        Associahedron and flips

Back to the course page.