MATH 357 – Combinatorics Review Sheet for Exam 1 February 17, 2017

General Information and Groundrules

The first midterm exam in Combinatorics this semester will be given (as announced in the course syllabus) in class on Friday, February 24. This will be a closed-book, individual exam. You may use a basic calculator if you like, but even that should not be necessary, since it will be OK (preferred, in fact!) to leave answers expressed in terms of the numbers P (n, k), \binom{n}{k}, s(n, k), etc.

What might be covered

The exam will cover all of the material we have studied so far this semester, though the material from section 3.5 on “dividers” (a.k.a. “stars and bars”) and 3.6 on multinomial coefficients. Note that this is slightly beyond the sections covered on Problem Set 3. Specifically this means:

0) Mathematical sets, unions, intersections, functions, etc.

1) The game Set and the structure of “sets” in the 81-card Set deck

2) The Multiplication and Addition Principles

3) The Pigeonhole Principle

4) Permutations, cycle decompositions, counting permutations by cycle type or cycle index, the Stirling numbers of the first kind (Know the proof of the recurrence relation s(n + 1, k) = ns(n, k) + s(n, k − 1).)

5) Legendre’s theorem on divisiblity of n! by a primes p.

6) Numbers of permutations P (n, k) and binomial coefficients \binom{n}{k} and the counting problems they solve.

7) Poker hands and related counting problems

8) Binomial coefficient identities (Know algebraic and combinatorial proofs of the “Pascal’s triangle” identity \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k−1} and be ready to prove other identities by either approach.)

9) The “dividers” method and applications

10) Multinomial coefficients.

Some practice problems

Disclaimer: These problems are only intended to give you an idea of the range of topics and the possible ways questions might be phrased. The actual exam questions might not be exactly like these! This list is also quite a bit longer than the actual exam will be.

I. A) How many bit strings of length 9 are there?

B) How many bit strings of length 9 are there which start with a 0 and which have at

least one other 0? C) How many bit strings of length 9 are there, such that every 1 is followed immediately

by a zero? (Hint: Break this one into cases depending on how many 1’s there are.)

II. A) You are in a city with rectangular blocks. You want to walk from point A five blocks

north and three blocks east to point B, while walking north or east for every block. In how many ways can you get from A to B?

B) Same question but supposing you start out by heading north from point A?

III. A) In the card game Set, suppose you deal 5 cards and place them face up on a table.

What is the largest number of 3-card “sets” that could be contained in that collection of cards? Give an example and explain why some other set of 5 cards could not contain any more “sets” than your 5 cards.

B Same question as A, but with 6 cards.

IV. How many numbers must you pick to ensure that at least three of them have the same remainder when divided by 11?

V. How many functions are there from the set X = {1, 2, 3} to the set

Y = {A, B, C, D, E, F, G}?

How many of these are one-to-one (injective)?

VI. A) How many permutations are there in S_{17} with cycle type [3, 3, 3, 3, 2, 2, 1]? B) State and prove the recurrence relation for the Stirling numbers of the first kind. C) Using part B and the base cases for the s(n, 1), s(n, n) (or other methods as appro-

priate), compute the Stirling number of the first kind s(5, 3).

VII. What is the largest power of 6 that divides 100!?

VIII. A) A store sells 8 kinds of balloons and they have at least 30 balloons of each kind in

stock. How many different combinations of 30 balloons can be chosen? B) What if the store has only 10 red balloons, but at least 30 of every other kind of

balloon?

IX. A pool of available computer programmers has 13 members–six men and seven women. A) In how many ways can you choose a team of five from the pool? B) In how many ways can you choose a team of five, with two men and three women? C) In how many ways can you choose a team of five, with at most three men?

D) Give a combinatorial proof that

\binom{13}{5} = ∑_{m=0}^{5} \binom{7}{m}\binom{6}{5 − m}

(Note: Generalizing this gives: If 1 ≤ ℓ ≤ n − 1, then

\binom{n}{k} = ∑_{m=0}^{k} \binom{ℓ}{m}\binom{n − ℓ}{k − m}

called the Vandermonde convolution identity.) E) Suppose that one of the men and one of the women are a divorced couple, and they

refuse to work together. In how many ways can you choose a team of five, with two men and three women, respecting the wishes of the divorced couple?

X. A) What is the coefficient of x^{4}y^{2} in (3x + 5y)^{6}? B) What is the coefficient of x^{3}y^{2}z in (x + 2y + 3z)^{6}?