Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

πŸ”—

Section 22.3 Applications

πŸ”—

Subsection 22.3.1 Distributing/choosing indistinguishable objects

πŸ”—

Worked Example 22.3.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:
∘∘∘∘∘∘∘.
Now grab two Hickory Sticksβ„’ from the snack table to act as dividers to split the coins up into three groups. For example,
∘∣∘∘∘∘∣∘∘
means that the first child will receive one coin, the second will receive four, and the third child will receive two, whereas
∘∘∘∘∘∘∘∣∣
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.8 and Worked Example 22.2.7): how many different symbol patterns can we obtain by arranging two indistinguishable ∣ symbols and seven indistinguishable ∘ symbols? Just choose two of the nine available positions in the pattern to place the ∣ symbols. And so we have arrived at the answer C(9,2)=36.
Now, why do we not have to take into account the ordering of the children at the beginning? Let c1,c2,c3 represent the three children. Relative to that ordering of children, the symbol pattern
∘∘∘∘∘∘∘∣∣
means that the child c1 gets all seven coins, as above. But relative to the ordering c3,c2,c1, the different symbol pattern
∣∣∘∘∘∘∘∘∘
also means that child c1 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.
Just as in the last example, use n ∘ symbols to represent the indistinguishable objects and kβˆ’1 indistinguishable ∣ symbols to represent the division into k containers. So each word from the alphabet Ξ£={∘,∣} that contains exactly n ∘ symbols and kβˆ’1 ∣ symbols represents a unique way to divide the objects into the containers. The length of such a word is n+kβˆ’1, and every such word can be constructed by choosing kβˆ’1 positions for the ∣ symbols from the n+kβˆ’1 available letter positions.
πŸ”—

Worked Example 22.3.3.

πŸ”—
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
C(10+4βˆ’1,4βˆ’1)=C(13,3)=286
ways to do this.
πŸ”—

Subsection 22.3.2 Counting edges in connected graphs

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β‰₯2.
πŸ”—
πŸ”—
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.11).
  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β‰₯2 vertices is complete if and only if it has exactly C(n,2) edges (Proposition 22.3.5 in the forward direction, Statement 3 of Proposition 14.2.11 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.
Considering the contrapositive, assume that G is simple but not connected. In Activity 15.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 |E| occurs when the connected components of G are an isolated vertex v and the complete graph Knβˆ’1, in which case the number of edges is C(nβˆ’1,2) (Proposition 22.3.5 for Knβˆ’1). All other nonconnected, simple graphs will then have |E|≀C(nβˆ’1,2), as required to complete the proof by contrapositive.
<Prev^TopNext>