Skip to main content

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)

Every counting question sits in one of these four cells once you answer two yes/no questions: does order matter, and is repetition allowed? 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 / Where This Shows Up Later​

  • Semester 2 algorithms: permutation counting underlies sort lower bounds ($\log_2 n!$ comparisons in the worst case). Multinomial bounds appear in the analysis of quicksort and in merge-sort recursion trees.
  • Semester 3 data structures: counting BSTs of $n$ labeled keys uses Catalan numbers (a combination divided by a symmetry factor). Permutation statistics govern hash-function uniformity arguments.
  • Semester 5 concurrency: the number of valid interleavings of $n$ threads each executing $k_i$ instructions is a multinomial coefficient, directly bounding the state space a model checker must explore.
  • Semester 7 architecture: capacity planning for sharded systems uses combinations when assigning keys to shards without replacement; with replacement (replication), the setup shifts to stars and bars.
  • Semester 6 distributed systems: the number of distinct quorum configurations on $n$ replicas with read-quorum $r$ and write-quorum $w$ is a combination; Paxos correctness proofs rely on $\binom{n}{r} + \binom{n}{w} > \binom{n}{r} \binom{n}{w}$ style pigeon counting.
  • Cryptography: key-space sizing for password cracking uses $26^n$ (permutations with repetition) vs $\binom{n+k-1}{k-1}$ for passphrase dictionaries (combinations with repetition); the gap is the practical difference between brute-force feasibility and infeasibility.

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​