Exam PProbability foundationsFree to read

Counting: permutations, combinations and partitions

Order matters or it does not, and repetition is allowed or it is not. Those two questions pick the formula every time.

The formulas

Multiplication rule

$$n_1 \times n_2 \times \dots \times n_k$$

Permutations

$$P(n,k) = \dfrac{n!}{(n-k)!}$$

order matters, no repetition

Combinations

$$\binom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$$

order does not matter

Multinomial

$$\dfrac{n!}{k_1!\,k_2!\cdots k_m!}$$

split n items into labelled groups

Stars and bars

$$\binom{n+k-1}{k-1}$$

n identical items into k distinct boxes

Where it comes from

1. Choosing $k$ items in order from $n$ leaves $n$ choices, then $n-1$, and so on for $k$ factors - that product is $n!/(n-k)!$.
2. Every unordered set of $k$ items was counted $k!$ times in that product, so dividing by $k!$ gives the combination count.
3. The multinomial coefficient is the same argument applied to several groups at once.

Worked example

This answer is recomputed from the site’s own interest-theory and probability functions every time the test suite runs, so the page and the mathematics cannot drift apart.

Memory hooks

• Ask 'would swapping two of my picks give a different outcome?' Yes means permutation; no means combination.
• Repeated letters in a word: n! divided by the factorial of each repeat count - the multinomial coefficient in disguise.

Traps

• Using a permutation when the selection is a committee (unordered).
• Forgetting to divide by the repeats when arranging items that are not all distinct.

Related

• Probability axioms and set identities
• Hypergeometric distribution
• Binomial distribution

Drill this: the Exam P question bank has original questions on this topic, and today’s free round is open to everyone.