Beginner24 min

Counting, Permutations and Combinations

Product and sum rules, permutations with and without repetition, combinations, and multinomial coefficients.

Counting, Permutations and Combinations

Intuition first

When every outcome is equally likely, a probability is just a fraction: favourable outcomes divided by total outcomes. So computing the probability is counting, and every mistake in this lesson becomes a mistake in every probability that follows.

Two questions settle almost every counting problem:

Does order matter? "ABC" and "CBA" — the same selection or different ones?
Can things repeat? Once used, is an item gone?

Answer those two and the formula follows mechanically. Almost all errors come from answering them wrongly, not from arithmetic.

The two fundamental rules

Multiplication rule. If a task splits into $k$ independent stages with $n_1, n_2, \dots, n_k$ choices, the total number of outcomes is

n_1 \times n_2 \times \dots \times n_k

Addition rule. If a task can be done in one of $k$ mutually exclusive ways, with $n_i$ options in case $i$ , the total is

n_1 + n_2 + \dots + n_k

Notation used in this lesson
Symbol	Meaning	Read aloud
n!	n factorial — the product 1 × 2 × … × n, with 0! = 1	n factorial
P(n, r)	Permutations: ordered selections of r from n	n permute r
C(n, r)	Combinations: unordered selections of r from n	n choose r
nCr or (n r)	Alternative notation for combinations	n choose r

The four cases

	Order matters	Order does not matter
No repetition	$P(n,r) = \dfrac{n!}{(n-r)!}$	$C(n,r) = \dfrac{n!}{r!\,(n-r)!}$
Repetition allowed	$n^r$	$\dbinom{n + r - 1}{r}$

Permutations

Arranging $r$ items from $n$ distinct items, order significant:

P(n, r) = n(n-1)(n-2)\cdots(n-r+1) = \frac{n!}{(n-r)!}

The reasoning is the multiplication rule: $n$ choices for the first position, $n-1$ for the second (one is used up), and so on for $r$ positions.

Combinations

C(n, r) = \binom{n}{r} = \frac{n!}{r!\,(n-r)!}

Why combinations divide by r!Advanced

Count ordered selections first: $P(n,r) = n!/(n-r)!$ .

Now notice that every unordered selection of $r$ items was counted multiple times — once for each way of ordering those $r$ items, which is $r!$ ways.

So the ordered count is exactly $r!$ times the unordered count:

P(n,r) = r! \times C(n,r) \quad\Longrightarrow\quad C(n,r) = \frac{P(n,r)}{r!} = \frac{n!}{r!\,(n-r)!}

Dividing by $r!$ removes the over-counting. This "count with order, then divide by the over-count" technique solves a large fraction of harder counting problems.

Two identities worth knowing by sight:

\binom{n}{r} = \binom{n}{n-r} \qquad\text{(choosing } r \text{ to keep = choosing } n-r \text{ to discard)}

\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r} \qquad\text{(Pascal's rule)}

Permutations with repeated items

Arranging $n$ items where $n_1$ are identical of one type, $n_2$ of another, and so on:

\frac{n!}{n_1!\,n_2!\cdots n_k!}

This is the multinomial coefficient, and it is the same divide-by-the-over-count idea: swapping two identical letters produces no new arrangement.

Solved problem 1 · Arrangements of a word with repeats

How many distinct arrangements are there of the letters in STATISTICS?

Step 1 — count letters and their multiplicities

STATISTICS has 10 letters:

\text{S}: 3, \quad \text{T}: 3, \quad \text{A}: 1, \quad \text{I}: 2, \quad \text{C}: 1

Check: $3 + 3 + 1 + 2 + 1 = 10 \;\checkmark$

Step 2 — apply the multinomial coefficient

\frac{10!}{3!\,3!\,1!\,2!\,1!}

Step 3 — evaluate

10! = 3{,}628{,}800

3! \times 3! \times 1! \times 2! \times 1! = 6 \times 6 \times 1 \times 2 \times 1 = 72

\frac{3{,}628{,}800}{72} = 50{,}400

Answer

$50{,}400$ distinct arrangements.

Solved problem 2 · A committee with constraints

A department has 7 men and 5 women. How many 4-person committees contain at least one woman?

Step 1 — total committees with no constraint

Order does not matter and nobody serves twice, so this is a combination:

\binom{12}{4} = \frac{12!}{4!\,8!} = \frac{12 \times 11 \times 10 \times 9}{4 \times 3 \times 2 \times 1} = \frac{11{,}880}{24} = 495

Step 2 — use the complement

"At least one woman" has many cases (1, 2, 3 or 4 women). Its complement has exactly one: no women, i.e. all 4 chosen from the 7 men.

\binom{7}{4} = \frac{7 \times 6 \times 5 \times 4}{4 \times 3 \times 2 \times 1} = \frac{840}{24} = 35

Step 3 — subtract

495 - 35 = 460

Step 4 — verify by direct enumeration

Summing the four cases as a check:

\binom{5}{1}\binom{7}{3} = 5 \times 35 = 175

\binom{5}{2}\binom{7}{2} = 10 \times 21 = 210

\binom{5}{3}\binom{7}{1} = 10 \times 7 = 70

\binom{5}{4}\binom{7}{0} = 5 \times 1 = 5

175 + 210 + 70 + 5 = 460 \;\checkmark

Answer

$460$ committees. The complement route needed one binomial coefficient; direct enumeration needed four.

Combinations with repetition

Choosing $r$ items from $n$ types, repetition allowed, order irrelevant — how many ways to pick 6 doughnuts from 4 varieties?

\binom{n + r - 1}{r}

The stars and bars argumentAdvanced

Represent a selection as $r$ stars divided into $n$ groups by $n-1$ bars. Six doughnuts from four varieties, taking 3 of the first, 0 of the second, 2 of the third and 1 of the fourth:

text

***||**|*

Every arrangement of 6 stars and 3 bars corresponds to exactly one selection, and every selection to exactly one arrangement. So we are counting arrangements of $r + n - 1$ symbols where $r$ are stars:

\binom{r + n - 1}{r} = \binom{6 + 4 - 1}{6} = \binom{9}{6} = 84

The bijection is the whole argument — once you see that a selection is a star-and-bar string, the formula is just the multinomial count.

Counting in code

python

from math import comb, perm, factorial

print(f"P(8,3) = {perm(8, 3)}")              # 336 — medals, order matters
print(f"C(52,5) = {comb(52, 5):,}")          # 2,598,960 — poker hands
print(f"STATISTICS = {factorial(10) // (factorial(3)*factorial(3)*factorial(2)):,}")
print(f"doughnuts  = {comb(6 + 4 - 1, 6)}")  # 84 — stars and bars

# Verify Pascal's rule for a few values.
assert all(comb(n, r) == comb(n-1, r-1) + comb(n-1, r)
           for n in range(1, 20) for r in range(1, n))
print("Pascal's rule verified")

Exercise 1

From a standard 52-card deck, how many 5-card hands contain exactly 2 aces?

Show solution

Split the choice into two independent stages and multiply.

Choose 2 of the 4 aces:

\binom{4}{2} = 6

Choose the remaining 3 cards from the 48 non-aces:

\binom{48}{3} = \frac{48 \times 47 \times 46}{6} = \frac{103{,}776}{6} = 17{,}296

By the multiplication rule:

6 \times 17{,}296 = 103{,}776

As a probability:

\frac{103{,}776}{2{,}598{,}960} \approx 0.0399

The common error is choosing 3 cards from all 50 remaining, which allows a third ace and therefore counts hands with 3 or 4 aces.

Exercise 2

How many ways can 8 people be seated at a round table, if rotations are considered identical?

Show solution

Linear arrangements of 8 people: $8! = 40{,}320$ .

At a round table each distinct seating is counted once for every rotation. With 8 seats there are 8 rotations producing the same circular arrangement, so

\frac{8!}{8} = 7! = 5{,}040

The standard shortcut: fix one person's seat to break the rotational symmetry, then arrange the remaining 7 freely, giving $7!$ directly.

If reflections also count as identical — relevant for necklaces rather than dinner parties — divide by a further 2, giving $7!/2 = 2{,}520$ .

Exercise 3

A password is 6 characters from the 26 lowercase letters. How many contain at least one repeated letter?

Show solution

Total passwords, repetition allowed and order mattering:

26^6 = 308{,}915{,}776

Passwords with all distinct letters — the complement:

P(26, 6) = 26 \times 25 \times 24 \times 23 \times 22 \times 21

26 \times 25 = 650, \quad 650 \times 24 = 15{,}600, \quad 15{,}600 \times 23 = 358{,}800

358{,}800 \times 22 = 7{,}893{,}600, \quad 7{,}893{,}600 \times 21 = 165{,}765{,}600

Subtract:

308{,}915{,}776 - 165{,}765{,}600 = 143{,}150{,}176

So about 46.3% of 6-letter passwords contain a repeat — a version of the birthday problem, and higher than most people guess.

Next: Inclusion–Exclusion and Pigeonhole, for counting problems where the cases overlap.