Graded: 6.3 #24, 6.4 #22

6.3 #16

A set with 10 elements has $\binom{10}1+\binom{10}3+\binom{10}5+\binom{10}7+\binom{10}9=\boxed{512}$ subsets with an odd number of elements. Not coincidentally, this is $2^9$, or exactly half the total number of subsets; as shown in class, there is a bijective correspondence between subsets with an odd number of elements and subsets with an even number of elements.

6.3 #18

a) $2^8 = \boxed{256}$

b) $\binom 83 = \boxed{56}$

c) $2^8 – \binom 80 – \binom 81 – \binom 82 = \boxed{219}$

d) $\binom 84 = \boxed{70}$

$\bigstar$ 6.3 #24

We first arrange the women in any order, which can be done in $10!$ ways. The men can then occupy any 6 of the 11 positions indicated by blanks below: $$\_W\_W\_W\_W\_W\_W\_W\_W\_W\_W\_$$ No more than one man may be placed in each blank, so there are $P(11,6) = 11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6$ ways to arrange the men. Overall, the number of ways to arrange all the people is $10!\cdot P(11,6)$, or $\boxed{1{,}207{,}084{,}032{,}000}$.

6.3 #30

a) There are $\binom{16}5$ committees consisting of five members of the department, of which we discard $\binom 95$ that consist of all men. Thus there are $\binom{16}5-\binom 95 = \boxed{4242}$ possible committees with at least one member who is a woman.

b) Of the committees from part (a), we must now discard $\binom 75$ more which consist of all women. This leaves $\boxed{4221}$ possible committees with at least one woman and one man.

6.3 #36

The strings in question can be regarded as anagrams of nine “characters”: $$011~~011~~011~~011~~011~~1~~1~~1~~1$$ (where each 011 is regarded as a single, indivisible unit). There are $\binom 95=\binom 94=\boxed{126}$ such anagrams.

6.3 #41

We can seat $r$ people from a set of $n$ in $P(n,r)$ ways, but if we wish to regard arrangements that are rotations of each other as the same outcome, then $P(n,r)$ overcounts distinct outcomes by a factor of $r$. For example, the permutations 1234, 2341, 3412, and 4123 are counted separately as ordinary permutations, but all lead to the same circular permutation.

Therefore, the number of circular $r$-permutations of $n$ people is $\frac{P(n,r)}r$, which can also be expressed as $\frac{n(n-1)(n-2)\cdots(n-r+1)}r$ or $\frac{n!}{r\cdot(n-r)!}$.

6.4 #8

The term in $x^8y^9$ is $\binom{17}9(3x)^8(2y)^9$, so the coefficient of $x^8y^9$ is $\binom{17}9\cdot 3^8\cdot 2^9$, or $\boxed{81{,}662{,}929{,}920}$.

6.4 #10

The full expansion of $\left(x+\frac 1x\right)^{100}$ is $\sum\limits_{j=0}^{100} \binom{100}j x^{100-j}\left(\frac 1x\right)^j$, which simplifies to $\sum\limits_{j=0}^{100} \binom{100}j x^{100-2j}$.

If $100-2j=k$, where $j$ is an integer from 0 to 100, then $j=\frac{100-k}2$, so the coefficient of $x^k$ is $\binom{100}{(100-k)/2}$. Therefore, the coefficient of $x^k$ is $$\begin{cases} \binom{100}{(100-k)/2} &\text{if } k \text{ is even and } -100\le k\le 100 \\ 0 &\text{ otherwise} \end{cases}.$$

6.4 #20

\begin{align*} \binom{n-1}{k-1}\binom n{k+1}\binom{n+1}k &= \frac{(n-1)!}{(n-k)!(k-1)!}\cdot\frac{n!}{(n-k-1)!(k+1)!}\cdot\frac{(n+1)!}{(n-k+1)!k!} \\ &= \frac{(n-1)!}{(n-k-1)!k!}\cdot\frac{n!}{(n-k+1)!(k-1)!}\cdot\frac{(n+1)!}{(n-k)!(k+1)!} \\ &= \binom{n-1}k\binom n{k-1}\binom{n+1}{k+1} \end{align*}

(Note that in the middle step, the factors in the denominator are merely getting shuffled around.)

$\bigstar$ 6.4 #22

a) Suppose we want to split a set of $n$ people into three disjoint subsets, which I’ll call $A$, $B$, and $C$, such that set $A$ consists of $k$ people, set $B$ consists of $r-k$ people, and set $C$ consists of the remaining $n-r$ people. Here are two different procedures for doing this:

• We could first choose the $r$ people who will be in $A\cup B$, then choose which $k$ of those people will be in $A$.
• Or, we could first choose the $k$ people who will be in $A$, then choose the $r-k$ people who will be in $B$.

The first procedure can be accomplished in $\binom nr\binom rk$ ways, because we first choose $r$ people from a set of $n$, then choose $k$ people from among those $r$ people.

The second procedure can be accomplished in $\binom nk\binom{n-k}{r-k}$ ways, because we first choose $k$ people from a set of $n$, then choose $r-k$ people from among the $n-k$ who weren’t chosen for set A.

But both procedures accomplish the same results, so the number of ways to do the first procedure must be equal to the number of ways to do the second procedure. That is, $$\binom nr\binom rk=\binom nk\binom{n-k}{r-k}.$$

b) Both $\binom nr\binom rk$ and $\binom nk\binom{n-k}{r-k}$ can be readily shown to equal the multinomial coefficient $\binom n{k,~r-k,~n-r} = \frac{n!}{k!(r-k)!(n-r)!}$.

6.4 #28

a) Suppose there are $n$ girls and $n$ boys, and we wish to choose 2 people from among these $2n$ people. The number of ways to do this is $\binom{2n}2$. The number of ways to do this is also $2\binom n2+n^2$, because there are $\binom n2$ ways to choose two girls, $\binom n2$ ways to choose two boys, and $n^2$ ways to choose one girl and one boy. Thus $$\binom{2n}2 = 2\binom n2+n^2.$$

b) \begin{align*} 2\binom n2+n^2 &= 2\cdot\frac{n(n-1)}2 + n^2 \\ &= n(n-1+n) \\ &= \frac{(2n)(2n-1)}2 \\ &= \binom{2n}2 \end{align*}

6.4 #33

See back of book

6.5 #4

The student must make a series of seven choices, each of which can be made in 6 ways. Thus there are $6\cdot 6\cdot 6\cdot 6\cdot 6\cdot 6\cdot 6 = 6^7$ possible series of choices.

6.5 #9

a) The problem is equivalent to deciding how many bagels will go into each of eight boxes (one box per type), where the total number of bagels is 6. This is the “stars and bars” problem described in the section. There are $\binom{6+8-1}6 = \boxed{1716}$ solutions.

b) $\binom{12+8-1}{12} = \boxed{50{,}388}$

c) $\binom{24+8-1}{24} = \boxed{2{,}629{,}575}$. Don’t send someone with decision anxiety to the bagel shop.

d) If we must have at least one bagel of each kind, then we really only get to choose the last four bagels. There are $\binom{4+8-1}4 = \boxed{330}$ ways to do that.

e) At least three egg bagels means we get to choose the other nine bagels. There are $\binom{9+8-1}9 = 11{,}440$ ways to do that. However, we must exclude solutions that include at least three salty bagels.

At least three egg bagels and at least three salty bagels means we choose six bagels, which is the situation of part (a). Thus there are 1716 unwanted solutions, leaving $11440 – 1716 = \boxed{9724}$ solutions with at least three egg bagels and at most two salty bagels.

6.5 #14

$\binom{17+4-1}{17} = \boxed{1140}$

6.5 #22

$\binom{12+6-1}{12} = \boxed{6188}$

6.5 #30

$\binom{11!}{1!4!4!2!} = \boxed{34650}$

6.5 #38

a) There are $\binom{40}{10}$ ways to fill box 1, $\binom{30}{10}$ ways to fill box 2, $\binom{20}{10}$ ways to fill box 3, and $\binom{10}{10}$ ways to fill box 4, if we fill the boxes in that order. Thus the total number of outcomes is $\binom{40}{10}\binom{30}{10}\binom{20}{10}\binom{10}{10} = \frac{40!}{10!10!10!10!}$, which is the multinomial coefficient $\binom{40}{10,~10,~10,~10}$.

We can also arrive at this answer by thinking of the problem in terms of anagrams. Line the 40 issues up and place a label on each one marked with a 1, 2, 3, or 4, indicating what box that issue will go in. There are 10 labels with each number, and the order of those labels determines the outcome. The labels can be ordered in $\binom{40}{10,~10,~10,~10}$ ways.

b) There are $4!=24$ ways to relabel the four boxes, so every way to pack the issues into four identical boxes corresponds to $4!$ ways to pack the issues into four distinguishable boxes. Therefore, the number of ways to pack the issues into four identical boxes is $\frac{40!}{10!10!10!10!4!}$.

6.5 #64

First we list the distinct types of terms: $$x^4y^0z^0~~x^3y^1z^0~~x^3y^0z^1~~x^2y^2z^0~~x^2y^1z^1$$ $$x^2y^0z^2~~x^1y^3z^0~~x^1y^2z^1~~x^1y^1z^2~~x^1y^0z^3$$ $$x^0y^4z^0~~x^0y^3z^1~~x^0y^2z^2~~x^0y^1z^3~~x^0y^0z^4$$ As a check that the list is complete, there should be $\binom 62$ types of terms (corresponding to the $\binom 62$ solutions in natural numbers to the system $a_1+a_2+a_3=4$). Indeed, there are $\binom 62=15$ items in the list above.

Now the coefficients themselves are simply multinomial coefficients. Here’s the full expansion (with grouping of terms that carry the same coefficient): $$\frac{4!}{4!0!0!}(x^4+y^4+z^4)+\frac{4!}{3!1!0!}(x^3y+xy^3+x^3z+xz^3+y^3z+yz^3)+\frac{4!}{2!2!0!}(x^2y^2+x^2z^2+y^2z^2)+\frac{4!}{2!1!1!}(x^2yz+xy^2z+xyz^2),$$ or, after evaluation of the coefficients: $$x^4+y^4+z^4+4(x^3y+xy^3+x^3z+xz^3+y^3z+yz^3)+6(x^2y^2+x^2z^2+y^2z^2)+12(x^2yz+xy^2z+xyz^2).$$ As a further check, if we plug in $x=y=z=1$, we should get $(1+1+1)^4=81$… and we do!