Introduction to Combinatorics
Homework Assignments

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.

• Rule 1: If your problems are too easy they will not get full credit.
• Rule 2: If you read the book's solution, you must say so in your solution. Otherwise, it's an automatic F if I think the book tells you the solution. If your solution is just the book's solution, I also will not accept it as your work, even if you say so; you're supposed to find a problem you can solve on your own. If the book's solution is just the starting point for yours, that's okay, but I want you to tell me that.
• Rule 3: If you read any source that tells you a solution or significant solution idea, you must cite it in your writing. This is the universal scholarly rule.

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 F₀ = F₁ = 1).

Chapter 2

1. [2-] Prove (14) on page 67 combinatorially, with a bijective proof.
2. [2]
   1. Evaluate the determinant det(a_ij)_1≤i,j≤n given that a_ij=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) := max_x 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 = P₁ × P₂ × ... × P_m (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(P_i,K).
   2. [2-] Deduce the corollary that μ(x,y) = Prod_i=1,...,m μ(x_i,y_i), where x=(x₁,...,x_m) and y=(y₁,...,y_m).
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.