22.3: Applications

Distributing/choosing indistinguishable objects

Example \(\PageIndex{1}\)

How many ways are there to distribute seven coins amongst three children? (Assume the coins are indistinguishable. But children are obviously distinguishable.)

Solution

Here is one scheme by which we can decide how many coins each child will get. Line the children up in some order. (There is no need to count the number of ways to do this — see the end of the solution.) Also lay out the coins in a line:

\begin{equation*} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \text{.} \end{equation*}
Now grab two Hickory Sticks™ from the snack table to act as dividers to split the coins up into three groups. For example,

\begin{equation*} \mathord{\circ} \mathord{\mid} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\mid} \mathord{\circ} \mathord{\circ} \end{equation*}
means that the first child will receive one coin, the second will receive four, and the third child will receive two, whereas

\begin{equation*} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\mid} \mathord{\mid} \end{equation*}
means that the first child gets all seven coins.

We are now back to the red bottle, blue bottle problem (see Worked Example 21.3.4 and Worked Example 22.2.2): how many different symbol patterns can we obtain by arranging two indistinguishable \(\mathord{\mid}\) symbols and seven indistinguishable \(\mathord{\circ}\) symbols? Just choose two of the nine available positions in the pattern to place the \(\mathord{\mid}\) symbols. And so we have arrived at the answer \(C(9, 2) = 36\text{.}\)

Now, why do we not have to take into account the ordering of the children at the beginning? Let \(c_1, c_2, c_3\) represent the three children. Relative to that ordering of children, the symbol pattern

\begin{equation*} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\mid} \mathord{\mid} \end{equation*}
means that the child \(c_1\) gets all seven coins, as above. But relative to the ordering \(c_3,c_2,c_1\text{,}\) the different symbol pattern

\begin{equation*} \mathord{\mid} \mathord{\mid} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \mathord{\circ} \end{equation*}
also means that child \(c_1\) gets all seven coins, which is the same result. So if we allow both symbol patterns and orderings of children to vary, we will end up over-counting.

Theorem \(\PageIndex{1}\)

There are \(C(n+k-1, k-1)\) ways to distribute \(n\) indistinguishable objects amongst \(k\) distinguishable containers.

Proof.

Just as in the last example, use \(n\) \(\mathord{\circ}\) symbols to represent the indistinguishable objects and \(k-1\) indistinguishable \(\mathord{\mid}\) symbols to represent the division into \(k\) containers. So each word from the alphabet \(\Sigma=\{\mathord{\circ},\mathord{\mid}\}\) that contains exactly \(n\) \(\mathord{\circ}\) symbols and \(k-1\) \(\mathord{\mid}\) symbols represents a unique way to divide the objects into the containers. The length of such a word is \(n+k-1\text{,}\) and every such word can be constructed by choosing \(k-1\) positions for the \(\mathord{\mid}\) symbols from the \(n+k-1\) available letter positions.

Example \(\PageIndex{2}\)

Your professor throws a discrete math party, but only nine students show up (sad face). The professor sends one of the students to the corner store to get cans of soda pop for everyone. The student decides to get a mix of four different varieties. How many possible mixes of soda varieties can the student come back with? (Assume that the cans are indistinguishable except by variety, and that the store has more than ten cans of each variety available.)

Solution

Here is one scheme by which the student can decide how to choose ten cans in some combination of soda varieties. Make four boxes labelled by soda variety. Have the student choose the soda cans while blindfolded, but has the store clerk place each can in the appropriate box as the cans are chosen (a permissible assumption, since it has no bearing on the outcome). In this way, we may assume that the cans are initially indistinguishable and remain so until they are placed in the appropriate box, at which time they magically become the variety specified by the box's label. The previous theorem now tells us that there are

\begin{equation*} C(10+4-1, 4-1) = C(13, 3) = 286 \end{equation*}
ways to do this.

Corollary \(\PageIndex{1}\)

There are \(C(n+k-1, k-1)\) ways to choose \(n\) objects from amongst \(k\) types of object, where objects are indistinguishable except by type, and there are at least \(n\) objects of each type available.

Proof Idea.

Appeal to Theorem \(\PageIndex{1}\) exactly as in Worked Example \(\PageIndex{2}\).

Counting edges in connected graphs

Proposition \(\PageIndex{1}\): Edges in a complete graph.

For \(n \ge 2\text{,}\) the complete graph with \(n\) vertices has \(C(n, 2)\) edges.

Proof.

A complete graph has no loops and exactly one edge between each pair of vertices. So to count the edges we can just count the number of pairs of vertices, which is \(C(n, 2)\) for \(n \ge 2\text{.}\)

Let's summarize what we know about the number of edges in an arbitrary connected graph.

1. A connected graph with \(n\) vertices has at least \(n - 1\) edges (Theorem 15.3.1).
2. A connected graph with \(n\) vertices is a tree if and only if it has exactly \(n - 1\) edges (Theorem 16.3.1).
3. A simple graph with \(n \ge 2\) vertices is complete if and only if it has exactly \(C(n, 2)\) edges (Proposition \(\PageIndex{1}\) in the forward direction, Statement 4 of Proposition 14.2.1 in the reverse direction).

The first fact tells us the minimum number of edges a connected graph must have, but it does not guarantee that a graph with that many edges must be connected, even if the graph is simple. The following is something of a converse to this fact, as it does provide such a guarantee: it tells use how many edges a (simple) graph must have before we can be certain that it is connected.

Theorem \(\PageIndex{1}\)

If \(G = (V,E)\) is a simple graph such that \(\vert V \vert = n\) and \(\vert E \vert \gt C(n-1, 2)\text{,}\) then \(G\) is connected.

Proof Idea.

Considering the contrapositive, assume that \(G\) is simple but not connected. In Activity 15.5.6, we discovered that such a \(G\) will be maximal when it has exactly two connected components, each of which is a complete graph. Among graphs with those two characteristics (and still \(n\) vertices), the largest possible value for \(\vert E \vert\) occurs when the connected components of \(G\) are an isolated vertex \(v\) and the complete graph \(K_{n-1}\text{,}\) in which case the number of edges is \(C(n-1, 2)\) (Proposition \(\PageIndex{1}\) for \(K_{n-1}\)). All other nonconnected, simple graphs will then have \(\vert E \vert \le C(n-1, 2)\text{,}\) as required to complete the proof by contrapositive.