Table of Contents


Sommer Term 2017
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 , 27 , 28

1. lecture, 18.4.2017

   What is Combinatorics - introductory examples
       Aspects of counting derangements (fixed point free permutations) Montmort
       sequence A000166 in OEIS
       recurrence - summation - asymptotics - generating function
2. lecture, 18.4.2017
     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, 26.4.2017
   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, 26.4.2017
   Combinatorics of Permutations
      The type of a permutation
        Enumeration of permutations of given type
      Permutations with k cycles
        Stirling numbers of first kind
        Recursion and raising factorials
      Expected number of cycles 
5. lecture, 2.5.2017
  The twelvefold way
      Partitions of a set
        Stirling numbers of 2nd kind
        Stirling inversion 
      Partitions on an integer
6. lecture, 2.5.2017
        Generating function of partitions
        The Hardy-Ramanujan-Rademacher formula
        Distinct and odd are equinumerous
        Euler's Pentagonal Number Theorem 
7. lecture, 9.5.2017
   Fibonacci numbers
      Basic models
      Number system (Zeckendorf)
      Binet's formula via generating function
8. lecture, 9.5.2017
  Solving linear recurrences
      The general approach (partial fraction decomposition)
      The matrix approach (companion matrix)
    Exponential generation function for Fibonacci numbers
9. lecture, 16.5.2017
  Formal power series
     Basic operations
     Bernoulli numbers and sums
     Composition of FPS
10. lecture, 16.5.2017
     The symbolic method
       Catalan numbers and their generating function 
     Permutations and inversions
     Mac Mahon's maj-index and the equidistribution theorem
11. lecture, 23.5.2017
       Eulerian numbers 
       Equidistribution of des and exc
       Worpitzky's identity
       q-binomial coefficients
12. lecture, 23.5.2017
         01-words and inversions
         A first q-binomial theorem
       Subspaces of q-vectorspaces
         A second q-binomial theorem   
   Finite sets and posets
      Intersecting families of subsets
13. lecture, 30.5.2017
     Posets and lattices
     Sperner's Theorem - LYM inequality
     Erdös-Ko-Rado Theorem - cyclic permutations
14. lecture, 30.5.2017
    Small maximal k-intersecting families
     Shadows and a second proof of Sperner's
    The Kruskal-Katona Theorem

15. lecture, 6.6.2017
    The Lovasz version of Kruskal-Katona
       Erdös-Ko-Rado from LKK
   Symmetric chain decompositins
16. lecture, 6.6.2017
   Symmetric chain decompositins
      Symmetric chain decompositions for multisets
      Symmetric chain decomp. and pairing brackets
      An application to Dedekind's problem
17. lecture, 13.6.2017
    Duality theorems
      Dilworth's Theorem       
      König-Egervary matching theorem
        Equivalence with Dilworth's
      Hall's Theorem (Marriage Theorem)
18. lecture, 13.6.2017
    Linear extensions
       generic algorithm
       dimension of posets
         Boolean lattices and standard examples
         bounds for dimension 
         characterizations of 2-dimensional posets 
19. lecture, 20.6.2017
   Polya Theorie: Counting with symmetries
      Necklaces and colored cubes - two introductory examples
      Permutation groups and the cycle index
      The Lemma of Cauchy-Frobenius-Burnside
20. lecture, 20.6.2017
      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 
21. lecture, 27.6.2017
   Design Theory
     Sλ(t,k,v) designs
     Some examples and constructions 
     Arithmetic conditions
22. lecture, 27.6.2017
     Fisher's inequality
     Kirkman's problem
     Resolvable designs
     Solutions to Kirkman's problem
     3-Designs from PGL(2,q)
23. lecture, 4.7.2017
   Möbius inversion
      Incidence algebra of a poset
      Zeta function and  Möbius function
      Möbius function of chains and products
24. lecture, 4.7.2017
  Lemma of Lindström, Gessel-Viennot
       Evaluating determinants 
       The Binet-Cauchy formula
       Counting disjoint path systems
25. lecture, 11.7.2017
  Permanents, Determinants and Matchings
      Derangements and a determinant
      Derangements and a permanent
    The permanent
      Basic facts
      The number of perfect matchings of 3-regular bip. graphs 
26. lecture, 11.7.2017
      Using determinants to evaluate permanents
      Determinants to count matchings of planar bipartite graphs
      Matchings and some tiling problems
27. lecture, 18.7.2017
  Catalan numbers
      Ten Catalan families
        some bijections
        Determining the numbers
           cycle lemma
           path reflection
28. lecture, 18.7.2017
           symmetric chain decompositions
        Narayana numbers via LGV Lemma 
      Orders on Catalan families
        Associahedron and flips

Back to the course page.