# 1.E: What is Combinatorics? (Exercises)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\(\rightarrow\) 1. Remember that we can write \(n\) as a sum of \(n\) ones. How many plus signs do we use? In how many ways may we write \(n\) as a sum of a list of \(k\) positive numbers? Such a list is called a composition of \(n\) into \(k\) parts.

2. In Problem 1 we defined a composition of \(n\) into \(k\) parts. What is the total number of compositions of \(n\) (into any number of parts)?

\(\cdot\) 3. Write down a list of all 16 zero-one sequences of length four starting with 0000 in such a way that each entry differs from the previous one by changing just one digit. This is called a Gray Code. That is, a *Gray Code* for 0-1 sequences of length \(n\) is a list of the sequences so that each entry differs from the previous one in exactly one place. Can you describe how to get a Gray Code for 0-1 sequences of length five from the one you found for sequences of length 4? Can you describe how to prove that there is a Gray code for sequences of length \(n\)?

(\rightarrow\) 4. Use the idea of a Gray Code from Problem 3 to prove bijectively that the number of even-sized subsets of an \(n\)-element set equals the number of odd-sized subsets of an \(n\)-element set.

(\rightarrow\) 5. A list of parentheses is said to be balanced if there are the same number of left parentheses as right, and as we count from left to right we always find at least as many left parentheses as right parentheses. For example, (((()()))()) is balanced and ((()) and (()()))(() are not. How many balanced lists of \(n\) left and \(n\) right parentheses are there?

* 6. Suppose we plan to put six distinct computers in a network as shown in Figure 1.9. The lines show which computers can communicate directly with which others. Consider two ways of assigning computers to the nodes of the network different if there are two computers that communicate directly in one assignment and that don’t communicate directly in the other. In how many different ways can we assign computers to the network?

*Figure 1.9: A computer network.*

(\rightarrow\) 7. In a circular ice cream dish we are going to put four scoops of ice cream of four distinct flavors chosen from among twelve flavors. Assuming we place four scoops of the same size as if they were at the corners of a square, and recognizing that moving the dish doesn’t change the way in which we have put the ice cream into the dish, in how many ways may we choose the ice cream and put it into the dish?

(\rightarrow\) 8. In as many ways as you can, show that \(\binom{n}{k} \binom{n-k}{m} = \binom{n}{m} \binom{n-m}{k}\).

(\rightarrow\) 9. A tennis club has 4n members. To specify a doubles match, we choose two teams of two people. In how many ways may we arrange the members into doubles matches so that each player is in one doubles match? In how many ways may we do it if we specify in addition who serves first on each team?

10. A town has \(n\) streetlights running along the north side of Main Street. The poles on which they are mounted need to be painted so that they do not rust. In how many ways may they be painted with red, white, blue, and green if an even number of them are to be painted green?

* 11. We have \(n\) identical ping-pong balls. In how many ways may we paint them red, white, blue, and green?

* 12. We have \(n\) identical ping-pong balls. In how many ways may we paint them red, white, blue, and green if we use green paint on an even number of them?