2.5: The Ubiquitous Nature of Binomial Coefficients

In this section, we present several combinatorial problems that can be solved by appeal to binomial coefficients, even though at first glance, they do not appear to have anything to do with sets.

Example 2.21

The office assistant is distributing supplies. In how many ways can he distribute 18 identical folders among four office employees: Audrey, Bart, Cecilia and Darren, with the additional restriction that each will receive at least one folder? Imagine the folders placed in a row. Then there are 17 gaps between them. Of these gaps, choose three and place a divider in each. Then this choice divides the folders into four non-empty sets. The first goes to Audrey, the second to Bart, etc. Thus the answer is \(C(17,3)\). In Figure 2.22, we illustrate this scheme with Audrey receiving 6 folders, Bart getting 1, Cecilia 4 and Darren 7.

Figure 2.22: Distributing Identical Objects into Distinct Cells

Example 2.23

Suppose we redo the preceding problem but drop the restriction that each of the four employees gets at least one folder. Now how many ways can the distribution be made?

Solution

The solution involves a “trick” of sorts. First, we convert the problem to one that we already know how to solve. This is accomplished by artificially inflating everyone's allocation by one. In other words, if Bart will get 7 folders, we say that he will get 8. Also, artificially inflate the number of folders by 4, one for each of the four persons. So now imagine a row of \(22 = 18 + 4\) folders. Again, choose 3 gaps. This determines a non-zero allocation for each person. The actual allocation is one less—and may be zero. So the answer is \(C(21,3)\).

Example 2.24

Again we have the same problem as before, but now we want to count the number of distributions where only Audrey and Cecilia are guaranteed to get a folder. Bart and Darren are allowed to get zero folders. Now the trick is to artificially inflate Bart and Darren's allocation, but leave the numbers for Audrey and Cecilia as is. So the answer is \(C(19,3)\).

Example 2.25

Here is a reformulation of the preceding discussion expressed in terms of integer solutions of inequalities.

We count the number of integer solutions to the inequality

\(x_1+x_2+x_3+x_4+x_5+x_6 \leq 538\)

subject to various sets of restrictions on the values of \(x_1,x_2,...,x_6\). Some of these restrictions will require that the inequality actually be an equation.

The number of integer solutions is:

1. \(C(537,5)\), when all \(x_i > 0\) and equality holds
2. \(C(543,5)\), when all \(x_i \geq 0\) and equality holds
3. \(C(291,3)\), when \(x_1,x_2,x_4,x_6 > 0\), \(x_3 = 52\), \(x_5 = 194\), and equality holds
4. \(C(537,6)\), when all \(x_i > 0\) and the inequality is strict (Imagine a new variable \(x_7\) which is the balance. Note that \(x_7\) must be positive.)
5. \(C(543,6)\), when all \(x_i \geq 0\) and the inequality is strict (Add a new variable \(x_7\) as above. Now it is the only one which is required to be positive.)
6. \(C(544,6)\), when all \(x_i \geq 0\).

A classical enumeration problem (with connections to several problems) involves counting lattice paths. A lattice path in the plane is a sequence of ordered pairs of integers:

\((m_1,n_1),(m_2,n_2),(m_3,n_3),...,(m_t,n_t)\)

so that for all \(i = 1,2,...t-1\), either

1. \(m_{i+1} = m_i + 1\) and \(n_{i+1} = n_i\), or
2. \(m_{i+1} = m_i\) and \(n_{i+1} = n_i + 1\).

In Figure 2.26, we show a lattice path from (0,0) to (13,8).

Figure 2.26: A Lattice Path

Example 2.27

The number of lattice paths from \((m,n)\) to \((p,q)\) is \(C((p-m) + (q-n),p-m)\).

To see why this formula is valid, note that a lattice path is just an \(X\)-string with \(X=\{H,V\}\), where \(H\) stands for horizontal and \(V\) stands for vertical. In this case, there are exactly \((p−m)+(q−n)\) moves, of which \(p−m\) are horizontal.

Example 2.28

Let \(n\) be a non-negative integer. Then the number of lattice paths from \((0,0)\) to \((n,n)\) which never go above the diagonal line \(y=x\) is the Catalan number

\(C(n) = \frac{1}{n+1} \dbinom{2n}{n}\).

To see that this formula holds, consider the family \(\mathcal{P}\) of all lattice paths from \((0,0)\) to \((n,n)\). A lattice path from \((0,0)\) to \((n,n)\) is just a \(\{H,V\}\)=string of length \(2n\) with exactly \(n\) \(H\)'s. So \(|\mathcal{P}| = \binom{2n}{n}\). We classify the paths in \(\mathcal{P}\) as good if they never go over the diagonal; otherwise, they are bad. A string \(s \in \mathcal{P}\) is good if the number of \(V\)'s in an initial segment of \(s\) never exceeds the number of \(H\)'s. For example, the string "\(HHVHVVHHHVHVVV\)" is a good lattice path from \((0,0)\) to \((7,7)\), while the path "\(HVHVHHVVVHVHHV\)" is bad. In the second case, note that after 9 moves, we have 5 \(V\)'s and 4 \(H\)'s.

Let \(\mathcal{G}\) and \(\mathcal{B}\) denote the family of all good and bad paths, respectively. Of course, our goal is to determine \(|\mathcal{G}|\).

Consider a path \(s \in \mathcal{B}\). Then there is a least integer \(i\) so that \(s\) has more \(V\)'s than \(H\)'s in the first \(i\) positions. By the minimality of \(i\), it is easy to see that \(i\) must be odd (otherwise, we can back up a step), and if we set \(i = 2j +1\), then in the first \(2j+1\) positions of \(s\), there are exactly \(j\) \(H\)'s and \(j+1\) \(V\)'s. The remaining \(2n-2j-1\) positions (the "tail of \(s\)") have \(n-j\) \(H\)'s and \(n-j-1\) \(V\)'s. We now transform \(s\) to a new string \(s\)' by replacing the \(H\)'s in the tail of \(s\) by \(V\)'s and the \(V\)'s in the tail of \(s\) by \(H\)'s and leaving the initial \(2j+1\) positions unchanged. For example, see Figure 2.29, where the path \(s\) is shown solid and \(s\)′ agrees with \(s\) until it crosses the line \(y=x\) and then is the dashed path. Then \(s\)′ is a string of length \(2n\) having \((n−j)+(j+1)=n+1\) \(V\)'s and \((n−j−1)+j=n−1\) \(H\)'s, so \(s\)′ is a lattice path from \((0,0)\) to \((n−1,n+1)\). Note that there are \(\binom{2n}{n-1}\) such lattice paths.

Figure 2.29: Transforming a Lattice Path

We can also observe that the transformation we've described is in fact a bijection between \(\mathcal{B}\) and \(\mathcal{P}\)', the set of lattice paths from \((0,0)\) to \((n-1, n+1)\). To see that this is true, note that every path \(s\)′ in \(\mathcal{P}\)′ must cross the line \(y=x\), so there is a first time it crosses it, say in position \(i\). Again, \(i\) must be odd, so \(i=2j+1\) and there are \(j\) \(H\)'s and \(j+1\) \(V\)'s in the first \(i\) positions of \(s\)'. Therefore the tail of \(s\)' contains \(n+1-(j+1)=n-j\) \(V\)'s and \((n-1)-j\) \(H\)'s, so interchanging \(H\)'s and \(V\)'s in the tail of \(s\)' creates a new string \(s\) that has \(n\) \(H\)'s and \(n\) \(V\)'s and thus represents a lattice path from (0,0) to \((n,n)\), but it's still a bad lattice path, as we did not adjust the first part of the path, which results in crossing the line \(y=x\) in position \(i\). Therefore, \(|\mathcal{B}| = |\mathcal{P}'|\) and thus

\(C(n) = |\mathcal{G}| = |\mathcal{P}| - |\mathcal{B}| = |\mathcal{P}| - |\mathcal{P}'| = \dbinom{2n}{n} - \dbinom{2n}{n-1} = \frac{1}{n+1}\dbinom{2n}{n}\),

after a bit of algebra.

It is worth observing that in Example 2.28, we made use of two common enumerative techniques: giving a bijection between two classes of objects, one of which is “easier” to count than the other, and counting the objects we do not wish to enumerate and deducting their number from the total.