Introduction to Combinatorics
Homework Assignments

Readings and Problems (and Extra Problems)

This page will be updated gradually.


To the main course page.

Readings

Study for the week of

Sections

Jan. 24: 1.1, 1.2. Generating functions. Basic enumeration problems and techniques.
Jan. 31: 1.3, 1.4. Counting permutations by various parameters (permutation statistics). Partitions and compositions of a set or an integer. Maximal chains in the power set of a set and in a finite vector space. Maximal chains. Philosophy and classification of counting problems; arrangement vs. distribution.
Feb. 7: 1.3, 1.4. More of the same.
Feb. 14: 1.4, 2.1-2.2. Partitions (of a set, of an integer) and their generating functions. Calculus of finite differences. Principle of Inclusion and Exclusion.
Feb. 21: 2.2-2.4. Permutations with restricted position. Boards and rook polynomials.
Feb. 28: 2.4-2.7. Ferrers boards. Counting unimodal sequences. The involution principle. Nonintersecting lattice paths.
Mar. 7: 2.7, 3.1-3.2. Nonintersecting lattice paths. Partially ordered sets.
Mar. 14: 3.3-3.5. Lattices and distributive lattices.
Mar. 28: 3.5-3.6 Distributive lattices. The incidence algebra.
Apr. 4: 3.6-3.9 Möbius madness: Möbius function, Möbius inversion, Möbius algebra, Möbius-function identities.
(Extra class this week.)
Apr. 11: 3.10-3.12 Möbius functions on semimodular lattices, with nice examples. Chains, multichains, and the zeta polynomial of a poset. Rank-selected invariants.
Apr. 18: 3.12-3.13 Rank-selected invariants. R-labellings.
Guest lecture Friday (Combinatorics Seminar) at our regular class time.
Apr. 25: 3.13-3.14 R-labellings. Eulerian posets.
May 2: 3.14-3.16 Eulerian posets. Binomial posets and generating functions. Rank selection in binomial posets and permutation enumeration.

Problems

Suggestions about problems

I'm not assigning specific exercises. You should work on as many as you can while doing a good job. I have the impression that the exercises for each chapter are in an order that corresponds to the order of the material of the chapter, but this may not be true. Certainly they're not in order of difficulty. So, don't just start at the first exercise; look around.

You'll find more good exercises if you read the text closely. There are many (deliberate) gaps in the proofs and examples, where filling in the details can be interesting or challenging (or both).

I expect you'll be working on more than just the three hand-in solutions each week. That's part of doing the job. (You can hand in your best solutions, of course.)

If you have any questions, e.g., if you get stuck and want an idea, I'm around most afternoons. Stop in and see me some time.

Submitting solutions

I will expect you to hand in three solutions each week, due the following Monday. (The first due date is Jan. 31.) They should (mostly) be related to the work of that week. I'll grade and return them as soon as I can. Which ones you hand in is up to you, but do have some every week, and make sure they're written neatly so I can read them.

If you don't like the grade on a problem, you may turn in a second solution (to the same problem) within two weeks of the due date. (No third solutions.) Please be sure to give me both the original solution and the revised solution so I'll know what to look for.

Extra Exercises

Chapter 1

  1. [2-] The number of fixed points of the mapping π —> hat(π) on the set of permutations of [n] equals the n-th Fibonacci number (with F0 = F1 = 1).

Chapter 2

  1. [2-] Prove (14) on page 67 combinatorially, with a bijective proof.
  2. [2]
    1. Evaluate the determinant det(aij)1≤i,j≤n given that aij=0 if j<i-1 and =1 if j=i-1.
    2. Use the preceding part to prove the unnumbered displayed formula between (15) and (16) on page 69.
    3. Prove (16) and (17) on page 69 and Prop. 2.2.6.
  3. For positive h, k, n:
    1. [1+] Find the number of ways to pick k points on a circle of n labelled points so that each two consecutive chosen points are separated by at least h-1 points.
    2. [4] Find the number of ways if the circle is unlabelled.
  4. [3+] Cast the sieve argument of Section 2.5 for counting V-partitions into the algebraic framework of Exercise 2.3(a,b). You might do this separately for different values of n, but can you set up a single algebraic system for all positive n?
  5. [1+] Prove that (29) on page 80 does define a bijection from Fix(τ) to Fix(τ~).
  6. Consider the condition in Theorem 2.7.1 that Bπ=Ø for all nonidentity permutations π of [n].
    1. [2] Find (i) necessary and sufficient conditions on (α,β,γ,δ) that this be true when n=2. Also, (ii) find necessary and sufficient conditions that Bπ=Ø if and only if π is not the identity.
    2. [3-] The same, for n=3.
    3. [5-] The same, for all n.

Chapter 3

  1. [1] Recall that in a poset P, the height h(x) = length of a longest chain with x as its top element. Prove that P has finite height, h(P) := maxx h(x), if and only if it has finite length. Decide whether the height and length of a finite poset P must be equal.
  2. [1+] We "know" that a finite lattice is complete (did you prove it?). But we can generalize this. Recall the height h(x) = length of a longest chain with x as its top element, in a poset. Finite height means that max{h(x) : x in P} is finite. Prove: Theorem. Any lattice of finite height is complete. (We like this because it covers infinite but finite-dimensional vector-space lattices, for instance.)
  3. [1-] Show that every finite distributive lattice is modular.
  4. Let P = P1 × P2 × ... × Pm (a product of m finite posets).
    1. [2-] Prove the theorem that I(P,K) is naturally isomorphic to the tensor product of the I(Pi,K).
    2. [2-] Deduce the corollary that μ(x,y) = Prodi=1,...,m μ(xi,yi), where x=(x1,...,xm) and y=(y1,...,ym).
  5. [2+] Prove that, in a (finite) semimodular lattice, μ(x,y) ≠ 0 if and only if y is the join of the atoms of the interval [x,y].
  6. [5+] Develop the idea of q-analogy in Corollary 3.12.2 and Theorem 3.12.3 into a general correspondence between distributive lattices and semimodular or geometric lattices in which the case q=1 of semimodular lattices degenerates to distributive lattices. (Everything is finite.) Even a partial correspondence would be significant.


To the
main course page.