Mathematics 357 – Combinatorics Information on Final Exam April 26, 1996

Background

The final exam for Combinatorics will be given as an in-class individual exam at our scheduled time, 8:30 a.m. on Thursday, May 12. The exam will be comprehensive, covering all the material we have studied since the beginning of the semester. I will write the exam to be twice the length of the in-class midterms. However, you will have the full three-hour period 8:30 - 11:30 a.m. to work on the exam if you need that much time. The questions will be similar to those on midterms. I will include some questions asking for definitions of terms and statements of theorems, as well as some problems where you will need to apply the ideas to derive a result or prove an assertion.

Reading Week Schedule and Review Session

I will be out of town (visiting Oberlin College as their mathematics department’s External Honors Examiner) from about 2:00 pm on Wednesday, May 4 through the end of the day on Friday, May 6. I may be able to check email, but I’m not going to have much if any open time while I’m at Oberlin. If there is interest, I would be happy to run a review session Monday May 9 or Tuesday May 10 during the exam week. On Wednesday evening, I have another commitment off campus so I will not be available.

Topics to be Covered

1) Chapter 2: The Pigeonhole Principle (basic and strong forms), applications.

2) Chapters 3 and 4: Basic counting principles, permutations and combinations of sets, permutations and combinations of multisets. Methods for generating combinations systematically. (Note – we only discussed a portion of the material in Chapter 4, and you’re only responsible for the stuff from sections 3 and 4 that we did cover.)

3) Chapter 5: Binomial coefficients, identities, algebraic and combinatorial proofs, applications to counting problems. (Omit the material in sections 4 and 7 of this chapter.)

4) Chapter 6: Inclusion-Exclusion Principle in the “union” and “complement of union” forms. Applications to counting combinations with repetition, derangements, permutations with forbidden positions (“rook placement” problems). Also know how to compute and use rook polynomials for these counting problems, including the product and expansion rules. (Omit section 6.6.)

5) Chapter 7: Number sequences, recurrences, solving homogeneous and nonhomogeneous linear recurrences with constant coefficients. Generating functions, and the generating function technique for solving recurrences. (Omit section 7.7)

6) Chapter 9: Hall’s “Marriage Theorem”, matchings in bipartite graphs, applications. (Note: you are only responsible for the topics here we covered in class. There’s actually a lot more in Chapter 9 than we looked at, and it’s presented differently in some cases. So my advice is: use the class notes!)

7) Chapter 11: Terminology and basic concepts for graphs and multigraphs. Euler trails. Hamilton cycles. Trees and Cayley’s Theorem.

8) Chapter 14: Counting with symmetry, group actions, Burnside’s Theorem (know the statement, the proof, and how to apply it).

Suggestion on How to Study

Begin by reviewing the class notes, your graded problem sets and the solutions and the discussion write-ups from your group’s work. Look at the in-class midterm problems and try to work out solutions for those again, without refering to your previous work. Look over some of the problems from the text and try some new ones that look interesting. Also try the practice/review problems below.

Practice/Review Problems

Also see review sheets for Exams 1 and 2

A) A golfer has 11 weeks to prepare for the Masters golf tournament. He decides to play at least one round of 18 holes of golf each day, but so as not to tire himself, he will play no more than 12 rounds in any calendar week. Show that there is a string of consecutive days in which he plays exactly 21 rounds. (Hint: Pigeonhole.)

B) How many distinct words of length 7 can be formed from the alphabet 0, 1, 2? How many containing exactly 4 2’s? How many with no more than 4 2’s? How many with equal numbers of 0’s and 1’s?

C) How many distinct “monomials” x_{1}^{a_{1}}x_{2}^{a_{2}} ⋯ x_{k}^{a_{k}} are there of “total degree” a_{1} + ⋯ + a_{k} = n? (Here the x_{i} are commuting variables and a_{i} ≥ 0 are integers.) How many monomials are there that are divisible by x_{1}^{3} (assuming the total degree is at least 3)? How many monomials are there which are divisible by x_{i} for all 1 ≤ i ≤ k?

D) Let n ≥ r ≥ m be natural numbers. Use a “choice” argument to prove the binomial coefficient identity:

\binom{n − m}{r − m} = ∑_{k=0}^{m}(−1)^{k}\binom{m}{k}\binom{n − k}{r}

(Hint: The left hand side is the number of ways to choose r objects from a collection of n, always including some particular subset of m “special” objects in the r – for instance, committees with ex officio members.)

E) Show that the number D_{n} of derangements of {1, 2, …, n} satisfies the recurrence

D_{n} = nD_{n−1} + (−1)^{n}. Deduce from this that D_{n} is even if and only if n is odd. F) Use generating functions to show that the number of partitions of any positive integer

n with distinct parts is the same as the number of partitions of n with all odd parts. G) Find (some formula for) the term a_{50} in the sequence with generating function

f(t) = \frac{1 − t}{1 − 2t + 3t^{2}} = a_{0} + a_{1}t + ⋯ + a_{50}t^{50} + ⋯

H) Fix some numbering of the vertices and edges of a graph G = (V, E). The incidence matrix of G is the |V | × |E| (0,1)-matrix M with M_{ij} = 1 if vertex i is one of the endpoints of edge j and M_{ij} = 0 if not. Give a general statement (valid for all graphs) describing the form of the |V | × |V | matrix MM^{t} (for instance, what are the diagonal entries, what are the off-diagonal entries?)

1) Show that if G is not a tree, the rows of the incidence matrix are linearly depen-

dent mod 2. (The converse also holds; can you prove it?) I) How many distinct labeled trees of order 7 are there with degrees

d_{1} = 2, d_{2} = 1, d_{3} = 1, d_{4} = 4, d_{5} = 2, d_{6} = 1, d_{7} = 1?

What if we changed d_{3} to 3 and kept the other degrees the same? State and prove Cayley’s Theorem on trees.

J) State and prove Burnside’s Theorem. K) From the text: Chapter 14/10 and 22, 17, 18, 31