Why Repeated Objects Reduce the Number of Arrangements

Why Repetition Changes the Count

When every object is distinct, arranging $n$ objects in a line gives $n!$ possible orders. But that count treats swaps of any two objects as producing a new arrangement. If some objects are indistinguishable, swapping two of those objects changes nothing that can be seen. Counting every swap as a different order therefore counts the same visible arrangement more than once.

For example, suppose there are two identical red counters and one blue counter. If the red counters are temporarily given labels, R1 and R2, then the labeled order R1, R2, blue differs from R2, R1, blue. Once the labels are removed, both orders look like red, red, blue. The central question is how many labeled orders collapse to each visible arrangement. That number determines how to correct the overcount.

Definition: A multiset arrangement is a linear ordering of objects divided into types, where objects of the same type are indistinguishable and objects of different types are distinguishable. If there are $r$ types, with $n_i$ objects of type $i$, the total number of objects is $n=n_1+n_2+\cdots+n_r$. The number of distinct arrangements is $$ \frac{n!}{n_1!n_2!\cdots n_r!}. $$

Here $n_i$ is the multiplicity of type $i$: how many objects of that type are present. The formula counts arrangements in a line, uses every object, and places no additional restrictions on their positions. Objects of the same type must truly be indistinguishable for the count to identify arrangements that differ only by swapping them.

Deriving the Formula: Count, Then Correct

Temporarily label every object, including objects that are supposed to be indistinguishable. For example, label the $n_1$ objects of the first type as 1 through $n_1$, and do the same within every other type. With all $n$ labels distinct, there are $n!$ orders.

Now remove the temporary labels. Fix any one visible arrangement. Its $n_1$ positions for type 1 can be filled by that type's labels in $n_1!$ ways. Independently, its $n_2$ positions for type 2 can be filled in $n_2!$ ways, and so on. Thus the fixed visible arrangement corresponds to exactly $n_1!n_2!\cdots n_r!$ labeled orders.

Every labeled order becomes one visible arrangement when the labels are removed. Also, every visible arrangement has exactly the same number, $n_1!n_2!\cdots n_r!$, of labeled versions. Dividing the total number of labeled orders by the number of labeled versions per visible arrangement therefore counts each visible arrangement exactly once:

\text{number of distinct arrangements} = \frac{\text{number of labeled orders}} {\text{labeled orders for each visible arrangement}} = \frac{n!}{n_1!n_2!\cdots n_r!}.

This division is not an arbitrary adjustment. It corrects a specific, uniform overcount. Each arrangement is counted equally often before the division, so the quotient is exactly the number of distinct visible arrangements.

Worked Example: Seven Counters in Three Types

A hypothetical craft kit contains 3 identical red counters, 2 identical blue counters, and 2 identical green counters. In how many different linear orders can all 7 counters be placed?

If the counters were all labeled as distinct, there would be $7!$ orders. But for any fixed visible color pattern, the 3 red counters could be assigned their temporary labels in $3!$ ways, the 2 blue counters in $2!$ ways, and the 2 green counters in $2!$ ways. Thus each visible pattern appears $3!2!2!$ times among the labeled orders.

The count is

\frac{7!}{3!2!2!} = \frac{5040}{6\cdot 2\cdot 2} = \frac{5040}{24} = 210.

There are 210 distinct linear color patterns. For instance, swapping the two red counters does not create another pattern, because they are indistinguishable.

A Second Way to See the Count

The same answer can be obtained by choosing positions for each type. First choose which $n_1$ of the $n$ positions hold type 1. Then choose which $n_2$ of the remaining positions hold type 2, and continue. The remaining positions belong to the last type. Each final arrangement determines exactly one such sequence of position choices, so this method also counts each arrangement once.

Using combinations, the product of these position counts is

\binom{n}{n_1} \binom{n-n_1}{n_2} \binom{n-n_1-n_2}{n_3} \cdots = \frac{n!}{n_1!n_2!\cdots n_r!}.

To see the cancellation, the first factor is $n!/[n_1!(n-n_1)!]$. The next is $(n-n_1)!/[n_2!(n-n_1-n_2)!]$, so the $(n-n_1)!$ in the first denominator cancels with the numerator of the second factor. Continuing in this way cancels the intermediate factorials, leaving $n!/(n_1!n_2!\cdots n_r!)$. This is a position-based explanation of the same formula.

Worked Example: Objects With One Single Object

A hypothetical display uses 4 identical smooth stones, 3 identical rough stones, and 1 striped stone. The striped stone is the only object of its type. How many linear orders are possible?

There are $8$ objects total. For any visible order, the smooth stones can be temporarily labeled in $4!$ ways, the rough stones in $3!$ ways, and the single striped stone in $1!$ way. The count is therefore

\frac{8!}{4!3!1!} = \frac{40320}{24\cdot 6\cdot 1} = \frac{40320}{144} = 280.

So there are 280 distinct linear orders. The factor $1!$ makes no numerical change: there is only one way to label a single object of its type. This example also shows why a type occurring once still fits naturally in the formula.

Worked Example: Choosing Positions in Turn

A hypothetical set contains 2 identical silver tokens, 2 identical gold tokens, and 2 identical black tokens. Count its distinct linear orders by choosing positions one type at a time, then compare with the formula.

Choose 2 of the 6 positions for the silver tokens. From the 4 positions left, choose 2 for the gold tokens. The last 2 positions must be black. Thus the position-choice count is

\binom{6}{2}\binom{4}{2} = 15\cdot 6 = 90.

The multiset formula gives the same result:

\frac{6!}{2!2!2!} = \frac{720}{2\cdot 2\cdot 2} = \frac{720}{8} = 90.

The position choices do not distinguish the two tokens of a given type. They record only which positions have each type, so each distinct visible order is counted once.

Reading the Denominator Correctly

Each factorial in the denominator corresponds to one type of indistinguishable objects. If type $i$ appears $n_i$ times, permuting those $n_i$ objects among their own positions creates $n_i!$ labeled versions of the same visible arrangement. The denominator is the product of these separate overcounts because the label assignments for different types can be made independently.

A type that appears once contributes $1!=1$, so it does not change the count. If all objects have different types, every $n_i=1$, and the formula reduces to $n!/(1!1!\cdots 1!)=n!$. If there is only one type, then $n_1=n$, and the formula gives $n!/n!=1$: there is just one visible order when all objects are identical.

The formula concerns arrangements of a fixed collection in a line. It does not, by itself, handle restrictions such as requiring two types to be separated, arranging objects around a circle, or leaving some objects unused. Such a problem may still use the same overcounting idea, but its restrictions must be accounted for separately.

Common Mistake: Dividing by the Wrong Amount

A frequent error is to divide by $n!$ because “the objects repeat,” or to divide by just one repeated-type factorial when several types repeat. Neither adjustment matches the overcount. The correction must account for the number of indistinguishable objects within each type, and the separate factors must all be included.

For the 3 red, 2 blue, and 2 green counters, dividing by $3!$ alone would give $7!/3!=840$. That still counts each visible color pattern $2!2!=4$ times, because the blue and green labels have not been accounted for. Dividing by $3!2!2!$ corrects all three sources of overcount and gives 210.

Key takeaway: To count arrangements of $n$ objects with $n_i$ indistinguishable objects of each type, begin with $n!$ labeled orders and divide by $n_i!$ for every type. The result, $n!/(n_1!n_2!\cdots n_r!)$, counts each visible arrangement once.

Check Your Understanding

For each question, identify the multiplicities before calculating.

A set has 3 identical white tokens and 2 identical orange tokens. How many distinct linear orders are there? Show the factorial calculation.
Why does a fixed visible arrangement correspond to $n_1!n_2!\cdots n_r!$ labeled orders?
A collection has 5 objects of one type and 1 object of another type. Which denominator factors appear, and why?
Explain what goes wrong if you divide by only $n_1!$ when two different types each have repeated objects.
When does the multiset arrangement formula reduce to $n!$, and why?