Repeated Objects and Multinomial Counting, introduction to probability lesson

A routing board shows five letter tiles, two N, two E and one S. If the five tiles were all different they could be ordered in $5! = 120$ ways, but swapping the two N tiles leaves the board looking exactly the same. So how many different strings can the board actually show? This lesson answers that question with the multinomial coefficient, which divides out exactly the rearrangements that the record cannot see. The same coefficient then counts the ways to split distinct objects into named groups and gives the coefficients in a power of a sum.

Key terms

Indistinguishable objects

Definition Objects in a counting problem are indistinguishable when the recorded outcome does not tell them apart, so that exchanging any two of them leaves the record unchanged. This is a property of what the outcome records, not of the physical objects. Two tiles printed with the same letter are indistinguishable for a board that shows only letters, and distinguishable for a record that also lists each tile’s serial number.

In plain words Before counting, decide what one outcome records. Swapping two objects that the record cannot tell apart does not produce a new outcome, so it must not be counted as one.

Example On the routing board, mark the repeated tiles temporarily as $N_1$ , $N_2$ , $E_1$ and $E_2$ , next to the single $S$ . The five marked tiles have $5! = 120$ orders. The visible string NESEN comes from exactly four of them, namely $N_1E_1SE_2N_2$ , $N_2E_1SE_2N_1$ , $N_1E_2SE_1N_2$ and $N_2E_2SE_1N_1$ , because the N marks can be placed in $2!$ ways and the E marks in $2!$ ways. Every visible string comes from four marked orders in the same way, so the board can show $120/4 = 30$ different strings.

Multiset permutation

Definition Suppose a collection of $n$ objects has $k$ types, with $n_i$ objects of type $i$ , where each $n_i$ is a nonnegative integer and

n_1 + n_2 + \cdots + n_k = n.

Objects of the same type are indistinguishable, and objects of different types are distinguishable. A multiset permutation of the collection is a sequence of length $n$ in which type $i$ appears exactly $n_i$ times. The number of multiset permutations is

\frac{n!}{n_1!\, n_2! \cdots n_k!}.

To see why, mark all $n$ objects so that they become distinct, which gives $n!$ marked arrangements. The marked arrangements behind one visible sequence are exactly those obtained by permuting the marks within each type, and there are $n_1!\, n_2! \cdots n_k!$ of them. So each multiset permutation corresponds to the same number of marked arrangements, and dividing $n!$ by that number gives the count.

In plain words Count as if every object were different, then divide by the number of ways to shuffle each group of identical objects among themselves. Each repeated type gets its own factorial in the denominator. Leaving out the factorial of a repeated type makes the count too large. Dividing once by the number of types is not a valid correction, and for NNEES it would give $120/3 = 40$ instead of $30$ .

Example The tiles NNEES give $5!/(2!\,2!\,1!) = 30$ strings, as found above. Two extreme cases check the formula. If all $n$ objects are different, each object is a type of its own with count $1$ , and the count is $n!$ , the number of ordinary permutations. If all $n$ objects have one type, the count is $n!/n! = 1$ , since every shuffle shows the same sequence. If the five tiles are shuffled so that all $120$ marked orders are equally likely, each visible string has probability $4/120 = 1/30$ , so the $30$ visible strings are equally likely as well, because each one comes from the same number of marked orders.

Multinomial coefficient

Definition For nonnegative integers $n_1, \dots, n_k$ with $n_1 + \cdots + n_k = n$ , the multinomial coefficient is

\binom{n}{n_1, \ldots, n_k} = \frac{n!}{n_1! \cdots n_k!}.

It is a positive integer, because it counts the multiset permutations with these type counts, and it does not change when the lower entries are listed in a different order. A type with count $0$ contributes the factor $0! = 1$ . With two types it is the binomial coefficient from Combinations and Binomial Coefficients, since $\binom{n}{n_1,\, n_2} = \binom{n}{n_1}$ when $n_2 = n - n_1$ . The formula is used only when the lower entries add up to the top entry.

In plain words The multinomial coefficient counts the ways to fill $n$ positions with $n_1$ copies of the first label, $n_2$ copies of the second and so on. The top number is the total, and the bottom numbers are the category counts that make up that total.

Example Three red labels, two green labels and one blue label fill six positions in

\begin{aligned} \binom{6}{3, 2, 1} &= \frac{6!}{3!\,2!\,1!} \\[0.4em] &= \frac{720}{12} = 60 \end{aligned}

different ways. Listing a fourth color with count $0$ does not change the answer, since $\binom{6}{3, 2, 1, 0} = 60$ as well.

Counting by choosing positions

Definition A multiset permutation is determined by the set of positions that each type occupies. Choose the $n_1$ positions of type $1$ from all $n$ positions, then the $n_2$ positions of type $2$ from the $n - n_1$ that remain, and continue in this way. The last type takes all remaining positions, so its factor is $\binom{n_k}{n_k} = 1$ . By the product rule, and because the factorials of the remaining counts cancel,

\begin{aligned} &\binom{n}{n_1}\binom{n - n_1}{n_2} \cdots \binom{n_k}{n_k} \\[0.4em] &\quad = \frac{n!}{n_1! \cdots n_k!}. \end{aligned}

Each set of positions is chosen without order, because the labels of one type are indistinguishable.

In plain words Instead of arranging labels, pick places. Decide where the copies of the first label go, then where the copies of the second go among the places left, and the last label fills whatever remains. This view is convenient when a condition fixes certain positions.

Example For three red, two green and one blue label, there are $\binom{6}{3} = 20$ ways to place the reds and then $\binom{3}{2} = 3$ ways to place the greens among the three remaining positions, and blue takes the one position still free. That gives $20 \cdot 3 = 60$ strings, as before. If blue must come first, fix it there and arrange three reds and two greens in the other five positions, which gives $\binom{5}{3} = 10$ strings. When one of the $60$ strings is chosen with all strings equally likely, the probability that blue comes first is $10/60 = 1/6$ , in agreement with the six equally likely positions of the single blue label.

Allocation to named groups

Definition Let $n$ distinct objects be split among $k$ named groups so that group $i$ receives exactly $n_i$ objects, where $n_1 + \cdots + n_k = n$ and the order of the objects inside a group does not matter. The number of such allocations is the multinomial coefficient $\binom{n}{n_1, \ldots, n_k}$ . To see this, list the objects in a fixed order and write under each object the name of its group. The result is a sequence with $n_i$ copies of name $i$ , and each such sequence describes exactly one allocation. Because the groups are named, exchanging the contents of two nonempty groups of equal size gives a different allocation.

In plain words The objects are distinct and the group names are distinct, but places inside a group are not, and only that last part is divided out. If the groups have no names and only the split into blocks is recorded, blocks of equal size can no longer be told apart. For each block size that occurs $r$ times among the nonempty blocks, divide by another $r!$ .

Example Eight distinct jobs go to teams A, B and C, with three jobs for A, three for B and two for C. Choose the jobs of A in $\binom{8}{3} = 56$ ways and the jobs of B from the remaining five in $\binom{5}{3} = 10$ ways, and C receives the last two, so

\binom{8}{3}\binom{5}{3} = 560 = \frac{8!}{3!\,3!\,2!}.

Teams A and B have the same size, but giving jobs 1, 2 and 3 to A and jobs 4, 5 and 6 to B is a different assignment from the reverse, so there is no extra division by $2!$ . If the teams had no names and only the split into two blocks of three and one block of two mattered, each split would appear twice among the $560$ allocations, and the count would be $280$ .

Multinomial expansion

Definition For every whole number $n \ge 0$ and all numbers $x_1, \dots, x_k$ , the power $(x_1 + \cdots + x_k)^n$ equals the sum of the terms

\binom{n}{n_1, \ldots, n_k}\, x_1^{n_1} x_2^{n_2} \cdots x_k^{n_k}

over all lists $(n_1, \dots, n_k)$ of nonnegative integers with $n_1 + \cdots + n_k = n$ . Here $x^0$ is read as $1$ , also for $x = 0$ . Multiplying out the $n$ brackets gives one product for each way of picking one variable from each bracket. Group these picks by how many brackets supplied each variable. A pick that takes $x_i$ from $n_i$ of the brackets, for every $i$ , has the product $x_1^{n_1} \cdots x_k^{n_k}$ , and the number of such picks is the number of sequences of length $n$ with $n_i$ copies of $x_i$ . Setting every $x_i = 1$ shows that the coefficients add up to $k^n$ .

In plain words Each bracket is a position, and choosing a variable from a bracket places a label there. The coefficient of a term counts the label sequences that produce it. With two variables this is the binomial theorem.

Example In $(a + b + c)^3$ the term $abc$ arises when the three brackets supply $a$ , $b$ and $c$ in some order, so its coefficient is $3! = 6$ . The term $a^2 b$ needs $a$ from two brackets and $b$ from one, which happens in the $3!/(2!\,1!) = 3$ ways $aab$ , $aba$ and $baa$ , so its coefficient is $3$ . The full expansion has ten terms, three cubes such as $a^3$ with coefficient $1$ , six terms such as $a^2 b$ with coefficient $3$ , and $abc$ with coefficient $6$ . Together the coefficients add up to $3 + 18 + 6 = 27 = 3^3$ .

Check yourself

How many distinct strings can be formed from the letters AAAABBC, and how many of them begin with C? If one of the distinct strings is chosen with all strings equally likely, what is the probability that it begins with C?

Show the answer

There are seven letters with type counts $4$ , $2$ and $1$ , so the number of strings is

\frac{7!}{4!\,2!\,1!} = \frac{5040}{48} = 105.

Fixing C in the first position leaves four A and two B for six positions, which gives $6!/(4!\,2!) = 15$ strings. The probability is $15/105 = 1/7$ . As a check, the same count of $15$ holds for C in any of the seven positions, so the single C is equally likely to sit in each of them.

Find the coefficient of $x y^2 z$ in $(x + 2y + z)^4$ .

Show the answer

The term needs $x$ from one bracket, $2y$ from two brackets and $z$ from one bracket. The brackets can supply these in

\frac{4!}{1!\,2!\,1!} = 12

ways, and each such product equals $x \cdot (2y) \cdot (2y) \cdot z = 4xy^2z$ . The coefficient is therefore $12 \cdot 4 = 48$ . Answering $12$ forgets that the constant $2$ is picked twice.

Six people are split into three pairs. Count the splits when the pairs are assigned to three named tasks X, Y and Z, and count them again when only who is paired with whom matters.

Show the answer

With named tasks this is an allocation to named groups of sizes $2$ , $2$ and $2$ , so the count is

\binom{6}{2, 2, 2} = \frac{6!}{2!\,2!\,2!} = 90.

When the tasks are dropped, the three pairs can be attached to the names X, Y and Z in $3! = 6$ ways, and each of these gives a different named allocation. So each pairing appears $6$ times among the $90$ allocations, and there are $90/6 = 15$ pairings. A direct count agrees. Number the people from $1$ to $6$ . Person 1 has $5$ possible partners, the lowest-numbered person left then has $3$ , and the last two people form the final pair, which gives $5 \cdot 3 = 15$ .

Repeated Objects and Multinomial Counting

Key terms

Indistinguishable objects

Multiset permutation

Multinomial coefficient

Counting by choosing positions

Allocation to named groups

Multinomial expansion

Check yourself

How this lesson connects

Builds on

Used later in