\documentclass[12pt]{article} \addtolength{\voffset}{-.5in} \addtolength{\textheight}{1in} \addtolength{\hoffset}{-.5in} \addtolength{\textwidth}{1in} \begin{document} \begin{center} {\bf \LARGE Permutations/Combinations Solutions} \end{center} \begin{enumerate} \item Without expanding the product $$(a+b+c)(d+e+f)(p+q+r+s)(x+y+u+v+w),$$ calculate how many terms there will be. Answer: Each term in the solution is obtained by selecting exactly one of $a$, $b$, or $c$; exactly one of $d$, $e$, or $f$; etc. Because these are independent choices, use the multiplication principle: there are $3\cdot3\cdot4\cdot5=\fbox{180 \mbox{\ terms.}}$ (The question was typed incorrectly, with two $x$ terms in the last factor. This would lead to $3\cdot3\cdot4\cdot4=\fbox{144 \mbox{\ terms.}}$) \item In how many ways can ten persons be seated in a row so that a certain two of them are not next to each other? Answer: Notice that you have two mutually exclusive possibilities: cases where a certain two of them {\em are\/} next to each other, and where a certain two of them {\em are not\/} next to each other. Every case is one of these two, and the sum of those cases is $10! = 10 \cdot 9 \cdot \cdots \cdot 2 \cdot 1$. I find it easier to count the number of ways where a certain two of them {\em are} next to each other. Pick the two persons, and glue them together, front to back so they can sit on one seat. Also, remove a seat. Now you need to seat nine persons on nine seats: there are $9!$ ways to do that. Put a seat beside the two glued persons, and unglue them. For each of the $9!$ arrangements, there are two ways they can sit. Again, this is independent, so use the multiplication principle: there are $9! \cdot 2$ ways to arrange everyone. Hence the answer is $10! - 2\cdot 9! = 9!(10-2) = \fbox{$9!\cdot8$.}$ \item In how many ways can ten A's, six B's, and five C's be lined in a row so that no two B's are adjacent? Answer: This is harder than the last problem: how do you ensure that no {\em two\/} B's are adjacent? Well, forget about the B's at first. How many ways can you arrange the A's and C's in order? Imagine you have 15 slots in which you need to place ten A's and five C's. Once you {\em choose\/} slots for the five C's, every remaining slot holds an A. So, the number of orderings is simply the number of ways to place the C's. Hence there are $15 \choose 5$ ways to place the A's and C's. \newpage Now we need to place the B's. Imagine a slot between every A and C, and also a slot to the left of the first letter and to the right of the last. This gives 16 slots. If we place no more than one B per slot, and leave the rest empty, we're done. The number of ways to place the six B's in the sixteen slots is is $16 \choose 6$. Hence the answer is \fbox{${15 \choose 5}{16 \choose 6}$.} \item In how many ways can all of $n$ distinct objects be put in $k$ distinct boxes, not more than one in each box, if there are more boxes than things? Answer: Since there are more boxes than things, $k-n$ boxes will be empty and $n$ boxes will be full. First choose which boxes: there are $k \choose n$ ways to choose the full boxes. For each choice, you have $n$ boxes in which to place $n$ objects, so there are $_nP_n=n!$ ways to place the objects. Hence your answer is \fbox{${k \choose n}n!$.} \item There are nine different books on a shelf; four are red and five are green. In how many different orders is it possible to arrange the books on the shelf if \begin{enumerate} \item there are no restrictions; \item the red books must be together and the green books together; \item the red books must be together whereas the green books may be, but need not be, together; \item the colors must alternate, i.e., no two books of the same color may be adjacent? \end{enumerate} Answer: Assume that red books are green books are not identical; otherwise the question is too easy. \begin{enumerate} \item There are $9!$ ways to place the books with no restrictions. \item There are $4!$ ways to arrange the red books, $5!$ ways to arrange the green books, and 2 ways to arrange them on a shelf (green-red or red-green), for a total of \fbox{$4! \cdot 5! \cdot 2$ ways.} \item Glue all of the red books together, as above, into a huge red book. Now you have six books to place on the shelf, for $6!$ ways. Unglue the red books --- there are $4!$ ways to arrange the red books in that location (relative to the green books). So there are \fbox{$6! \cdot 4!$ ways.} \item If no two books of the same color may touch, the row must start and end with green (since there is one more green book). So you have five slots for green books and four for red: this gives you $\fbox{$5! \cdot 4!$ ways.}$ \end{enumerate} \item How many of the first 10,000 positive integers have distinct digits? Answer: Break this into five cases, corresponding to one-digit, two-digit, \ldots, five-digit numbers. All of the 9 positive one digit numbers have distinct digits. $9 \cdot 9=81$ of the two digit numbers do. (Pick the first digit from 1, 2, \ldots, 9. Then you have 9 choices for the second digit --- anything but the first, plus zero.) $9 \cdot 9 \cdot 8 = 648$ of the three-digit numbers do. $9 \cdot 9 \cdot 8 \cdot 7 = 4536$ of the four-digit numbers do. 10000 does not have distinct digits. Hence your answer is $9 + 81 + 648 + 4536 = \fbox{5274 \mbox{\ integers}.}$ \item You have a box containing four red socks, three blue socks, and two green socks. You pick out three socks at random; what is the most likely outcome? Answer: You need to go through the possibilities: how many ways can you pick 2 reds and a blue? ${4 \choose 2}{3 \choose 1}{2 \choose 0}=6 \cdot 3 = 18$ ways. Two blues and a green? ${4 \choose 0}{3 \choose 2}{2 \choose 1} = 3 \cdot 2 = 6$ ways. In general, you have ${4 \choose a}{3 \choose b}{2 \choose c}$, where $a+b+c=3$. Notice that the best answer must have $a \geq b \geq c$, since if $a \geq b$ then ${a \choose k} \geq {b \choose k}$, and you're trying to get the largest number. (There are more ways to pick 2 out of 4 than there are ways to pick 2 out of 3, so if you're going to pick two socks of one color, pick two red socks, not two blue or green socks.) This narrows things down nicely. \begin{tabular}{|c|c|c|c|} \hline $a$ & $b$ & $c$ & combinations \\ \hline 3 & 0 & 0 & 4 \\ \hline 2 & 1 & 0 & $6 \cdot 3 = 18$ \\ \hline 1 & 1 & 1 & $4 \cdot 3 \cdot 2 = 24$ \\ \hline \end{tabular} Hence your answer is that the most likely result is \fbox{one of each.} \item If 9 students are separated onto three ARML relay teams, what is the probability that a specific two of them are on the same team? What is the probability that a specific three of them are completely separated, one on each team? Answer: For both of these questions, it doesn't matter {\em which\/} team the students are on (team 1, team 2, team 3), only the division of students into teams. If we cared about team numbers, the number of ways of breaking up the teams is ${9 \choose 3}{6 \choose 3}{3 \choose 3}={9 \choose 3}{6 \choose 3}{3 \choose 3}$. (Choose 3 students from 9 for team one, 3 from the remaining 6 for team two, and all of the remaining 3 for team three.) But since we don't care about the order, we divide by 3!. Hence the denominator for both of these problems is $$\frac{{9 \choose 3}{6 \choose 3}}{3!}.$$ So place the two students on team 1. There are 7 students left, and you need one more on first team, so you have $7 \choose 1$ ways to pick. For each way you pick, you have 6 students left. Pick 3 for the second team. There are $6 \choose 3$ ways to do that, and once you do, the last team is composed of the remaining 3 students. There are ${3 \choose 3}=1$ ways to pick the last team. BUT, the second and third teams are interchangable: we're just grouping students into two groups of three. For each way you picked three students to make the second team, you could have picked the other three students and gotten the same distribution of students onto teams. So you need to divide by 2. Hence the the numerator of the first answer is \fbox{$\frac{1}{2}{7 \choose 1}{6 \choose 3}$.} Divide by the denominator above to get your answer. Another example: if you are dividing six people onto three teams, you might think the answer is ${6 \choose 2}{4 \choose 2}{2 \choose 2}$ --- and that {\em is\/} the answer, if the teams are numbered. But if the teams are not numbered, then order doesn't matter, so 12-34-56 is the same as 12-56-34, 34-12-56, 34-56-12, 56-12-34, and 56-34-12. Consequently you need to divide by $3!=6$ to get the right answer, making the right answer $\frac{1}{3!}{6 \choose 2}{4 \choose 2}{2 \choose 2}$ Another way to calculate the answer to this problem: Once you have the first team set (with the two students who have to be together, and the additional person), identify one student. Put two of the remaining five on that student's team, and the remaining three on the other team. This gives \fbox{${7 \choose 1}{5 \choose 2}$,} which is the same numerator as given above. If three need to be completely separated, the problem is easier. Place one on each team. You now have three distinct teams --- the team with the first student, the team with the second student, the team with the third student. (This means that order matters.) To place the remaining six students, you need to place 2 on each team. Hence the second numerator is \fbox{${6 \choose 2}{4 \choose 2}{2 \choose 2}$}, and again you need to put thise over the denominator above. \item A man has a large supply of wooden regular tetrahedra (a solid with four equilateral triangles as faces), all the same size. If he paints each triangular face in one of four colors, how many different painted tetrahedra can he make, allowing all possible combinations of colors? (Two colorings are the same if one tetrahedron could be rotated to match the other's coloring.) Answer: There are only a few possibilities: With one color, you can have 4 sides of the same color (4). With two colors, you can have three of one and one of another (3-1) or you can have two and two (2-2). With three colors, you can only have two, one, and one (2-1-1). With four colors, you need to have one of each color (1-1-1-1). (4) There are 4 ways to paint the tetrahedron a solid color, if you have four colors. (3-1) There are $4 \cdot 3=12$ ways to paint the 3-1 case (the colors are not interchangable). (2-2) There are ${4 \choose 2}=6$ ways to paint the 2-2 case (the colors are interchangable). (2-1-1) There are ${4 \choose 1}{3 \choose 2}$ ways to pick the three colors: 4 ways to pick the color that colors two sides, and three ways to pick the last two colors, for a total of 12. Paint the two sides the same color (it doesn't matter which two sides --- all ways you can paint two sides are the same). Place one on the bottom, so you can't see it. Looking down from above, there are two different ways to place the last two colors. That means there are a total of $12\cdot 2=24$ ways to paint the 2-1-1 case. (1-1-1-1) Paint one of the sides color 1, and place that on the bottom (so you can't even see it). Now you need to paint the last three sides colors 2, 3, and 4. Looking down from above, you could paint these three colors clockwise or counterclockwise. 234, 342, and 423 are all the same, and 432, 324, and 243 are all the same. This gives two possibilities. Our grand total is $4 + 12 + 6 + 2 + 24 = \fbox{$48$ colorings.}$ \item A child has a set of 96 distinct blocks. Each block is one of 2 materials ({\em plastic, wood}), 3 sizes ({\em small, medium, large}), 4 colors ({\em blue, green, red, yellow}), and 4 shapes ({\em circle, hexagon, square, triangle}). How many blocks in the set are different from the ``{\em plastic medium red circle}'' in exactly two ways? (The ``{\em wood medium red square}'' is such a block). Answer: First, pick the two ways that the block is different. Call the properties A, B, C, and D. (A is material, B is size, C is color, and D is shape.) There are ${4 \choose 2} = 6$ ways to pick: AB, AC, AD, BC, BD, and CD. Suppose the two properties were A and B. Since there are only 2 materials, you must switch to the other, and since there are 3 sizes, you have two other sizes to choose from. Thus the blocks can differ in those two properies in $1 \cdot 2=2$ ways. In general, for whichever two properties you choose, subtract one from the number of possibilities of each, and multiply together to get the number of blocks: \begin{tabular}{|c|c|} \hline AB & $1 \cdot 2 = 2$\\ \hline AC & $1 \cdot 3 = 3$\\ \hline AD & $1 \cdot 3 = 3$\\ \hline BC & $2 \cdot 3 = 6$\\ \hline BD & $2 \cdot 3 = 6$\\ \hline CD & $3 \cdot 3 = 9$\\ \hline \end{tabular} So your answer is $2+3+3+6+6+9=\fbox{29 blocks.}$ \item How many differently colored blocks of a fixed cubical shape can be made if six colors are available, and a block is to have a different color on each of its six faces? Answer: You need to find a way to count colorings without counting anything twice. Take one of the colored sides, say the side that's color 1, and put it on the bottom. Since every cube has a side of that color, we can count the colorings of the remaining five sides. There are 5 other colors that could be on the top --- $5 \choose 1$ to be precise. That leaves 4 colors. These can be arranged in $4!$ ways around the cube, but each coloring of the four sides is equivalent to three other colorings (for example, 3456, 4563, 5634, 6345 are all the same). Since you have groups of four colorings, there are $\frac{4!}{4}=3!=6$ ways to color the sides. This gives a grand total of $6 \cdot 5 = \fbox{30 ways to color the cube.}$ \item Prove that ${n \choose r} = {n-1 \choose r} + {n-1 \choose r-1}$, both algebraically and with a non-algebraic explanation. Answer: Non-algebraically, pick one element and call it the ``last'' element. The number of ways of picking $r$ things from $n$ is the number of ways of picking $r-1$ things from $n-1$ and also picking the last element, {\em plus\/} the number of ways of picking $r$ things from $n-1$ and not picking the last element. In both cases, you end up with $r$ elements. From another perspective, this breaks the original number into two numbers --- those that do, and those that don't, include a specific element. Algebraically, $${n-1 \choose r}+{n-1 \choose r-1}$$ $$\frac{(n-1)!}{r!(n-r-1)!} + \frac{(n-1)!}{(r-1)!(n-r)!}$$ $$\frac{(n-1)!}{r\cdot (r-1)!(n-r-1)!} + \frac{(n-1)!}{(n-r)(r-1)!(n-r-1)!}$$ $$\frac{(n-1)!}{(r-1)!(n-r-1)!}\left(\frac{1}{r} + \frac{1}{n-r}\right)$$ $$\frac{(n-1)!}{(r-1)!(n-r-1)!}\left(\frac{(n-r)+r}{(r)(n-r)}\right)$$ $$\frac{(n-1)!}{(r-1)!(n-r-1)!}\left(\frac{n}{(r)(n-r)}\right)$$ $$\frac{n!}{r!(n-r)!}$$ $$n \choose r$$ \item Determine a closed form for $\sum_{k=0}^n {n \choose k}$, and prove that your closed form is correct. (For example, what is ${6 \choose 0} + {6 \choose 1} + {6 \choose 2} + {6 \choose 3} + {6 \choose 4} + {6 \choose 5} + {6 \choose 6}$?) Answer: $\sum_{k=0}^n {n \choose k} = 2^n$. You can prove this using mathematical induction: our theorem holds for $n=0$ since ${0 \choose 0}=1=2^0$. Now assume our theorem works for $n$, and prove it works for $n+1$. Specifically, assume $\sum_{k=0}^n {n \choose k} = 2^n$, and prove that $\sum_{k=0}^{n+1} {n+1 \choose k} = 2^{n+1}$. $$\sum_{k=0}^{n+1} {n+1 \choose k}$$ By the previous problem, $$ = \sum_{k=0}^{n+1}\left({n \choose k}+{n \choose k-1}\right)$$ By the commutative property, $$ = \sum_{k=0}^{n+1}{n \choose k}+\sum_{k=0}^{n+1}{n \choose k-1}$$ Since you can't choose more than you have, or less than zero, we can remove $n \choose n+1$ from the first sum and $n \choose -1$ from the second: $$ = \sum_{k=0}^{n}{n \choose k}+\sum_{k=1}^{n+1}{n \choose k-1}$$ Shifting the index of the second sum, $$ = \sum_{k=0}^{n}{n \choose k}+\sum_{k=0}^{n}{n \choose k}$$ By our assumption that the theorem holds for $n$, $$ = 2^n + 2^n$$ $$ = 2\cdot2^n$$ $$ = 2^{n+1}$$ This property can be seen in Pascal's triangle: the row sums are the powers of 2. \end{enumerate} \end{document}