Counting Arrangements of Multisets

Hello! Last lesson, you counted sequences in which a symbol could be reused without limit. Now the supply is fixed: you might have two $A$s, one $B$, and one $C$, and must arrange all four symbols. The positions still matter, but exchanging the two $A$s does not produce a new arrangement.

This lesson develops a reliable way to count such arrangements, proves the formula behind it, and shows how to distinguish a fixed inventory from unrestricted reuse. Allow about 35–40 minutes, including the video and reading.

When a swap changes nothing

Consider the four symbols $A,A,B,C$. If the $A$s were distinguishable—temporarily call them $A_1$ and $A_2$—there would be $4!=24$ ways to arrange the four objects. But the labelled arrangements $A_1{A}_{2}BC$ and $A_2{A}_{1}BC$ both appear as $AABC$ once the subscripts are erased. Every visible arrangement has exactly two labelled versions, so the number of distinct arrangements is

The image makes this overcount visible. Compare its columns by asking which swaps you can still detect after balls of the same color become indistinguishable.

Watch Eddie Woo’s Permutations: how do we account for repetitions? for the transition from one repeated type to several. His examples use letter strings; they need not be dictionary words to count as distinct arrangements.

The important word is each: division is justified because each distinct visible arrangement corresponds to the same number of arrangements with artificial labels. We can establish that number in general.

The multiset arrangement rule

A multiset records types of objects and how many copies of each type are present. Suppose there are $k$ distinct types, with respective multiplicities $m_1,\dots ,m_k$, and every object is used. The total number of positions is

The number of distinct linear arrangements is

To prove it, temporarily give every copy a unique label. All $n$ objects are then distinguishable, so there are $n!$ labelled arrangements. Take any one arrangement after the labels have been erased. Its $m_1$ positions occupied by the first type can receive that type’s labels in $m_1!$ ways; its $m_2$ positions occupied by the second type can receive their labels in $m_2!$ ways; and so on. The multiplication principle gives exactly $m_1!\cdots m_k!$ labelled arrangements for every visible arrangement. Dividing $n!$ by this common overcount proves the rule.

Notice the limiting cases. If all $n$ objects have different types, every denominator factor is $1!$, and the answer is $n!$. If all $n$ objects have the same type, the answer is $n!/n!=1$. The formula moves between these extremes as more copies become indistinguishable.

Read the example in MIT OpenCourseWare’s Counting, II course notes. It counts arrangements of BOOKKEEPER and then applies the same reasoning to a sequence of walking directions. The notes express an arrangement as sets of positions occupied by each letter; that is another way to describe the visible string, not an additional ordering within a type.

BOOKKEEPER contains ten letters: one $B$, two $O$s, two $K$s, three $E$s, one $P$, and one $R$. Thus its count is

The factorials in the denominator correspond to types of letter, not to positions in the original word. A repeated letter can occupy nonadjacent positions; those positions are still part of the same visible arrangement.

Recognizing an arrangement in a different setting

In the notes’ walking example, a route consists of 20 recorded moves: five north, five east, five south, and five west. Writing down the directions in order specifies the walk completely. Each direction appears five times, but the individual northward moves, for example, carry no separate identities. The count is therefore

This way of representing an outcome is useful beyond literal objects. Suppose five successive observations are classified as high, moderate, or low, with exactly two high, two moderate, and one low. There is only one stated collection of counts—$(2,2,1)$—but there are

possible time-ordered classification sequences with those counts. The formula counts the sequences, not the collection of counts. This distinction will matter when counting outcomes for probability calculations later in the course.

The method has two checks worth making before you use it:

• Are positions distinguishable? Day 1 versus day 2, or the first letter versus the second, must matter. The rule counts linear arrangements.
• Is the multiplicity of every type fixed, with the whole inventory used? If so, the denominator records which exchanges are invisible. Extra restrictions on positions require further reasoning; the quotient alone does not enforce them.

Fixed multiplicities are not unlimited reuse

The previous lesson’s $n^r$ and today’s factorial quotient answer different questions. With three available symbols $A,B,C$, unrestricted reuse in four positions gives $3^4=81$ sequences. If the specification instead requires exactly two $A$s, one $B$, and one $C$, the count is $4!/(2!1!1!)=12$.

Both questions concern ordered sequences, and both permit a repeated symbol to appear in the result. The distinction is whether you have unrestricted choices at each position or prescribed totals across all positions. Writing down the inventory before choosing a formula is often enough to prevent a miscount.

Key takeaways

For $n$ objects comprising $m_1,\dots ,m_k$ indistinguishable copies of each type, with all objects used, the number of distinct linear arrangements is $n!/(m_1!\cdots m_k!)$. The proof starts with $n!$ artificially labelled arrangements and divides by the number of labelings that produce each identical visible arrangement.

Next, you will count unordered selections. Instead of arranging an entire fixed inventory, you will decide which objects to take when the order of selection does not matter.