3. Applications of combinations and combinations with repetition#

The previous notes introduced strings, permutations, and combinations. The central modeling questions were whether order matters and whether a selection may repeat an object. In these notes we use those questions to count lattice paths and repeated-letter anagrams. We then develop the remaining basic model: unordered selections in which repetition is allowed.

After studying these notes, you will be able to do the following.

Define a northeast lattice path.
Encode a two- or three-dimensional lattice path as a string of steps.
Count arrangements with repeated symbols using multinomial coefficients.
Recognize an unordered selection with repetition as a multiset.
Use stars and bars to count multisets and nonnegative integer solutions.
Combine several counting models in a single problem.

3.1 Choosing the correct model#

We begin with a selection of objects from available types. Before using a formula, we must decide what one outcome records.

Order matters?	Repetition allowed?	Standard model
Yes	Yes	Strings
Yes	No	Permutations
No	No	Combinations
No	Yes	Multisets

The previous notes established the first three formulas. Stars and bars will establish the last formula later in these notes. In every row, is the number of available types and is the total number selected. For the rows without repetition, we must also have .

The words used in a problem do not determine the row. The word ``choose,’’ for example, does not automatically mean that order is irrelevant. Choosing a president and then a vice president creates an ordered pair of people, while choosing two ordinary committee members creates an unordered subset.

Warning (The outcome comes first)#

A formula should not come from keywords alone. We first state what information determines one outcome. Next, we decide whether changing the order or repeating an object changes that outcome.

3.2 Lattice paths in the plane#

An integer lattice point in the plane is a point whose coordinates are integers. For nonnegative integers and , a northeast lattice path from to uses only the two unit steps Thus moves one unit to the right and moves one unit up.

Every such path must use exactly right steps and exactly up steps. It therefore has steps altogether. Reading the steps from start to finish turns the path into a string containing copies of and copies of .

Figure 1 shows one path together with the step string that records it.

A rectangular grid with a blue path from (0,0) to (5,3). The path has step string RURRURRU. — Figure 1: A path from the origin to the point (5,3) and its step string.#

The correspondence between paths and step strings goes in both directions. A path determines its string by recording its steps, and a string with copies of and copies of determines a unique path by following those instructions from the origin. This is a bijection.

Theorem 1 (Northeast lattice paths)#

For nonnegative integers and , the number of northeast lattice paths from to is

Proof#

Each path determines a unique length- string containing copies of and copies of . We choose the positions occupied by the right steps. The remaining positions must contain up steps, so there are paths. Equivalently, we may choose the positions occupied by the up steps, giving .

Example 2 (Paths from to )#

A path from to must contain five right steps and three up steps. It has eight steps in total, so the number of paths is The path in Figure 1 corresponds to the string RURRURRU. Its five copies of R and three copies of U verify that it has the required endpoint.

The same idea counts paths between two other lattice points. To move from to using only right and up steps, we need right steps and up steps. Such a path exists only when and .

Problem (Practice)#

How many northeast lattice paths go from to ? What are the number of right steps, the number of up steps, and the total number of steps?

3.3 Three-dimensional paths and multinomial coefficients#

The string model extends naturally to higher dimensions. In three dimensions, the positive coordinate steps are

We begin with a concrete path and build its step string one kind of step at a time.

Example 3 (Filling the positions of a three-dimensional path)#

How many positive-coordinate lattice paths go from to ?

Solution: Throughout this example, we display X steps in blue, Y steps in orange, and Z steps in purple. Every path has six steps: two X steps, three Y steps, and one Z step. Before making any choices, picture six empty positions:

This is a multistep operation. In the first stage, we choose which two of the six positions will contain X. There are choices. For example, one possible first-stage choice is

This is only a partial string, not yet a complete path.

In the second stage, we choose three of the four positions that are still empty and put Y in them. Thus this stage has choices. Continuing the particular first-stage choice displayed above, one possibility is

One position remains, so it must contain Z:

If we record this forced final stage as a choice, it has possible outcome. Every complete path arises from exactly one choice at each stage, so the product rule gives

For a general three-dimensional endpoint , there are positions. The same three stages contribute The final factor always equals , because . This is exactly what we should expect. The last stage is not a new choice among several possibilities: after we choose the and positions, we fill every remaining position with .

The same position-filling procedure works for any number of symbol types. A length- string may need to contain copies of symbol , copies of symbol , and so on through copies of symbol , where We start with empty positions. First, we choose the positions for symbol . Next, we choose the positions for symbol , but only from the positions still empty. After those two stages, positions remain. We continue in this way. At the final stage, we choose the positions for symbol from the positions still empty. This final binomial coefficient equals , as it should: the sum condition says that exactly positions remain, and we fill all of them with the last symbol.

Definition 4 (Multinomial coefficient)#

For and nonnegative integers whose sum is , the multinomial coefficient is the number of strings of length containing exactly copies of symbol for each . It is also commonly written as .

Theorem 5 (Formula for a multinomial coefficient)#

For and nonnegative integers satisfying ,

Proof#

The stages described above have choices, respectively. The choice at one stage determines which positions are available at the next, but the number of choices at the next stage is always the displayed binomial coefficient. Therefore the product rule gives The crossed-out in the denominator of the first factor cancels with the same factorial in the numerator of the second. Next, the two copies of cancel. The same cancellation continues from one factor to the next through every intermediate factorial. The only remaining factorial of this form is in the denominator, and .

To apply this formula to paths, we write for the number of steps in coordinate direction . Thus, in dimensions, a positive-coordinate path from the origin to has steps, and the number of such paths is

3.4 Anagrams with repeated letters#

An anagram of a word is a rearrangement of all of its letters. If all letters are distinct, there are anagrams of a word of length . Repeated letters make some of those arrangements indistinguishable.

Theorem 6 (Anagrams of a word with repeated letters)#

If a nonempty word of length has distinct kinds of letters and letter type occurs times, where then the number of anagrams is

Proof#

An anagram is exactly a string with a prescribed number of copies of each letter, so the result follows from Theorem 5. Here is a second explanation of the denominator. Temporarily distinguish equal letters with labels. For instance, we write the three copies of as . The labeled letters have arrangements. After we erase the labels, each unlabeled anagram appears times, because we can permute the labels within every repeated letter type independently. The division principle gives the stated quotient.

Example 7 (Anagrams of BANANA)#

The word BANANA has six letters: three copies of A, two copies of N, and one copy of B. Therefore it has distinct anagrams.

We can also choose the three positions for A, then two of the three remaining positions for N; the last position contains B. This gives

Warning 8 (Divide only for genuinely interchangeable copies)#

If two people, colors, or roles are distinct in the outcome, exchanging them does not create the same outcome. A factorial belongs in the denominator only when permuting the corresponding labeled copies leaves the underlying outcome unchanged.

3.5 Combinations with repetition#

A doughnut shop offers ten types of doughnuts and has an unlimited supply of each type. How many ways are there to buy six doughnuts?

An outcome is not a string of six successive purchases. For example, buying a glazed doughnut and then a chocolate doughnut gives the same purchase as buying the chocolate doughnut first and the glazed doughnut second. Order does not matter. On the other hand, the buyer may purchase several doughnuts of one type, so the model allows repetition.

This is an unordered selection with repetition, also called a multiset. One way to record the purchase is by a multiplicity vector where is the number of doughnuts of type . The entries must satisfy Thus the doughnut problem is equivalent to counting nonnegative integer solutions of an equation.

3.5.1 The stars-and-bars encoding#

We encode a nonnegative solution of using stars and bars. The stars are the selected objects, and the bars separate the types. Reading from left to right,

is the number of stars before the first bar;
is the number of stars between bars and ;
is the number of stars after the last bar.

For example, when and , we encode the vector by

Figure 2 displays the same encoding with the four groups of stars separated visually.

Seven blue stars are split by three vertical bars into groups of two, one, two, and two. — Figure 2: The stars-and-bars encoding of the vector (2,1,2,2).#

Bars may be adjacent, because we may select a type zero times. A bar may also occur first or last, corresponding respectively to or . These are valid encodings, not exceptional cases.

Theorem 9 (Stars and bars)#

For integers and , the number of nonnegative integer solutions to is

Proof#

Every solution determines one string containing stars and bars, and every such string determines one solution by counting the stars in its groups. These two operations undo one another, so this is a bijection.

The string has positions. We choose the positions occupied by bars; all remaining positions contain stars. This gives strings. Equivalently, choosing the star positions gives .

Corollary 10 (Combinations with repetition)#

If types are available and we select objects, with order irrelevant and repetition allowed, then the number of selections is

Example 11 (Buying six doughnuts)#

Let us return to the shop with ten types of doughnuts. The multiplicities satisfy Stars and bars uses six stars and nine bars, so the number of purchases is

The value would count ordered strings of six choices and would count the same purchase many times. The value would forbid buying two doughnuts of the same type. Neither model describes the stated outcome.

Remark 12 (If every variable must be positive)#

When for every , we first give one object to each type and write . Then and When , the number of positive integer solutions is therefore If , there are no positive solutions.

Problem (Practice)#

How many nonnegative integer solutions are there to Which stars-and-bars string encodes the particular solution ?

3.6 Combining models: nonadjacent letters in ARKANSAS#

We finish with a problem that uses repeated-letter anagrams, the product rule, and an ordinary combination.

Example 13 (ARKANSAS with no adjacent copies of A)#

How many anagrams of ARKANSAS have no two copies of A adjacent?

Solution: The word contains three copies of A, two copies of S, and one copy each of R, K, and N.

We first remove the three copies of A. Next, we arrange the five remaining letters RKNSS. Because the two copies of S are identical, the number of base arrangements is

Every base arrangement has six gaps: before the first letter, between each pair of consecutive letters, and after the last letter. To prevent adjacent copies of A, we place at most one A in each gap. We must choose three distinct gaps from the six available gaps, which can be done in ways.

By the product rule, the requested number of anagrams is

This construction counts each valid anagram exactly once. Given a valid anagram, deleting its three copies of A recovers one unique base arrangement of RKNSS; the former locations of the copies of A recover the three chosen gaps.

Figure 3 illustrates the gap construction for one base arrangement.

The base arrangement RSKNS has six gaps. Copies of A occupy the first, third, and sixth gaps, producing ARSAKNSA. — Figure 3: Choosing three gaps around one arrangement of RKNSS.#

There is a useful consistency check. If we allowed adjacent copies of A, stars and bars would distribute the three indistinguishable copies among the six gaps with repetition. This gives distributions. Thus the total number of unrestricted anagrams would be Direct use of the multinomial formula gives which agrees. When we forbid adjacency, the gap selection changes from a combination with repetition to an ordinary combination without repetition.

3.7 A counting checklist#

The main ideas in these notes are different views of the same objects. A lattice path is a step string; an anagram is a string with prescribed symbol multiplicities; a multiset is a multiplicity vector; and a multiplicity vector is a stars-and-bars string.

When solving a new problem, we can organize the model with the following checklist.

What information determines one outcome?
Does order matter, and does the model allow repetition?
Which familiar encoding fits: a string, subset, multiset, integer vector, or lattice path?
Why is the encoding reversible, or why is any overcounting factor constant?
Which formula corresponds to that model?

The formulas developed here are

3.8 Further reading#

The course resources page links to the books used as references for these notes. Applied Combinatorics, Sections 2.5 and 2.7, covers lattice paths and multinomial coefficients. Counting Rocks!, Sections 3.5.1, 4.1, 4.5, and 4.6, covers multisets, stars and bars, lattice paths, and repeated-letter anagrams.