Counting Allocations with Multinomial Coefficients

Recommended resources

The freely available resources this lesson will direct you to.

Hello! Last lesson, you counted unordered selections from distinct objects. Now suppose every object must go into one of several named groups, with each group’s size fixed in advance. Choosing one group determines what remains available for the others, so the combination rule you already know is enough to build the new count.

This lesson derives the multinomial coefficient in two ways and uses it to distinguish labelled groups from unordered collections of groups. Allow about 35–40 minutes, including the short video and reading.

An allocation is a sequence of selections

Suppose eight distinct proposals must be assigned to three destinations: three to Review, two to Audit, and three to Archive. A complete outcome specifies which proposals belong to each destination. It does not specify an order within Review, Audit, or Archive.

Choose the Review proposals first, then the Audit proposals from those remaining. The final three must go to Archive. By the multiplication principle, the count is

(3 8) (2 5) (3 3) = 56 \cdot 10 \cdot 1 = 560.

The destinations are labelled: assigning proposals $A, B, C$ to Review and $D, E, F$ to Archive differs from swapping those two sets, even though both destinations hold three proposals. There is no division by $2!$ for their equal sizes.

Watch the three-task example in Jingchen (Monika) Hu’s [Chapter 1] #6 Multinomial coefficients. It develops exactly this sequential-selection argument before introducing the general notation.

[Chapter 1] #6 Multinomial coefficients

Jingchen (Monika) Hu's [Chapter 1] #6 Multinomial coefficients shows how successive combinations count assignments of distinct people to tasks with fixed staffing levels.

Watch the assignment for why the last group requires no further choice. Then watch the cancellation and the general rule. Focus on why group membership matters while order within a group does not.

The general rule

Let $n$ distinct objects be allocated among $k$ labelled groups. Group $j$ must contain $n_{j}$ objects, where every $n_{j}$ is nonnegative and

n_{1} + n_{2} + \dots + n_{k} = n .

Choose $n_{1}$ objects for group 1, then $n_{2}$ from the $n - n_{1}$ remaining objects for group 2, and continue. Once the first $k - 1$ groups have been filled, the last group is determined. Thus the count is

(n _{1} n) (n _{2} n - n _{1}) \dots (n _{k - 1} n - n _{1} - \dots - n _{k - 2}) .

Writing out the binomial coefficients as factorials makes the intermediate factorials cancel. The result is the multinomial coefficient:

(n _{1} , n _{2} , \dots , n _{k} n) = \frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !} .

The lower entries are the group sizes in label order. Their sum must equal the upper entry.

For three groups, you can see every cancellation explicitly. With $n_{1} + n_{2} + n_{3} = n$ ,

(n _{1} n) (n _{2} n - n _{1}) = \frac{n !}{n _{1} ! ( n - n _{1} )!} \frac{( n - n _{1} )!}{n _{2} ! n _{3} !} = \frac{n !}{n _{1} ! n _{2} ! n _{3} !} .

When $k = 2$ , the second group is simply the complement of the first. The rule reduces to last lesson’s combination formula:

(r , n - r n) = (r n) .

A prescribed size may also be zero. Since $0! = 1$ , an empty labelled group fits the same formula: there is exactly one way to give it no objects.

Why the denominator removes exactly the right distinctions

There is a second derivation, useful when checking whether a division by a factorial is justified. List all $n$ distinct objects in a row. Assign the first $n_{1}$ positions to group 1, the next $n_{2}$ to group 2, and so on. Every one of the $n!$ lists produces an allocation.

But many lists produce the same allocation. For any fixed allocation, its group 1 members can be rearranged within their block in $n_{1}!$ ways, its group 2 members in $n_{2}!$ ways, and similarly for every group. Therefore each allocation, without exception, comes from exactly $n_{1}! n_{2}! \dots n_{k}!$ lists. Dividing $n!$ by that common number gives the multinomial coefficient again.

Read the formal version in MIT OpenCourseWare’s 6.042J Chapter 11: Cardinality Rules. Its “split” is an ordered sequence of subsets: the sequence positions play the role of our group labels.

[PDF] 6.042J Chapter 11: Cardinality rules - MIT OpenCourseWare

Read MIT OpenCourseWare's treatment of the Subset Split Rule for a precise account of why the factorial division works.

In Section 11.6, "Sequences with Repetitions," find subsection 11.6.1, "Sequences of Subsets" (printed p. 326). Begin where the text says that choosing a subset is splitting a set into two parts. Read the split rule, stopping just before subsection 11.6.2, "The Bookkeeper Rule." Focus on the map from a permutation to a split, and on why every split has the same number of permutations mapping to it.

The two derivations count the same outcomes from different starting points. Successive combinations build an allocation group by group; permutations divided by within-group reorderings start with lists and remove distinctions the allocation does not retain.

Modelling an allocation carefully

Imagine nine distinct records assigned to three named reviewers, with workloads of four, three, and two. No order is specified for the records within a reviewer’s workload, so the number of allocations is

(4 , 3 , 2 9) = \frac{9 !}{4 ! 3 ! 2 !} = 1260.

If instead the task were to assign each reviewer a ranked queue of records, changing the order within a queue would create a different outcome. The multinomial coefficient would then count only the group memberships, not the complete ranked queues. As always, the first question is what information defines one outcome.

“All objects must be allocated” need not mean all receive an active assignment. If eight distinct applications yield three for immediate review, two for later review, and three left untouched, treat Untouched as a third labelled group. The count is

(3 , 2 , 3 8) = 560.

Without that last group, the proposed sizes would add to only five, and the multinomial expression would not describe an allocation of all eight applications.

The familiar multiset-arrangement formula from an earlier lesson has the same numerical form, but it describes a different object. If you write one destination label beside each of the eight distinct applications, an allocation with group sizes $3, 2, 3$ becomes a length-eight sequence containing three Review labels, two Audit labels, and three Archive labels. Each such label sequence specifies exactly one allocation because each sequence position belongs to a distinct application. The equality of the counts is therefore a correspondence, not a coincidence.

Key takeaways

For $n$ distinct objects going into labelled groups of prescribed sizes $n_{1}, \dots, n_{k}$ , check that the sizes sum to $n$ , then count with

(n _{1} , \dots , n _{k} n) = \frac{n !}{n _{1} ! \dots n _{k} !} .

You can recover the formula either by choosing each group in turn or by dividing $n!$ lists by the reorderings within groups. Equal group sizes do not make labelled groups interchangeable.

This completes the first module’s counting toolkit. Next, you will use complementary counting to handle constraints that are easier to describe by what must not happen.