Permutations, Combinations, and Multinomial Thinking

What This Concept Is

Permutations and combinations are specialized answers to a structural question about what counts as the same outcome:

• permutation: ordered selection or arrangement. Reordering produces a different outcome. Counted by $P(n,k) = \frac{n!}{(n-k)!}$ when selecting $k$ from $n$.
• combination: unordered selection. Reordering produces the same outcome. Counted by $\binom{n}{k} = \frac{n!}{k!,(n-k)!}$.
• multinomial count: arrangement of labeled positions when several categories repeat. Given total $n$ with group sizes $n_1, n_2, \ldots, n_r$ (summing to $n$), the count is $\binom{n}{n_1, n_2, \ldots, n_r} = \frac{n!}{n_1!,n_2!,\cdots,n_r!}$.

These formulas are the division rule in disguise. $\binom{n}{k}$ is $P(n,k)$ divided by $k!$ because each unordered subset gets counted $k!$ times by the ordered procedure. The multinomial coefficient is $n!$ divided by the product of internal symmetries within each indistinguishable group.

The formulas matter, but only after you know which distinctions the problem cares about. The real work is identifying the equivalence relation the problem imposes on outcomes.

A useful mental matrix sorts the four variants:

	order matters (sequence)	order does not matter (set)
no repeats	$P(n,k) = n!/(n-k)!$	$\binom{n}{k}$
repeats	$n^k$	$\binom{n+k-1}{k}$ (cluster 2)

For basic selection problems, first answer two questions: does order matter, and is repetition allowed? The four cells describe those basic models; additional restrictions require further reasoning. Write those two answers down before touching factorials.

Why It Matters Here

A large fraction of counting errors come from answering the wrong question:

• counting order when the problem does not care
• forgetting order when the problem does care
• ignoring repeated objects or repeated categories
• splitting into ordered stages and forgetting to quotient

You need to hear the difference between "choose 3 people for the committee" (combination) and "assign president, vice-president, and treasurer to 3 people" (permutation). The first treats the trio as a set; the second treats it as a labeled tuple.

Multinomial thinking comes up the moment categories appear: assigning $n$ tasks to $k$ workers with fixed quotas, distributing poker hands among players, counting interleavings of colored marbles in a row.

Concrete Examples

Example 1: MISSISSIPPI. How many distinct arrangements of the letters in MISSISSIPPI?

There are $11$ total positions, with letter multiplicities M: $1$, I: $4$, S: $4$, P: $2$. If all letters were distinct, there would be $11!$ arrangements. Swapping two identical Is yields the same string, and likewise for S and P, so each distinct string is counted $4! \cdot 4! \cdot 2!$ times in $11!$. Divide:

$$\frac{11!}{4!,4!,2!} = \frac{39,916,800}{24 \cdot 24 \cdot 2} = 34,650.$$

That is exactly the multinomial coefficient $\binom{11}{1,4,4,2}$.

Example 2: team split. In how many ways can $12$ students be split into three labeled groups of sizes $5$, $4$, and $3$ (Group A, Group B, Group C)?

Stage 1: choose $5$ students for Group A: $\binom{12}{5}$. Stage 2: choose $4$ from the remaining $7$ for Group B: $\binom{7}{4}$. Stage 3: remaining $3$ form Group C: $\binom{3}{3} = 1$.

Product: $\binom{12}{5}\binom{7}{4}\binom{3}{3} = 792 \cdot 35 \cdot 1 = 27{,}720 = \binom{12}{5,4,3}$.

If the three groups were unlabeled and all the same size, we would additionally divide by $3!$ to remove the false ordering of groups. Labels change everything.

Example 3: bridge deal. How many ways can a standard $52$-card deck be dealt to four labeled players (North/East/South/West) so each receives $13$ cards?

This is a four-category multinomial with $n_1 = n_2 = n_3 = n_4 = 13$:

$$\binom{52}{13, 13, 13, 13} = \frac{52!}{(13!)^4} \approx 5.36 \times 10^{28}.$$

Each of the roughly $5 \times 10^{28}$ deals is a distinct game-playing situation. That astronomical number is why bridge analysis leans heavily on probability: exact case analysis is hopeless, but multinomial modeling produces the denominator of every subsequent probability calculation.

Common Confusion / Misconceptions

• Memorizing $nPr$ vs $nCr$ without modeling. Learners memorize the formulas but still misapply them because they never ask what counts as the same outcome. The formula does not answer that; the problem statement does.
• Treating identical objects as distinct. If two red balls are genuinely indistinguishable, swapping them does not create a new arrangement. The division factor removes this phantom count.
• Forgetting to divide by group symmetry. When dividing $10$ students into three unlabeled teams of sizes $4, 3, 3$, the two size-$3$ teams are interchangeable; the raw multinomial overcounts by $2!$.
• Conflating "distinct" with "distinguishable in the problem." Two coin tosses HT and TH are distinct sequences but not distinct if the question only asks "how many heads?" The problem framing dictates the equivalence, not physical intuition.
• $\binom{n}{k}$ when $k > n$. By convention $\binom{n}{k} = 0$ if $k > n$ or $k < 0$. Forgetting this convention in generating-function arguments (cluster 3) produces phantom nonzero terms.
• Multinomial groups with size $0$. $\binom{n}{n_1, \ldots, n_r}$ is still defined if some $n_i = 0$; $0! = 1$. Some learners incorrectly drop terms and produce the wrong coefficient in the multinomial theorem.

How To Use It

Ask, in order:

1. Does order matter? (If you permuted the outcome, is it the same to the problem?)
2. Are all selected objects distinct, or are there repeats?
3. Are some categories repeated, requiring division by internal symmetries?
4. Is the outcome a subset, a sequence, a role assignment, or a partition into labeled/unlabeled groups?
5. Can the count be recomputed by the product rule and a division rule separately, as a cross-check?

Then choose:

• role assignment or ranking $\to$ permutation logic
• pure selection $\to$ combination logic
• repeated categories in positions $\to$ multinomial logic
• unlabeled groupings of equal size $\to$ multinomial divided by the group-label symmetry
• sequences with repetition $\to$ plain $n^k$ (product rule, no division)
• multisets (unordered with repetition) $\to$ the combinations-with-repetition formula $\binom{n+k-1}{k}$ (covered in cluster 2 as stars-and-bars)

Transfer to the workshop model

Use this concept to justify or challenge one result in the workshop project. Specify the counted objects or graph semantics before interpreting any numerical output.

Check Yourself

1. Why is $\binom{n}{k}$ smaller than $P(n,k)$ when $k > 1$? State the ratio and interpret it.
2. What symmetry causes division in multinomial counts? Give a two-category example.
3. When does $n!$ become an overcount? Name two different situations.
4. Derive $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ by a two-case argument, explaining what the cases are.
5. Compare: how many $5$-letter words (ordered) vs $5$-letter multisets (unordered) can be made from the $26$-letter English alphabet? Which formula?
6. Explain why $\binom{n}{k, n-k}$ equals $\binom{n}{k}$. What is the general identity relating multinomial coefficients with two categories to ordinary binomials?
7. For the multinomial theorem $(x_1 + \cdots + x_r)^n = \sum \binom{n}{n_1, \ldots, n_r} \prod x_i^{n_i}$, count the number of terms in the expansion before simplification. Why does it equal the number of length-$n$ sequences over ${1, \ldots, r}$?

Mini Drill or Application

Classify each problem as permutation, combination, or multinomial and explain why; then compute:

1. Select $5$ books from a shelf of $20$ to read this month.
2. Select gold, silver, and bronze winners from $20$ finalists.
3. Count distinct arrangements of BANANA.
4. Count ways to split $10$ students into labeled groups of sizes $4, 3, 3$.
5. Count ways to split $10$ students into unlabeled groups of sizes $4, 3, 3$.
6. How many distinct interleavings of two sequences of lengths $5$ and $4$? (This is also the number of monotone lattice paths, tying back to Example 3 in the previous concept.)
7. Poker: how many distinct $5$-card hands contain exactly one pair? Write the count as a product of a combination (choose rank of the pair), a combination (choose the two suits of that rank), and a permutation (choose and suit the three remaining distinct ranks).

Read This Only If Stuck

Use the bounded reading guide to locate the topic in MCS or Rosen. These links open indexes. Check the actual heading in your edition, read one targeted explanation, then reconstruct the argument with the book closed.

A four-cell table is a starting model, not a universal solver

Ordered/unordered and replacement/no replacement describe unconstrained basic selections. An adjacency restriction, forbidden pair, capacity or equivalence under rotation adds information those two yes/no answers do not encode. Name those constraints before deciding that a factorial or binomial formula applies.

The empty ordered sequence and the empty subset each count once. With zero available types there is one selection of size zero and none of positive size; the combinations-with-repetition formula with a negative top entry should not be applied blindly. For unlabeled equal-size groups, division by the factorial of the number of groups requires proving every grouping has that many distinct labelings. Transfer: compare the two group models in P3.

After your attempt use practice feedback and model contracts to check the argument.