VO Kombinatorik WS2010/11 LVNr. 250011
Contact me if you want to take an exam.
Exam 1, 31.01.2011
Exam 2, 11.02.2011
Exam 3, 28.02.2011
Exam 4, 02.05.2011
Upon request you get an English translation of the problems in the exam.
The exam will be written and oral.
Answers may be given in German or English. The exam will be written and oral.
Important: It is not sufficient to give correct answers in the written part of the exam. Students will be asked
to explain their solutions in the oral part.
The list of question should help the students when preparing
for the exam. Subject of the exam is the whole material which was presented in the leture.
Here is Chapter 3 of the lecture notes (version 17.02.2011).
winter term 2010/11, lecture on combinatorics, 4 hours a week (6 ECTS).
The lecture will be given in
English. There is an exercise section (Übung), 2 hours a week (4 ECTS)
Lecture Monday 12:15-13:45, Thursday 10:00-11:45 (with break), C2.09 UZA 4.
Exercise class by Ilse Fischer, Monday 15:15-16:45, C2.07 UZA 4. The problem sheets can be found
This is a Mathematica package written by Thomas Blank with a corresponding sample file with which one can compute cycle indicator series for finite permutation groups.
The input is a set of permutations which generate the group. The present version of Mathematica 7 at our
University does not include such tools, but the new Matheatica 8 is said to have related tools.
Here you find the problem of the hundred prisoners (in German).
Prerequesites: There are no other specific courses required for this lecture as prerequestite, but I am assuming that you
are familiar with some elementary notions such as cyclic decomposition of permutations, prime decomposition of integers,
the binomial theorem, the solution of linear recursions or group homomorphisms. These are things which you
can find in
books or on Wikipedia. Please contact me if you have further questions.
I have given a silimar course in 2008, see
This time I will use the theory of "combinatorial species".
You do not have to buy any books. But if you are looking for additional literature I recommend:
F. Bergeron, G. Labelle, P. Leroux, "Combinatorial Species and Tree-like Structures", Cambridge
University Press 1998.
0.1 How to prove combinatorial statements
0.2 The number of disjoint k-tuples of subsets of [n]
0.2.1 Standard method
0.2.2 Bijective proof
0.3 Spanning trees of certain classes of graphs
1 Combinatorial Species
1.3 Formal power series
1.4 Generating series of species
1.5 Combinatorial equality
1.6 Sum of species
1.7 Product of species
1.8 Sequences without labels
1.9 Sequences with labels (surjections)
1.10 Sustitution of species
1.11 Derivation of species
1.12 Lagrange-Bürmann inversion
2 Redfield-Pólya Theory
2.1 Group representations and Cayley-graphs
2.2 Group actions
2.3 Burnside's Lemma
2.4 Actions on sets of labelled objects
2.5 Cycle indicator series
2.6 Cycle indicator series with weight functions
3.1 Posets, basic definitions
3.2 Lattices, basic definitions
3.3 Theorem of Sperner and symmetric chain decompositions
3.4 Theorem of Dilworth
3.5 The Marriage Theorem
3.6 The Incidence Algebra
3.7 Möbius inversion
3.8 Möbius inversion and sets - The inclusion-exclusion principle
3.9 Möbius inversion in number theory
3.10 Möbius function and topology - Euler-characteristic
3.10.1 Euler-characteristic of order complexes
3.10.2 Euler-characteristic of cell complexes
3.10.3 Euler-characteristic of surfaces
4 Restricted compositions and partitions (by M. Schlosser)
Below you find questions for the exams on 11 and 28 February. For future exams, this list will be different.
1. Sketch one of the proofs (your choice) of how to determine the number of disjoint k-tuples of
2. Sketch the idea of how to determine the number of spanning trees in the ladder graphs.
3. Give a precise formal definition of a "species of structures" and explain the definition with an
4. Determine the expansion of (1-√1-4z)/(2z)
around z=0 as formal power series.
5. Define formal power series in general. Define generating and type generating functions of combinatorial
Define combinatorial equality (isomorohism). Show that the species of linear orders and the species of permutations
have the same generating function and show that hey are not isomorphic.
6. Define sum and product of species. What can we say about their generating and type generating functions?
7. Detemine the number of triangulations of an n-gon. Formulate and solve the problem using species of structures.
8. Detemine the number of domino-sequences of length n. Formulate and solve the problem using species of structures.
9. Detemine the number of plane rooted trees with n vertices. Formulate and solve the problem using species of structures.
10. Detemine the number of surjections from an n-element set onto an r-element set in general and for specific
values of n and r. Express the species of such surjections in terms of the species of sets.
11. Define and explain the composition of combinatorial species.
12. Find identities for the following combinatorial species using sums, products, compositions or derivatives of other
combinatorial species. Examples:
linear orders, ballots, endofunctions, plane rooted trees, binary plane rooted trees, pre-orders,...
13. Define the derivation of species. Explain examples as partial partitions or linear orders.
14. What is the chain rule for derivations of species? Give at least a heuristic explanation of this
15. Which formal power series have a multiplicative inverse, which have compositional inverses and why?
16. What is Lagrange inversion?
17. Use Lagrange inversion to compute the number of triangulations of an n-gon.
18. Use Lagrange inversion to prove Cayley's formula on the number of labelled trees with or without
19. Explain the problem of the 100 prisoners and explain how to solve it.
20. Determine the group and a Cayley-graph for a given presentation.
21. Determine the group and a Cayley-graph for the automorphism group of a given graph.
22. Define group actions. Give examples of actions where the homomorphism is injective, not injective,
not surjective. Define free action and transitive action and give examples.
23. Take two points in the orbit of a group action. Show that the number of group elements that map one point
other is the same as the cardinality oftheir pointwise stabilizers.
24. Use the result in the previous question to show that the product of the cardinality of a stabiliser of a
with the cardinality of the orbit of that point is the order of the group.
25. Given a geometric object with a group of symmetries. How do we detemine the number of different
color this object with a given number of colors using the cycle indicator series? State Burnside's Lemma and
explain how it is used here.
26. Determine the cycle indicator series for given group actions. The examples will be easy or similar to
considered in the lecture. In particular consider symmetries of bracelets, necklaces, cube, octahedron and
27. Determine the number isomorphy classes of graphs with four vertices using a cycle indicator series.
28. How can we use weight functions for cycle indicator series to determine colorings where certain colors
certain number of times. You will get such an example.
29. Define: poset, maximal element, maximum, supremum, lattice, Jordan-Dedekind-property and rank in a poset.
When does a finite
poset have a rank function?
30. Define supremum and infimum and show that they are unique if they exist. Show that infimum and supremum
31. Formulate and prove the Theorem of Sperner on the size of maximal antichains in the subset lattice. You
can prove it directly or
you can formulate the Theorem of de Bruin on symmetric chain decompositions of the divisor lattice and show that this implies
the Theorem of Sperner.
32. Formulate and prove the Theorem of de Bruin on symmetric chain decompositions of the divisor lattice. Why
does it also hold for
the subset lattice? How does it imply the Theorem of Sperner?
33. Formulate and sketch the proof the Theorem of Dilworth on maximal antichains and minimal chain
34. Formulate and prove the Marriage Theorem. You may use the Theorem of Dilworth here without proving
35. Define the incidence algebra of a poset and show that it is isomorphic to a subalgebra of the upper
36. When does an element of the incidence algebra have an inverse? Show how to compute it with an explicite
37. How can we compute the number of chains of a given length between two given points and how can we compute
the total number of
chains in a finite poset between two given points?
38. Define the Zeta-function and the Möbius-function. Derive a recursive formula with which you
compute the Möbius-function and use it to compute single values for given
examples of posets.
39. You will get a concrete example of a poset. Compute the matrix of the Möbius-function. To check that
multiply it with the matrix of the Zeta-function and show that you obtain the unity matrix.
40. What is a dual theorem on posets? How do obtain such theorems? You will get a theorem on posets and you
will be asked to
formulate the dual theorem, such as the dual Theorem of Weisner.
41. Formulate one of the Möbius-inversion formulas. Use it to prove the
42. Prove the principle of inclusion and exclusion using Möbius-inversion.
43. Define a simplicial complex and its Euler characteristic. Define the order-complex of a poset.
Determine the Euler characteristic of the order complex of a given poset. What does this have to do with the
44. Define a cell-complex. Determine the Euler characteristic of a cell-complex that generates a given topological space. You will
get an example that we have discussed in the lecture and which you can find in the lecture notes.
You do not have to reproduce the proofs of the following theorems and the corresponding lemmas in the written part
of the exam, but you have to
explain them in the oral exam using lecture notes:
a) Lagrange inversion for Laurent series
b) Burnside's Lemma
c) Möbius inversion formula, both proofs
d) Weisner's Theorem