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

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

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

Basic Counting Basic rules for counting Binomial coefficients Models and identities Extending binomial coefficients Extending binomial identities to polynomial identities The binomial theorem

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

The twelvefold way Partitions of a set Stirling numbers of 2nd kind Stirling inversion Partitions on an integer

Generating function of partitions The Hardy-Ramanujan-Rademacher formula Distinct and odd are equinumerous Euler's Pentagonal Number Theorem

Fibonacci numbers Basic models Identities Number system (Zeckendorf) Binet's formula via generating function

Solving linear recurrences The general approach (partial fraction decomposition) The matrix approach (companion matrix) Exponential generation function for Fibonacci numbers

Formal power series Basic operations Bernoulli numbers and sums Composition of FPS

The symbolic method Catalan numbers and their generating function q-Enumeration Permutations and inversions Mac Mahon's maj-index and the equidistribution theorem

Eulerian numbers Equidistribution of des and exc Worpitzky's identity q-binomial coefficients

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

Posets and lattices Sperner's Theorem - LYM inequality Erdös-Ko-Rado Theorem - cyclic permutations

Small maximal k-intersecting families Shadows and a second proof of Sperner's The Kruskal-Katona Theorem

The Lovasz version of Kruskal-Katona Erdös-Ko-Rado from LKK Symmetric chain decompositins

Symmetric chain decompositins 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 Equivalence with Dilworth's Hall's Theorem (Marriage Theorem) Applications

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

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

Applications of the lemma, e.g. Stirling numbers of 2nd kind Polya's first theorem: counting orbits ofRWeights on^{D}Rand the induced weight onRPolya's second theorem: counting orbits with weights^{D}

Design TheorySdesigns Some examples and constructions Arithmetic conditions_{λ}(t,k,v)

Fisher's inequality Kirkman's problem Resolvable designs Solutions to Kirkman's problem 3-Designs fromPGL(2,q)

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

Lemma of Lindström, Gessel-Viennot Applications Evaluating determinants The Binet-Cauchy formula Counting disjoint path systems

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

Using determinants to evaluate permanents Determinants to count matchings of planar bipartite graphs Matchings and some tiling problems

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

symmetric chain decompositions Narayana numbers via LGV Lemma Orders on Catalan families Associahedron and flips

Back to the course page.