The Ubiquitous Nature of Binomial Coefficients

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

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, Thus the answer is \(C(17,3)\). In , we illustrate this scheme with Audrey receiving\(6\) folders, Bart getting\(1\), Cecilia\(4\) and Darren7.

Example

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 lessand may be zero. So the answer is \(C(21,3)\).

Example

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

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 \[\begin{aligned}\end{aligned}\] subject to various sets of restrictions on the values of \(x_1,x_2,\dots,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)\)\(x_i> 0\)
2. \(C(543,5)\)\(x_i\ge 0\)
3. \(C(291,3)\)\(x_1,x_2,x_4,x_6>0\)\(x_3=52\)\(x_5=194\)
4. \(C(537,6)\)\(x_i > 0\)\(x_7\)\(x_7\)
5. \(C(543,6)\)\(x_i \ge 0\)\(x_7\)
6. \(C(544,6)\)\(x_i \ge 0\)

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

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.

Practice (3)

Try each one on paper first. Reveal the answer to check; verified ones can be opened in the solver for every step.

1. Suppose we are distributing \(12\) identical candy bars to four lucky children and want to determine the number of ways in which we can do this. Write a couple of sentences to describe how you would approach this problem using the methods of this section, and include a discussion of how (if at all) the methods differ between a setting where each child must get at least one candy bar and a setting where one or more children can get no candy bars.

2. Alice and Bob are discussing how to distribute \(20\) identical pens to Alice, Bob, Carlos, Dave, Xing, Yolanda, and Zori, our cast of seven recurring characters. Bob and Dave each need to get at least one pen, since they were forgetful and didn't bring any. Each of the other five could get zero pens.

   Alice approaches the problem by deciding to add five artificial pens, bringing the total number to \(25\). She says this then determines \(24\) gaps, and they need six dividers. Thus, she comes up with \(C(24,6)\) ways to distribute the pens.

   Bob claims to have gotten the same answer via a different approach. He first set aside one pen each for him and Dave, taking the total pens down to \(18\). Then each of the seven could get no pens, so he adds \(7\) artificial pens, for a total of \(25\). Again, he says this means \(24\) gaps and \(6\) dividers are required, so he concludes there are \(C(24,6)\) ways to distribute the pens.

   Is there a flaw in the reasoning of one (or both) of these arguments? If so, what flaws are there? If both arguments are correct, explain which way of solving the problem you prefer and why.

3. Consider the lattice path \(HHVHVHVVVHHV\) from \((0,0)\) to \((6,6)\). This lattice path is, in the language of , bad. Numbering the moves in the lattice path from \(1\) to \(12\), what is the first position in which the lattice path turns bad? (In the lattice path in the first paragraph of , we would say that the lattice path there turns bad at move \(9\).) Explain why the lattice path goes bad at the position you specify (and not before then).

Symbols used here

\leq,\ \geq

less/greater than or equal
Inequalities that allow equality; < and > exclude it.

n!

factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.

\binom{n}{k}

binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).

\sum_{k=1}^{n} a_k

summation
Add a_k for k = 1 up to n.

\prod_{k=1}^{n} a_k

product
Multiply a_k for k = 1 up to n.

\emptyset,\ |A|

empty set, cardinality
The set with no elements; the number of elements of A.

Questions people ask

Permutation or combination?

Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).

What is a graph in this sense?

Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.

Özüňi synla

⌨ Type ✎ Draw

Siziň rime problemaňyz

Çöl

x²√÷×π( )=∫d/dxlim[ ]sinlogeˣ

Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

_Ýaşa Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs