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

What is Combinatorics What does it mean to count? Aspects of counting derangements (fixed point free permutations) P.R.de Montmort sequence A000166 in OEIS recurrence - summation - asymptotics - generating function

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

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

Identities Number system (Zeckendorf) Binet's formula via generating function via linear algebra Continued fractions and continuants

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

Euler's Pentagonal Number Theorem Formal power series Basic operations Bernoulli numbers and sums

Composition of FPS Catalan numbers and their generating function Solving linear recurrences The general approach

Spanning trees ofGExponential generation function for Fibonacci numbers q-Enumeration Permutations and inversions Mac Mahon's maj-index and the equidistribution theorem_{n}

01-words and inversions A q-binomial theorem Subspaces of q-vectorspaces A second q-binomial theorem

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

Shadows Sperner's Theorem again Kruskal-Katona Theorem

Symmetric chains Symmetric chain decompositions for multisets Symmetric chain decomp. and pairing brackets An application to Dedekind's problem

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

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

Polya Theorie: Counting with symmetries Necklaces and colored cubes - two introductory examples Permutation groups and the cycle index The Lemma of Cauchy-Frobenius-Burnside

Polya's first theorem: counting orbits ofRWeights on^{D}Rand the induced weight onRPolya's fundamental theorem:^{D}

Linear extensions generic algorithm dimension of posets Boolean lattices and standard examples bounds for dimension characterizations of 2-dimensional posets

Algorithms for chain- and antichain partitions the 2-dimensional case Young-Tableaux and the Robinson-Shensted correspondence bumping Viennot's proof via skeletons Connections to the Greene-Kleitman theory

Design TheorySdesigns Some examples and constructions Arithmetic conditions Kirkman's problem_{λ}(t,k,v)

Resolvable designs Solutions to Kirkman's problem Projective planes as designs A construction of the planeS(2,5,21)fromKFisher's inequality_{6}

Möbius inversion Incidence algebra of a poset Zeta function and Möbius function Möbius function of chains and products Applications

Involutions Vandermonde determinant and tournaments Lemma of Lindström, Gessel-Viennot

Catalan numbers Ten Catalan families some bijections Determining the numbers path reflection

cycle lemma Narayana numbers via LGV Lemma Further directions two lattices on Catalan families rotations and flips the associahedron

Back to the course page.