MATH 357 – Combinatorics Solutions for Review Problems for Final Exam May 1, 2017

1.3.13. Let H be the set of guests who have a hamburger and let D be the set who have a hot dog. The given information is |H| = 25, |D| = 18, and |H ∩ D| = 10. Since it is given that everyone had either a hamburger or a hot dog, the set of guests is H ∪ D and by the Inclusion-Exclusion Principle,

|H ∪ D| = |H| + |D| − |H ∩ D| = 25 + 18 − 10 = 33.

1.4.8. If σ, τ are both bijections of X, then consider σ ∘ τ. If (σ ∘ τ)(x) = (σ ∘ τ)(x′), the σ(τ(x)) = σ(τ(x′)). Since σ is injective (one-to-one), this implies τ(x) = τ(x′). But then x = x′ since τ is also injective. This shows σ ∘ τ is injective. Now, let x ∈ X be arbitrary. Since σ is surjective (onto), there is some y ∈ X such that σ(y) = x. But τ is also surjective, so there is some z ∈ X such that y = τ(z). Substituting this into the previous equation gives σ(τ(z)) = (σ ∘ τ)(z) = x. Since x was arbitrary, this shows σ ∘ τ is surjective as well, hence bijective.

1.5.7. (This problem is very like Example 1.5.3 in the text.) Let a_{1}, …, a_{32} be the number of math problems done after day 1, day 2, ..., day 32. We have a_{32} ≤ \frac{9}{8} · 32 = 36. Now consider the “pigeons” to be the numbers

a_{1}, a_{2}, …, a_{32}, a_{1} + 27, a_{2} + 27, …, a_{32} + 27

and the “pigeonholes” to be the number values. We have 32 + 32 = 64 numbers in the range 1 to 36 + 27 = 63. Hence two of them must be the same, say

a_{i} = a_{j} + 27.

The a_{i} are strictly increasing with i, so we must have i > j here, hence a_{i} − a_{j} = 27 and this represents the number of problems done between day j + 1 and day i, a consecutive string of days. This is what we wanted to show.

2.1.22. Note: I’m assuming the whole password consists of 8 characters.) (i) 26^{6} · 10^{2} ( (ii) 25 · 26^{5} · 10^{2}. (iii) 26^{6} · 99 (iv) 25 · 26^{5} · 99.

2.2.9. By the Inclusion-Exclusion Principle, the number is

26^{5} + 25^{6} − 25^{5}

(the last term is the number of words that begin with a and contain no b).

2.3.9. The number depends on whether n is even or odd. If n is even there are n/2 odds and n/2 evens in [n]. To make a permutation with evens and odds alternating, we can either begin with and even or an odd. The total number is 2 · (n/2)!(n/2)!. For instance, with n = 4, there are 8 such permutations. In the “one-row” format (not cycle decomposition), they are:

(1234), (1432), (3214), (3412), (2143), (2341), (4123), (4321).

If n is odd, then there are (n + 1)/2 odds and (n − 1)/2 evens in [n]. To make one of the required permutations, we must start with an odd (i.e. 1 must map to an odd). Otherwise, we “run out” of evens before odds. There are ((n − 1)/2)!((n + 1)/2)! such permutations. For instance, with n = 5, there are 12 such permutations. (Write them down to make sure you understand!)

2.4.8. We use Corollary 2.4.2 and Inclusion-Exclusion. There are

⌊\frac{10000}{3}⌋ = 476

numbers divisible by 21 = 3 · 7,

⌊\frac{10000}{33}⌋ = 303

numbers divisible by 33 = 3 · 11, and

⌊\frac{10000}{231}⌋ = 43

numbers divisible by 231 = 3 · 7 · 11. Hence the number divisible by 21 or 33 is

476 + 303 − 43 = 736.

2.5.9. Let I, II, III, IV be the sets of elections where conditions (i),(ii),(iii),(iv) respectively are satisfied. Note that |I| = P (19, 3) = 19 · 18 · 17 = 5814 (the other three positions are three other distinct people). We also have |II| = P (19, 3) = 19 · 18 · 17 = 5814, but |I ∩ II| = P (18, 2) = 18 · 17 = 306. Then |III| = 18 · 17 · 2 = 612 and |IV | = P (18, 4) = 18 · 17 · 16 · 15 = 73440. Now the set where at least one condition is satisfied is I ∪ II ∪ III ∪ IV. Note that (I ∪ II) ∩ III = ∅, (I ∪ II) ∩ IV = ∅, III ∩ IV = ∅. Hence by the Addition Principle, and Inclusion-Exclusion, we have

|(I ∪ II) ∪ III ∪ IV | = |I ∪ II| + |III| + |IV | = (5814 + 5814 − 306) + 612 + 73440 = 85347.

(There are 20 · 19 · 18 · 17 = P (20, 4) = 116280 total different election outcomes.)

2.7.15. The number is

(\frac{P (25, 8)}{8}) (\frac{P (17, 8)}{8}) (\frac{P (9, 6)}{6})

(The last three numbers go into the three 1-cycles and there is only one way that can happen. You could also express the number of ways to pick them as

\frac{1}{3!}P (3, 1)P (2, 1)P (1, 1) = 1.

3.1.15. There are \binom{6}{3} ways to pick the digits that come from \{2, 3, 5, 9\}. Since repeated digits are allowed, there are 4^{3} ways to pick the digits themselves. The locations of the other digits from {1, 4, 6, 7} are then determined and there are 4^{3} ways to pick them. The number of security codes is \binom{6}{3}4^{3} · 4^{3} = 81920.

3.2.7. There are 13 denominations for the three cards and \binom{4}{3} = 4 possibilities for the suits. Then there are 12 possible denominations for the pair and \binom{4}{2} = 6 possibilities for the suits. This gives

13 · 4 · 12 · 6 = 3744

possible full house hands.

3.3.8. We construct such a bijection inductively. If n = 1, then the subsets of [1] are ∅ (with an even cardinality = 0) and [1] with odd cardinality. So clearly there are as many subsets of [1] with even cardinality as with odd cardinality in this base case and the bijection just maps ∅ to [1]. Now, assume we have such a bijection for subsets of [k − 1] and consider subsets of [k]. Every such subset either contains k or it does not. If it does not then, it is a subset of [k − 1] and there is a bijection between the number of such subsets with even cardinality and those with odd cardinality by the induction hypothesis. If the subset A ⊆ [k] does contain k, then it has the form A = A′ ∪ {k} for some A′ ⊆ [k − 1]. Clearly |A′| even ⇒ |A| odd and vice versa. By the induction hypothesis again, there is a bijection between subsets of [k] containing k with even cardinality and those with odd cardinality. This gives the required bijection for subsets of [k] by patching the two bijections together (i.e. the one for subsets that do not contain k and the bijection for those that do) and we are done by induction.

3.5.6. This is slightly tricky but it also follows by the “dividers” method. The trick is that you now need to think of the k dominoes as the dividers and the m − 2k unoccupied columns within the m × 1 array as the things between the dividers. This gives a total number of placements equal to

\binom{(m − 2k) + k}{k} = \binom{m − k}{k}.

3.6.20. Since the two Ns, the two Us and the two Os are indistinguishable, the number is

\binom{10}{2, 2, 2, 1, 1, 1, 1} = \frac{10!}{2!2!2!}.

See Example 3.6.9.

4.2.12. This is slightly ambiguous, depending on whether you interpret k-tuple as meaning an ordered list or an unordered list. If it is ordered, then this is the same as the number of ways to distribute n unlabeled balls to k labeled urns with no urn empty, or \binom{n−1}{k−1} (dividers). If the list is unordered, then think unlabeled urns, so the number is p(n, k) – the number of partitions of n into exactly k positive parts. (Also note, it’s the k-tuples that are “distinct” – this does not mean that the numbers in the k-tuple are distinct.)

4.2.19. The right side k^{n} is the number of ways of distributing k labeled balls into n labeled urns. The left side counts the same thing, but breaking it down into all the possible cases of how many balls go to each urn, and using the Addition Principle. The term \binom{n}{λ_{1},...,λ_{k}} counts the number of ways to distribute the n labeled balls into the k labeled urns where urn 1 gets λ_{1} balls, urn 2 gets λ_{2} balls, etc. That equals the k^{n} since we are summing over all collections of (λ_{1}, …, λ_{k}) where λ_{i} ≥ 0 for all i, and λ_{1} + ⋯ + λ_{k} = n.

4.3.14. The number is p(11, 5) = p(10, 4) + p(6, 5) = 9 + 1 = 10. They can be represented like this (this is equivalent to counting partitions):

\begin{matrix}7 + 1 + 1 + 1 + 1, 6 + 2 + 1 + 1 + 1, 5 + 3 + 1 + 1 + 1, 5 + 2 + 2 + 1 + 1, 4 + 4 + 1 + 1 + 1, \\ 4 + 3 + 2 + 1 + 1, 4 + 2 + 2 + 2 + 1, 3 + 3 + 3 + 1 + 1, 3 + 3 + 2 + 2 + 1, 3 + 2 + 2 + 2 + 2 \end{matrix}

4.3.15. (See Example 4.3.11 which is somewhat similar). Distribute the unlabeled red balls first. Suppose that out of the n_{1}, j_{1} go into the unlabeled red urns and the other n_{1} − j_{1} of them go into the labeled white urns. There are

p(j_{1}, 1) + ⋯ + p(j_{1}, k_{1}) = ∑_{ℓ=1}^{k_{1}} p(j_{1}, ℓ)

ways to do the distribution to the red urns and then \binom{n_{1}−j_{1}+k_{2}−1}{k_{2}−1} ways to distribute the others to the white urns. We then multiply and sum over j_{1} to get the total number of ways to distribute the red balls:

(1) ∑_{j_{1}=1}^{n_{1}} (∑_{ℓ=1}^{k_{1}} p(j_{1}, ℓ)) · \binom{n_{1} − j_{1} + k_{2} − 1}{k_{2} − 1}.

Now we do the labeled white balls. Suppose j_{2} of them go into the unlabeled red urns and the other n_{2} − j_{2} go into the labeled white urns. There are

S(j_{2}, 1) + ⋯ + S(j_{2}, k_{2}) = ∑_{m=1}^{k_{2}} S(j_{2}, m)

ways to do the distribution to the red urns, and k_{2}^{n_{2}−j_{2}} ways to the do the distribution to the white urns. Then the total number of ways to distribute the white balls is

(2) ∑_{j_{2}=1}^{n_{2}} ( ∑_{m=1}^{k_{2}} S(j_{2}, m)) (k_{2}^{n_{2}−j_{2}}) .

Finally, by the Multiplication Principle, the total number of ways to distribute is the product of the sum in (1) times the sum in (2) – too complicated to write out on one line(!)

5.3.9 (just say how you would solve this using a generating function). This would be the coefficient of x^{100} in the Taylor expansion of

\frac{1}{1 − x} · \frac{1}{1 − x^{5}} · \frac{1}{1 − x^{10}} · \frac{1}{1 − x^{20}} · \frac{1}{1 − x^{50}} · \frac{1}{1 − x^{100}} .

5.4.9 (same directions). This would be the sum of the coefficients of all the terms u^{i}v^{j} with 3 ≤ i ≤ 11 and 5 ≤ j ≤ 13 in the expansion of

\frac{1}{1 − uv^{2}} · \frac{1}{1 − u^{4}v^{3}} · \frac{1}{1 − u^{5}v^{5}} · \frac{1}{1 − u^{6}v^{7}} .

6.1.20 (figure 6.2 is at the top of the page). Note that there are R_{0} = 1 squares in s_{0}, R_{1} = 6 squares in s_{1}, and R_{2} = 26 squares in s_{2}. In going from s_{n−1} to s_{n} we place a copy of s_{n−1} into each quadrant of the larger graph, and then we also add the large outside square and the small central square. Therefore the total number of squares in s_{n} is 4 times the number of squares in s_{n−1}, plus 2:

R_{n} = 4R_{n−1} + 2

for all n ≥ 1.

6.3.10 (solve with a generating function and by the “shortcut” method). The generating function R(x) satisfies

(1 − x − 6x^{2})R(x) = R_{0} + (R_{1} − R_{0})x = x

so

R(x) = \frac{x}{1 − x − 6x^{2}}

Now, using partial fractions, we have

= \frac{x}{(1 − 3x)(1 + 2x)} = \frac{1/5}{1 − 3x} + \frac{−1/5}{1 + 2x}.

So expanding in geometric series, we see that

R_{n} = \frac{1}{5} · (3^{n} − (−2)^{n}).

The shortcut method gets us to the same place somewhat more quickly. The characteristic polynomial is 1 − x − 6x^{2} = (1 − 3x)(1 + 2x) so the general solution is

R_{n} = A · 3^{n} + B · (−2)^{n}

for some A, B. From n = 0 we get 0 = A + B and from n = 1, we get 1 = 3A − 2B. Therefore A = \frac{1}{5} and B = \frac{−1}{5}.

6.5.27. Because the characteristic polynomial is 1 − 8x + 16x^{2} = (1 − 4x)^{2}, we need to take a particular solution of the form Cn^{2}4^{n} using Table 6.1. The solution has the form (A + Bn)4^{n} + Cn^{2}4^{n} and we can solve for A, B, C from the given initial values R_{0} = 1, R_{1} = 1, R_{2} = 8 − 16 + 4^{2} = 8. Answer:

R_{n} = 4^{n} (1 − \frac{5n}{4} + \frac{n^{2}}{2} ) .

7.1.16 (just say how you would solve it using generating functions). We need to use generating functions and Inclusion-Exclusion for this since we are counting the number of elements of a union of four sets. Let A, B, C, D be the sets of solutions of the equation with each of the constraints separately. Then

|A| = coeff. of x^{35} in \frac{1 + x + ⋯ + x^{12}}{(1 − x)^{3}}
|B| = coeff. of x^{35} in \frac{1 + x + ⋯ + x^{10}}{(1 − x)^{3}}
|C| = coeff. of x^{35} in \frac{1 + x + ⋯ + x^{7}}{(1 − x)^{3}}
|D| = coeff. of x^{35} in \frac{1 + x + ⋯ + x^{4}}{(1 − x)^{3}}

|A ∩ B| = coeff. of x^{35} in \frac{(1 + x + ⋯ + x^{12})(1 + ⋯ + x^{10})}{(1 − x)^{2}}
|A ∩ C| = coeff. of x^{35} in \frac{(1 + x + ⋯ + x^{12})(1 + ⋯ + x^{7})}{(1 − x)^{2}}
|A ∩ D| = coeff. of x^{35} in \frac{(1 + x + ⋯ + x^{12})(1 + ⋯ + x^{4})}{(1 − x)^{2}}
|B ∩ C| = coeff. of x^{35} in \frac{(1 + x + ⋯ + x^{10})(1 + ⋯ + x^{7})}{(1 − x)^{2}}
|B ∩ D| = coeff. of x^{35} in \frac{(1 + x + ⋯ + x^{10})(1 + ⋯ + x^{4})}{(1 − x)^{2}}
|C ∩ D| = coeff. of x^{35} in \frac{(1 + x + ⋯ + x^{7})(1 + ⋯ + x^{4})}{(1 − x)^{2}}

|A ∩ B ∩ C| = coeff. of x^{35} in \frac{(1 + ⋯ + x^{12})(1 + ⋯ + x^{10})(1 + ⋯ + x^{7})}{(1 − x)}
|A ∩ B ∩ D| = coeff. of x^{35} in \frac{(1 + ⋯ + x^{12})(1 + ⋯ + x^{10})(1 + ⋯ + x^{4})}{(1 − x)}
|A ∩ C ∩ D| = coeff. of x^{35} in \frac{(1 + ⋯ + x^{12})(1 + ⋯ + x^{7})(1 + ⋯ + x^{4})}{(1 − x)}
|B ∩ C ∩ D| = coeff. of x^{35} in \frac{(1 + ⋯ + x^{10})(1 + ⋯ + x^{7})(1 + ⋯ + x^{7})}{(1 − x)}
|A ∩ B ∩ C ∩ D| = coeff. of x^{35} in (1 + ⋯ + x^{12})(1 + ⋯ + x^{10})(1 + ⋯ + x^{7})(1 + ⋯ + x^{4})

Then

|A ∪ B ∪ C ∪ D| = ∑_{I⊆[4],I≠∅}(−1)^{|I|+1} |⋂_{i∈I} A_{i}| .

7.3.4. Recall that we know D_{n} = n! ∑_{m=0}^{n} \frac{(−1)^{m}}{m!} . Hence

lim_{n→∞} \frac{D_{n}}{n!} = lim_{n→∞} ∑_{m=0}^{n} \frac{(−1)^{m}}{m!} = e^{−1}.

8.3.20. The 4 × 4 grid with squares labeled by [16] is our X. The group acting is C_{4} = {e, ρ, ρ^{2}, ρ^{3}} acting by rotations about the center point of the grid. Let’s label the squares 1, 2, 3, 4 left to right across the top row, then 5, 6, 7, 8 left to right across the second row, etc. We see

Inv(e) = [16]
Inv(ρ) = ∅
Inv(ρ^{2}) = ∅
Inv(ρ^{3}) = ∅

By Burnside’s Lemma, the number of orbits is equal to

\frac{1}{|G|} ∑_{g∈G} |Inv(g)| = \frac{1}{4}(16 + 0 + 0 + 0) = 4.

(The orbits are {1, 4, 13, 16} (the corners), {2, 9, 15, 8} and {3, 5, 14, 12} (interior points of outside rows and columns), and {6, 7, 10, 11} the 4 points in the “inside ring.”)

8.5.12 (just say how you would solve it using the Polya Theorem). We begin by computing the cycle index polynomial for this action of C_{4} on X. We have

cim(e) = x_{1}^{16}
cim(ρ) = x_{4}^{4}
cim(ρ^{2}) = x_{2}^{8}
cim(ρ^{3}) = x_{4}^{2}

Hence

Z_{C_{4}}(x_{1}, x_{2}, x_{4}) = \frac{1}{4}(x_{1}^{16} + 2x_{4}^{2} + x_{2}^{8}).

Then by the Polya Theorem, the number of distinct two-colorings of the 4 × 4 grid using the first color 10 times and the second 6 times is equal to the coefficient of c_{1}^{10}c_{2}^{6} in the expansion of

Z_{C_{4}}(c_{1} + c_{2}, c_{1}^{2} + c_{2}^{2}, c_{1}^{4} + c2^{4}).

(In case you are interested, this number is 2016.)