Table of Contents


Sommer Term 2011
Stefan Felsner

Vorlesungsdetails: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24

1. lecture, 11.4.2011

   What is Combinatorics
     What does it mean to count?
       Aspects of counting derangements (fixed point free permutations) Montmort
       sequence A000166 in OEIS
       recurrence - summation - asymptotics - generating function
2. lecture, 11.4.2011
     Orthogonal Latin Squares 
       (Euler's 36 officers problem)
       Orthogonal Latin squares from groups
       MOLS (mutually orthogonal Latin squares)
       There are at most N-1 MOLS of order N
       MOLS and projective planes
3. lecture, 18.4.2011
   Basic Counting
      Basic rules for counting
      Binomial coefficients
        Models and identities
        Extending binomial coefficients 
        (positive integer -> integer -> complex -> polynomial)
      The binomial theorem
   Fibonacci numbers
      Basic models
4. lecture, 18.4.2011
      Number system (Zeckendorf)
      Binet's formula via generating function
                      via linear algebra
      Continued fractions and continuants
5. lecture, 2.5.2011
      The twelvefold way
      Partitions of a set
        Stirling numbers of 2nd kind
      Partitions on an integer
        Generating function of partitions
        The Hardy-Ramanujan-Rademacher formula
        Distinct and odd are equinumerous
6. lecture, 2.5.2011
        Euler's Pentagonal Number Theorem 
      Formal power series
        Basic operations
        Bernoulli numbers and sums
7. lecture, 9.5.2011
        Composition of FPS
        Catalan numbers and their generating function 
      Solving linear recurrences
        The general approach
8. lecture, 9.5.2011
        Spanning trees of Gn
        Exponential generation function for Fibonacci numbers
        Permutations and inversions
        Mac Mahon's maj-index and the equidistribution theorem
9. lecture, 16.5.2011
        01-words and inversions
        A q-binomial theorem
        Subspaces of q-vectorspaces
        A second q-binomial theorem       
10. lecture, 16.5.2011
   Finite sets and posets
        Intersecting families of subsets
        Posets and lattices
        Substructures in posets and lattices
        Sperner's Theorem - LYM inequality
        Erdös-Ko-Rado Theorem - cyclic permutations
        Small maximal k-intersecting families
11. lecture, 23.5.2011
          Sperner's Theorem again
          Kruskal-Katona Theorem
12. lecture, 23.5.2011
        Symmetric chains
          Symmetric chain decompositions for multisets
          Symmetric chain decomp. and pairing brackets
          An application to Dedekind's problem
13. lecture, 30.5.2011
      Duality theorems
        Dilworth's Theorem       
        König-Egervary matching theorem
        The Marriage Theorem (Hall condition)
        A quantified Marriage Theorem
        On the number of Latin squares
14. lecture, 30.5.2011
      The matching polytope of a bipartite graph 
        LP relaxation for max matching
        Polyhedra, polytopes and their vertices
        The TDI property of the incidence matrix
        LP-duality and the König-Egervary theorem    
15. lecture, 6.6.2011
    Polya Theorie: Counting with symmetries
      Necklaces and colored cubes - two introductory examples
      Permutation groups and the cycle index
      The Lemma of Cauchy-Frobenius-Burnside
16. lecture, 6.6.2011
      Polya's first theorem: counting orbits of RD
      Weights on R and the induced weight on RD
      Polya's fundamental theorem:  
17. lecture, 20.6.2011
      Linear extensions
        generic algorithm
        dimension of posets
          Boolean lattices and standard examples
        bounds for dimension 
        characterizations of 2-dimensional posets 
18. lecture, 20.6.2011
     Algorithms for chain- and antichain partitions
       the 2-dimensional case
       Young-Tableaux and the Robinson-Shensted correspondence
          Viennot's proof via skeletons 
       Connections to the Greene-Kleitman theory
19. lecture, 27.6.2011
   Design Theory
     Sλ(t,k,v) designs
     Some examples and constructions 
     Arithmetic conditions
     Kirkman's problem
20. lecture, 27.6.2011
     Resolvable designs
     Solutions to Kirkman's problem
     Projective planes as designs
     A construction of the plane S(2,5,21) from K6
     Fisher's inequality
21. lecture, 4.7.2011
       Möbius inversion
         Incidence algebra of a poset
         Zeta function and  Möbius function
         Möbius function of chains and products
22. lecture, 4.7.2011
         Vandermonde determinant and tournaments
         Lemma of Lindström, Gessel-Viennot
23. lecture, 11.7.2011
       Catalan numbers
         Ten Catalan families
            some bijections
         Determining the numbers
            path reflection
24. lecture, 11.7.2011
            cycle lemma
            Narayana numbers via LGV Lemma 
         Further directions
            two lattices on Catalan families
            rotations and flips
            the associahedron

Back to the course page.