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

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?

Solution: There are 2^{9} such strings by the Multiplication Principle (2 choices for each of the 9 bits).

B) How many bit strings of length 9 are there which start with a 0 and which have at least one other 0? Solution: There are 2^{8} − 1 such strings. After the leading 0, we can have any of the 2^{8} strings of length 8, except for 11111111.

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.) Solution: Since there are 9 bits in all, the largest number of 1’s that you can have is 4.

• If there are no ones, you have the all-0 string, so 1 of those

• If there is exactly one one, then it can only come in positions 1 through 8 in the string because there must be (at least one) zero after it. There are 8 of these.

• If there are exactly two ones, then they can come in positions

(1, 3), (1, 4), …, (1, 8)

or

(2, 4), (2, 5), … (2, 8)

or

(3, 5), (3, 6), (3, 7), (3, 8)

or

(4, 6), (4, 7), (4, 8)

or (5, 7), (5, 8), or (6, 8), so 21 of these.

• If there are exactly three ones, then can come in positions

(1, 3, 5), (1, 3, 6), (1, 3, 7), (1, 3, 8)

or

(1, 4, 6), (1, 4, 7), (1, 4, 8),

or

(1, 5, 7), (1, 5, 8)

or (1, 6, 8), or

(2, 4, 6), (2, 4, 7), (2, 4, 8)

or (2, 5, 7), (2, 5, 8), or (2, 6, 8), or (3, 5, 7), (3, 5, 8), or (3, 6, 8), or (4, 6, 8), so 20 of these.

• Finally, if there are exactly four ones, they can come in positions

(1, 3, 5, 7), (1, 3, 5, 8), (1, 3, 6, 8), (1, 4, 6, 8),

or (2, 4, 6, 8), so 5 of these. The total is 1 + 8 + 21 + 20 + 5 = 55. (Note: There are other ways to do these counts as well that are less “brute force” in nature!)

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? Solution: By the “dividers” or “stars and bars” method, the number is \binom{8}{5} = \binom{8}{3} = \frac{8·7·6}{3·2·1} = 56.

B) Same question but supposing you start out by heading north from point A? if you must start out heading north from point A, there are 7 remaining blocks to travel east or north, and you must do 4 more north blocks and 3 east blocks. The number if \binom{7}{4} = \binom{7}{3} = \frac{7·6·5}{3·2·1} = 35.

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. Solution: In that collection of 5 cards, there are \binom{5}{3} = 10 triples. However, recall that any two cards in a “set” determine the third card uniquely. Hence if the five cards are a, b, c, d, e and we stipulate that {a, b, c} is a “set,” then the six triples {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {b, c, d}, {b, c, e} cannot be “sets” because they each share two cards with the triple that is a “set.” However, one of the cards in the first set, say a, can be in a second “set” {a, d, e} with the two remaining cards, d, e. If we now rule out other sets containing exactly two of these cards, we must conclude {a, d, b}, {a, d, c}, {a, e, b}, {a, e, c}, {d, e, b}, {d, e, c} are not “sets” either. The first four of these were already ruled out from before with the “set” {a, b, c}, but the last two are not. Of the 10 possible triples, we have 2 that we have claimed are “sets,” and the remaining 8 triples are all ruled out. Therefore, the largest number of “sets” we could have is two(!) An example: Take the five cards to be

a, b, c, d, e = [0, 0, 0, 0], [1, 1, 1, 1], [2, 2, 2, 2], [1, 2, 1, 2], [2, 1, 2, 1]

There are exactly two “sets” in this collection {a, b, c} and {a, d, e}. Our argument shows there cannot be any more than two.

B) Same question Proceed as in part A. There are \binom{6}{3} = 20 triples. If the cards a, b, c do form a “set,” then the \binom{3}{2} · 3 = 9 triples

{a, b, d}, {a, b, e}, {a, b, f}, {a, c, d}, {a, c, e}, {a, c, f}, {b, c, d}, {b, c, e}, {b, c, f}

cannot be “sets.” Any remaining triples that are “sets” must have either one card in common with the first set or no cards in common with the first one. If there are no cards in common, then the second “set” is {d, e, f} and as before this means that none of

{a, d, e}, {b, d, e}, {c, d, e}, {a, d, f}, {b, d, f}, {c, d, f}, {a, e, f}, {b, e, f}, {c, e, f}

can be “sets.” We have 2 disjoint “sets” and 9+9 different distinct triples that cannot be “sets,” and that accounts for all 20 of the triples. So there cannot be any more than 2 “sets” in this case. The remaining case to consider is where the second “set” does have one card, say a, in common with the first “set.” For instance, if {a, d, e} is a “set,” then that rules out additional triples (but some of these have been listed before):

{a, b, d}, {a, c, d}, {a, d, f}, {a, b, e}, {a, c, e}, {a, e, f}, {b, d, e}, {c, d, e}, {d, e, f}.

Five of these did not appear in the first excluded list, so there are now two “sets” and 9 + 5 = 14 different triples that cannot be “sets.” In this case it is possible for a third “set” to exist. One of the triples that has not been excluded as a “set” is {b, d, f} (and up to the naming of the elements this is essentially the only case!) If that triple is also a “set” then we must rule out

{a, b, d}, {b, c, d}, {b, d, e}, {a, b, f}, {b, c, f}, {b, e, f}, {a, d, f}, {c, d, f}, {d, e, f}

Now we have 3 “sets” and 9+5+2 = 16 triples that cannot be “sets.” It looks as though there might be “room” for one more “set” in the sense that {c, e, f} has not been ruled out. But you can check that that one remaining triple can never satisfy the algebraic condition that would produce a set (the sums of the entries of the 4-tuples cannot all be 0 mod 3). This is because we know a + b + c ≡ 0 mod 3, a + d + e ≡ 0 mod 3 and b + d + f ≡ 0 mod 3. But then c ≡ 2a + 2b mod 3, e ≡ 2a + 2d mod 3 and f ≡ 2b + 2d mod 3. So a + c + f ≡ 2a + 2b + 2a + 2d + 2b + 2d ≡ a + b + d mod 3. But the triple {a, b, d} was one of the ones we ruled out and that means a + b + d mod 3 cannot equal 0. Thus the largest number of “sets” in 6 cards is actually 3(!) I’ll let you cook up such a collection of cards as actual 4-tuples of integers mod 3.

(Comment: This is too hard for an in-class exam question, so if you did not see how to finish it, don’t worry! I just wanted to get your problem-solving “juices” flowing!)

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

Solution: By the Generalized Pigeonhole Principle, if you have 23 numbers (the “pigeons”) and you place them into the 11 “pigeonholes” of their congruence classes mod11, then some pigeonhole must have strictly more than ⌊\frac{23−1}{11}⌋ = 2 pigeons. On the other hand you could have 22 numbers where there are exactly two in each of the congruence classes mod11. So 23 is the smallest number of numbers where this is guaranteed to happen.

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)?

Solution: There are 7 choices for f(1), 7 choices for f(2), and 7 choices for f(3). So by the Multiplication Principle, there are 7^{3} = 343 functions in all. Of these the injective functions are the ones where f(1) ≠ f(2), f(1) ≠ f(3), and f(2) ≠ f(3). There are P (7, 3) = 7 · 6 · 5 = 210 injective functions.

VI. A) How many permutations are there in S_{17} with cycle type [3, 3, 3, 3, 2, 2, 1]?

Solution: As in examples from class and Problem Set 2, the number of permutations with this cycle type is

\frac{1}{4!} (\frac{P (17, 3)}{3} · \frac{P (14, 3)}{3} · \frac{P (11, 3)}{3} · \frac{P (8, 3)}{3}) · \frac{1}{2!} (\frac{P (5, 2)}{2} · \frac{P (3, 2)}{2}) · 1.

B) State and prove the recurrence relation for the Stirling numbers of the first kind. Solution: The recurrence is

s(n + 1, k) = n · s(n, k) + s(n, k − 1).

The proof is as follows: s(n + 1, k) counts the number of permutations in S_{n+1} with cycle index k. This collection of permutations is the disjoint union of two subsets: The permutations with cycle index k that satisfy σ(n + 1) = n + 1 and the ones with σ(n + 1) ≠ n + 1. In the first case, (n + 1) will be a cycle of length 1 in the disjoint cycle decomposition. The remainder then consists of k − 1 cycles not containing n + 1. Hence these permutations are in 1-1 correspondence with the permutations in S_{n} with cycle index k − 1, and that number of such is s(n, k − 1). The permutations of the second type are all formed by inserting n + 1 in one location in a permutation in S_{n} with cycle index k. There are exactly n possible ways to insert the n + 1, so there are n · s(n, k) of these by the Multiplication Principle. By the Addition Principle, s(n + 1, k) = n · s(n, k) + s(n, k − 1) as claimed.

C) Using part B and the base cases for the s(n, 1), s(n, n) (or other methods as appropriate), compute the Stirling number of the first kind s(5, 3). Solution: We use the recurrence relation three times and collect like terms:

s(5, 3) = 4 · s(4, 3) + s(4, 2)
= 4 · (3s(3, 3) + s(3, 2)) + 3s(3, 2) + s(3, 1)
= 12 · s(3, 3) + 7 · s(3, 2) + s(3, 1)

We can stop here since we recall s(3, 3) = 1, s(3, 2) = 3, and s(3, 1) = 2. So

s(5, 3) = 12 · 1 + 7 · 3 + 2 = 35.

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

Solution: By the Legendre formula the highest power of the prime 2 that divides 100! is

∑_{k≥1}⌊\frac{100}{2^{k}}⌋ = 50 + 25 + 12 + 6 + 3 + 1 = 97

Similarly the highest power of the prime 3 that divides 100! is

∑_{k≥1}⌊\frac{100}{3^{k}}⌋ = 33 + 11 + 3 + 1 = 48

Since 6 = 2 · 3, the largest power of 6 that divides 100! is 6^{48}.

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? Solution: By the “dividers” method. This is the same as finding the number of ways of writing 30 = a_{1} + ⋯ + a_{8} with 0 ≤ a_{i} ≤ 30 for all i. This number is \binom{30+7}{7} = \binom{37}{7}.

B) What if the store has only 10 red balloons, but at least 30 of every other kind of balloon? Solution 1: Say a_{1} is the number of red balloons. There is a restriction now because 0 ≤ a_{1} ≤ 10 (we cannot have any more than 10 of them). The most direct way to count now is to use the Addition Principle and break things down by how many red balloons are included in the 30. The terms below are the numbers with 0, 1, 2, …, 10 red balloons, respectively:

\binom{36}{6} + \binom{35}{6} + ⋯ + \binom{26}{6}

Solution 2: An alternate way to think about it: If we could buy at least 11 red balloons, then we would be getting \binom{19+7}{7} = \binom{26}{7} out of the \binom{37}{7} total ways to make up 30 balloons from part A. So the number here should be \binom{37}{7}−\binom{26}{7} (by the Addition Principle). Good additional exercise: Convince yourself that

\binom{36}{6} + \binom{35}{6} + ⋯ + \binom{26}{6} = \binom{37}{7} − \binom{26}{7}.

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?

Solution: There are \binom{13}{5} ways. B) In how many ways can you choose a team of five, with two men and three women?

Solution: There are \binom{6}{2} · \binom{7}{3} ways. C) In how many ways can you choose a team of five, with at most three men?

Solution: We can have either 0, 1, 2, or 3 men, so by the Addition Principle there are

\binom{7}{5}\binom{6}{0} + \binom{7}{4}\binom{6}{1} + \binom{7}{3}\binom{6}{2} + \binom{7}{2}\binom{6}{3}

ways D) Give a combinatorial proof that

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

(Note: Generalizing this gives:

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

called the Vandermonde convolution identity.) Solution: The left hand side gives the total number of ways to pick a 5-person team from the pool of 13 programmers. The right hand side gives the same number but broken down into the different possible gender make-ups of the team. The term for each m, 0 ≤ m ≤ 5 gives the number of teams with exactly m women and 5 − m men.

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? Solution 1: There are \binom{6}{3} · \binom{5}{2} teams that contain neither of the two divorced people, \binom{6}{2} · \binom{5}{2} teams that contain the woman but not the man, and \binom{6}{3} · \binom{5}{1} that contain the man, but not the woman. By the Addition Principle, the total number is the sum

\binom{6}{3} · \binom{5}{2} + \binom{6}{2} · \binom{5}{2} + \binom{6}{3} · \binom{5}{1}.

Solution 2: Another way to do this is to count the number of teams containing both of the people from the divorced couple and subtract that from the total number of teams from part B:

\binom{7}{3} · \binom{6}{2} − \binom{6}{2} · \binom{5}{1}.

(You should check that these two ways of looking at the problem give the same result!)

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

Solution: The coefficient is \binom{6}{4} · 3^{4} · 5^{2}. B) What is the coefficient of x^{3}y^{2}z in (x + 2y + 3z)^{6}?

Solution: This involves a multinomial coefficient: \binom{6}{3,2,1} · 2^{2} · 3.