14.6: Sequences with Repetitions

Sequences of Subsets

Choosing a \(k\)-element subset of an \(n\)-element set is the same as splitting the set into a pair of subsets: the first subset of size \(k\) and the second subset consisting of the remaining \(n - k\) elements. So, the Subset Rule can be understood as a rule for counting the number of such splits into pairs of subsets.

We can generalize this to a way to count splits into more than two subsets. Let \(A\) be an n-element set and \(k_1, k_2,\ldots,k_m\) be nonnegative integers whose sum is \(n\). \(A(k_1, k_2, \ldots, k_m)\)-split of \(A\) is a sequence

\[\nonumber (A_1, A_2, \ldots, A_m)\]

where the \(A_i\) are disjoint subsets of \(A\) and \(|A_I| = k_i\) for \(i = 1, \ldots, m\).

To count the number of splits we take the same approach as for the Subset Rule. Namely, we map any permutation \(a_1 a_2 \ldots a_n\) of an \(n\)-element set \(A\) into a \((k_1, k_2, \ldots, k_m)\)-split by letting the 1st subset in the split be the first \(k_1\) elements of the permutation, the 2nd subset of the split be the next \(k_2\) elements, . . . , and the \(m\)th subset of the split be the final \(k_m\) elements of the permutation. This map is a \(k_1! k_2! \cdots k_m!\)-to-1 function from the \(n!\) permutations to the \((k_1, k_2, \ldots, k_m)\)- splits of \(A\), so from the Division Rule we conclude the Subset Split Rule:

Definition \(\PageIndex{1}\)

For \(n, k_1, \ldots, k_m \in \mathbb{N}\), such that \(k_1 + k_2 + \cdots + k_m = n\), define the multinomial coefficient

\[\nonumber {n choose k_1, k_2, \ldots, k_m} ::= \dfrac{n!}{k_1! k_2! \ldots k_m!}.\]

Rule 14.6.2 (Subset Split Rule). The number of \((k_1, k_2, \ldots, k_m)\)-splits of an nelement set is

\[\nonumber {n \choose k_1, \ldots, k_m}.\]

The Bookkeeper Rule

We can also generalize our count of \(n\)-bit sequences with \(k\) ones to counting sequences of \(n\) letters over an alphabet with more than two letters. For example, how many sequences can be formed by permuting the letters in the 10-letter word BOOKKEEPER?

Notice that there are 1 B, 2 O’s, 2 K’s, 3 E’s, 1 P, and 1 R in BOOKKEEPER. This leads to a straightforward bijection between permutations of BOOKKEEPER and (1,2,2,3,1,1)-splits of \(\{1, 2, \ldots, 10\}\). Namely, map a permutation to the sequence of sets of positions where each of the different letters occur.

For example, in the permutation BOOKKEEPER itself, the B is in the 1st position, the O’s occur in the 2nd and 3rd positions, K’s in 4th and 5th, the E’s in the 6th, 7th and 9th, P in the 8th, and R is in the 10th position. So BOOKKEEPER maps to

\[\nonumber (\{1\}, \{2, 3\}, \{4, 5\}, \{6, 7, 9\}, \{8\}, \{10\}).\]

From this bijection and the Subset Split Rule, we conclude that the number of ways to rearrange the letters in the word BOOKKEEPER is:

\[\nonumber \dfrac{\overbrace{10!}^{\text{total letters}}}{\underbrace{1!}_{\text{B's}} \quad \underbrace{2!}_{\text{O's}} \quad \underbrace{2!}_{\text{K's}} \quad \underbrace{3!}_{\text{E's}} \quad \underbrace{1!}_{\text{P's}} \quad \underbrace{1!}_{\text{R's}}}\]

This example generalizes directly to an exceptionally useful counting principle which we will call the

Rule 14.6.3 (Bookkeeper Rule). Let \(l_1, \ldots, l_m\) be distinct elements. The number of sequences with \(k_1\) occurrences of \(l_1\), and \(k_2\) occurrences of \(l_2\), ..., and \(k_m\) occurrences of \(l_m\) is

\[\nonumber {k_1 + k_2 + \cdots + k_m \choose k_1, \ldots, k_m}.\]

For example, suppose you are planning a 20-mile walk, which should include 5 northward miles, 5 eastward miles, 5 southward miles, and 5 westward miles. How many different walks are possible?

There is a bijection between such walks and sequences with 5 N’s, 5 E’s, 5 S’s, and 5 W’s. By the Bookkeeper Rule, the number of such sequences is:

\[\nonumber \dfrac{20!}{(5!)^4}.\]

A Word about Words

Someday you might refer to the Subset Split Rule or the Bookkeeper Rule in front of a roomful of colleagues and discover that they’re all staring back at you blankly. This is not because they’re dumb, but rather because we made up the name “Bookkeeper Rule.” However, the rule is excellent and the name is apt, so we suggest that you play through: “You know? The Bookkeeper Rule? Don’t you guys know anything?”

The Bookkeeper Rule is sometimes called the “formula for permutations with indistinguishable objects.” The size \(k\) subsets of an \(n\)-element set are sometimes called \(k\)-combinations. Other similar-sounding descriptions are “combinations with repetition, permutations with repetition, \(r\)-permutations, permutations with indistinguishable objects,” and so on. However, the counting rules we’ve taught you are sufficient to solve all these sorts of problems without knowing this jargon, so we won’t burden you with it.

The Binomial Theorem

Counting gives insight into one of the basic theorems of algebra. A binomial is a sum of two terms, such as \(a + b\). Now consider its 4th power, \((a + b)^4\).

By repeatedly using distributivity of products over sums to multiply out this 4th power expression completely, we get

\[\begin{aligned} (a+b)^4 = &\quad aaaa + aaab + aaba + aabb \\ &+ abaa + abab + abba + abbb \\ &+ baaa + baab + baba + babb \\ &+ bbaa + bbab + bbba + bbbb \end{aligned}\]

Notice that there is one term for every sequence of \(a\)’s and \(b\)’s. So there are \(2^4\) terms, and the number of terms with \(k\) copies of \(b\) and \(n-k\) copies of \(a\) is:

\[\nonumber \dfrac{n!}{k! (n-k)!} = {n \choose k}\]

by the Bookkeeper Rule. Hence, the coefficient of \(a^{n-k}b^k\) is \(n \choose k\). So for \(n = 4\), this means:

\[\nonumber (a+b)^4 = {4 \choose 0} \cdot a^4b^0 + {4 \choose 1} \cdot a^3b^1 + {4 \choose 2} \cdot a^2b^2 + {4 \choose 3} \cdot a^1b^3 + {4 \choose 4} \cdot a^0b^4\]

In general, this reasoning gives the Binomial Theorem:

Theorem \(\PageIndex{4}\)

(Binomial Theorem). For all \(n \in \mathbb{N}\) and \(a, b \in \mathbb{R}\):

\[\nonumber (a+b)^4 = \sum_{k = 0}^{n} {n \choose k} a^{n-k}b^k\]

The Binomial Theorem explains why the \(n\) choose \(k\) number is called a binomial coefficient.

This reasoning about binomials extends nicely to multinomials, which are sums of two or more terms. For example, suppose we wanted the coefficient of

\[\nonumber no^2k^2e^3pr\]

in the expansion of \((b+o+k+e+p+r)^{10}\). Each term in this expansion is a product of 10 variables where each variable is one of \(b, o, k, e, p,\) or \(r\). Now, the coefficient of \(bo^2k^2e^3pr\) is the number of those terms with exactly 1 \(b\), 2 \(o\)’s, 2 \(k\)’s, 3 \(e\)’s, 1 \(p\), and 1 \(r\). And the number of such terms is precisely the number of rearrangements of the word BOOKKEEPER:

\[\nonumber {10 \choose 1,2,2,3,1,1} = \dfrac{10!}{1!2!2!3!1!1!}\]

This reasoning extends to a general theorem:

Theorem \(\PageIndex{5}\)

(Multinomial Theorem). For all \(n \in \mathbb{N}\),

\[\nonumber (z_1 + z_2 + \cdots + z_m)^n = \sum_{k1, \ldots, k_m \in \mathbb{N} \\ k_1 + \cdots + k_m = m} {n \choose k_1, k_2, \ldots, k_m} z_1^{k_1} z_2^{k_2} \cdots z_m^{k_m}.\]