How do I tell whether order matters?

Ask yourself: does swapping two of the chosen items give a different outcome? If it does, order matters and you want permutations or arrangements. A winners podium, a numeric passcode or an assignment of roles on a board are cases where it does. A team line-up, a set of lottery numbers or picking three people for a delegation are cases where it does not.

Because an empty sequence can be arranged in exactly one way — by doing nothing. The definition is not a whim but a consistency requirement: if 0! were zero, the formula for combinations would divide by zero at k = 0 and k = n, although both of those cases obviously have the answer 1.

What is the difference between arrangements and combinations?

Arrangements count order, combinations do not. The same team of three is one combination but six different arrangements, because three people can be ordered in 3! = 6 ways. Hence the formula: combinations are arrangements divided by k!, that is by the number of orderings of one and the same choice.

When is the formula n to the power k the right one?

When each of the k steps chooses from the same n options and items may repeat — arrangements with repetition. Typical cases: a PIN from ten digits, the outcome of a series of dice rolls, a string over a fixed alphabet. The formula is just the rule of product applied k times.

Why is C(n, k) equal to C(n, n − k)?

Because every choice of k items uniquely determines the set of n − k items left behind — and the other way round. The two viewpoints count the same thing, so the counts agree. The practical upshot: C(20, 18) is computed like C(20, 2), in three seconds instead of three minutes.

Can combinatorics be done without formulas?

Very often, yes — with the rule of product alone. Break the choice into steps and count the options at each one. The formulas for permutations and arrangements are nothing but the rule of product written down once and for all; the only thing to remember is to divide by k! if order did not matter.

Why do the numbers grow so fast?

Because every further step MULTIPLIES the number of options rather than adding to it. Ten people can queue up in 10! = 3,628,800 ways, even though there are only ten of them. That is exactly why combinatorial problems are not solved by listing every case.

How do I write down the next row of Pascal's triangle?

Start and end with a 1, and make every entry in between the sum of the two above it — the one to the left and the one to the right. So the row 1, 6, 15, 20, 15, 6, 1 gives 1, 7, 21, 35, 35, 21, 7, 1: the 7 is 1 + 6, the 21 is 6 + 15, the 35 is 15 + 20. Not one factorial is needed — the triangle computes itself.

How do I find the coefficient of a given power?

From the binomial theorem: in the expansion of (a + b) to the power n, the term a to the power n − k times b to the power k carries C(n, k), which is entry k of row n of Pascal's triangle (counting from zero). In (x + 2)⁵ the coefficient of x³ is C(5, 2) · 2² = 10 · 4 = 40. The number from the triangle is not yet the answer — it has to be multiplied by the powers of both terms.

What happens when k is larger than n?

For a choice without repetition, nothing sensible: five distinct items cannot be picked out of a set of three, so the count is zero. For a choice with repetition there is no problem at all, since items may be taken over and over; a ten-character password over 26 letters is simply 26 to the tenth power.

Advanced level

Combinatorics

The art of counting without listing. The rule of product, factorials, permutations, arrangements and combinations all answer one question — in how many ways can this be done — and the whole difficulty comes down to two decisions: does order matter, and may items repeat.

Before you start

This topic builds on earlier ideas. Before you start, it's worth working through the lessons below — they'll make everything click:

MultiplicationMultiplication is repeated addition of the same number. Learn the names of the factors and the product, the laws of multiplication (commutativity, associativity, distributivity), the times tables and column multiplication.
PowersA power is shorthand for multiplying the same factor by itself. Learn the base and the exponent, the laws of exponents, powers of a product and of a quotient, zero and negative exponents, the monotonicity of exponentiation, and scientific notation.
Special productsSeven identities that turn multiplying out brackets into a single line — and the same seven read right to left, which is factoring. The square of a sum and of a difference, the difference of squares, the cubes and the sum and difference of cubes, proved on a drawing and used for mental arithmetic.

Where this is used

Real situations where you count exactly the way this lesson teaches:

How strong a password is
A four-digit PIN is 10⁴ = 10,000 possibilities — a phone locks after three attempts, but a stolen database of such codes falls in a fraction of a second. Eight lower-case letters give 26⁸ ≈ 209 billion combinations, and eight characters drawn from 62 (lower case, upper case, digits) give 62⁸ ≈ 218 trillion, over a thousand times as many. Every character you add multiplies that count by the size of the alphabet rather than adding to it.
See the lesson: Powers
Planning a delivery round
Eight addresses can be visited in 8! = 40,320 different orders; add two more and there are 10! = 3,628,800, ninety times as many. That is why routing software hunts for a good round rather than the best one — the factorial itself says at which point going through the options one by one stops being feasible.
Drawing up a season
In a sixteen-team league everyone plays everyone once per round: C(16, 2) = 120 fixtures, or 240 across two rounds. Eight matches to a matchday makes 30 matchdays, so before a single fixture is drawn you know how many weekends the season has to fill and how many refereeing teams have to be rostered.
Putting a project team together
Three people out of ten can be picked in C(10, 3) = 120 ways. Once the roles differ — lead, analyst, tester — order counts and there are 10 · 9 · 8 = 720 options, six times as many, because every trio can be assigned in 3! = 6 ways. The same distinction settles whether a recruiter is discussing who is on the team or who does what on it.
Where compound interest comes from
Ten years at 5% a year multiply the capital by (1 + 0.05)¹⁰ ≈ 1.6289. The binomial theorem splits that number into parts: the 1 is the capital, 10 · 0.05 = 0.5 is simple interest on its own, and C(10, 2) · 0.05² = 0.1125 is interest on interest — the first term a simple-interest calculation cannot see at all. The remaining terms (0.015 and 0.0013) add the rest. That is why at low rates the gap between simple and compound interest is small, and at high rates it grows quadratically.
See the lesson: Compound interest

All formulas

Rule of product
$N = k_1 \cdot k_2 \cdot \ldots \cdot k_m$
a choice made in several independent steps — multiply the counts
Factorial
$n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n, \qquad 0! = 1$
the product of the first n naturals; 0! equals 1 by definition
Permutations
$P_n = n!$
the number of orderings of all n items
Arrangements without repetition
$\frac{n!}{(n-k)!} = n(n-1)\ldots(n-k+1)$
choose k out of n, order matters, nothing repeats
Arrangements with repetition
$n^k$
k times over, we choose from the same n options
Combinations
$\binom{n}{k} = \frac{n!}{k! \, (n-k)!}$
choose k out of n, order does NOT matter
Symmetry of combinations
$\binom{n}{k} = \binom{n}{n-k}$
choosing k items is the same as discarding the other n − k
Pascal's rule
$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
every entry of the triangle is the sum of the two above it
The binomial theorem
$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$
the coefficients of the expansion are row n of Pascal's triangle

Combinatorics answers the question "in how many ways?" before anyone can start listing cases. It is also a prerequisite for classical probability: to divide the number of favourable outcomes by the number of all of them, you first have to be able to count both.

The rule of product

All of combinatorics grows out of a single observation. If a choice is made in several independent steps offering $k_1, k_2, \ldots, k_m$ options, then the number of outcomes is:

N = k_1 \cdot k_2 \cdot \ldots \cdot k_m

The counts are multiplied, not added — because every decision in the first step can be paired with every decision in the second.

A restaurant offers 4 soups, 6 mains and 3 desserts. How many different three-course meals are there?

Factorials

The product of the first few naturals turns up so often in counting that it has its own symbol:

n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n

It is read "n factorial". The first few values are worth knowing by heart:

$n$	0	1	2	3	4	5	6	7
$n!$	1	1	2	6	24	120	720	5040

Mind the first column: $0! = 1$ , by definition. An empty sequence can be arranged in exactly one way — by doing nothing — and besides, without that convention the combination formula would divide by zero.

The first three bars are almost invisible at this scale. A factorial grows faster than any power — 10! is already over three and a half million.

That growth is a practical hint: if ten people can be ordered in $3{,}628{,}800$ ways, solving a problem by listing cases is out of the question.

Permutations

A permutation is an ordering of all $n$ items. The first position can be filled in $n$ ways, the second in $n-1$ (one item is already used), and so on:

P_n = n \cdot (n-1) \cdot \ldots \cdot 2 \cdot 1 = n!

In how many ways can five people form a queue?

Arrangements without repetition

When only $k$ of the $n$ items are chosen but order matters, we are counting arrangements without repetition:

\frac{n!}{(n-k)!} = n(n-1)\ldots(n-k+1)

The second form is the handier one to compute: it is simply $k$ decreasing factors starting at $n$ .

A club has 8 members. In how many ways can a chair, a secretary and a treasurer be chosen?

Arrangements with repetition

If items may repeat, each of the $k$ steps has the full $n$ options, so the rule of product gives directly:

n^k

How many four-digit PINs are there?

Combinations

When $k$ items are chosen out of $n$ and order does not matter, we have combinations:

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

Where does the $k!$ in the denominator come from? From the fact that the arrangements counted every $k$ -element set $k!$ times over — once for each ordering of the same items. So we divide by the number of those orderings:

\binom{n}{k} = \frac{n!/(n-k)!}{k!}

In how many ways can a delegation of three be chosen out of 8 people?

Symmetry

Combinations have a property that saves a great deal of arithmetic:

\binom{n}{k} = \binom{n}{n-k}

Choosing $k$ items is, after all, the same as naming the $n-k$ items left behind. So $\binom{20}{18}$ is computed like $\binom{20}{2} = 190$ , rather than by writing out eighteen factors.

The counts of choices from a six-element set line up symmetrically: the outer bars are choosing nothing and choosing everything, and the tallest one stands exactly in the middle.

The bars add up to $64 = 2^6$ — the number of subsets of a six-element set, because every item is decided independently: take it or leave it.

Pascal's triangle

The symbols $\binom{n}{k}$ for successive $n$ line up into a triangle in which not one factorial has to be computed. The rows are numbered from zero:

\begin{array}{ccccccccccccc} & & & & & & 1 \\ & & & & & 1 & & 1 \\ & & & & 1 & & 2 & & 1 \\ & & & 1 & & 3 & & 3 & & 1 \\ & & 1 & & 4 & & 6 & & 4 & & 1 \\ & 1 & & 5 & & 10 & & 10 & & 5 & & 1 \\ 1 & & 6 & & 15 & & 20 & & 15 & & 6 & & 1 \end{array}

There is a single rule of construction: every row starts and ends with a 1, and every entry in between is the sum of the two above it. Written in symbols, that is the identity:

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

Why does it hold? Single out one fixed item of the set — say the first. Every choice of $k$ items either takes it (leaving $k-1$ places to fill from the other $n-1$ items) or skips it (all $k$ places have to be filled from those $n-1$ ). The two cases do not overlap and cover everything, so the counts add up.

The triangle also displays two properties we already have, only this time as a picture. The symmetry $\binom{n}{k} = \binom{n}{n-k}$ is the mirror image of a row about its middle. And the entries of row $n$ add up to $2^n$ — row six is exactly the $1, 6, 15, 20, 15, 6, 1$ of the chart above, summing to $64$ .

Write down the eighth row of Pascal's triangle (that is, row number 7).

The binomial theorem

The triangle is not a curiosity — it is the table of coefficients of a power of a sum. The binomial theorem states:

(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k

The justification is again a counting argument rather than an algebraic one. The power $(a+b)^n$ is a product of $n$ identical brackets; multiplying them out, each bracket contributes either $a$ or $b$ . A term with $b^k$ arises exactly when $b$ was taken from $k$ of the $n$ brackets — and there are $\binom{n}{k}$ such choices. Hence the coefficient.

In practice nobody sums this symbolically; you read off row $n$ of the triangle. For $n = 4$ that row is $1, 4, 6, 4, 1$ :

(a+b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4

Note the two independent rhythms: the exponent of $a$ falls from $n$ to zero, the exponent of $b$ rises from zero to $n$ , and in every term the two add up to $n$ . That is the fastest check on an expansion. The special products for $(a+b)^2$ and $(a+b)^3$ are simply rows two and three of this same triangle.

Expand (x + 2)⁵ and give the coefficient of x³.

Which formula to use

The whole difficulty comes down to two questions about the problem:

does order matter?	may items repeat?	formula
yes, all items are used	—	$n!$
yes, $k$ out of $n$	no	$\dfrac{n!}{(n-k)!}$
yes, $k$ out of $n$	yes	$n^k$
no, $k$ out of $n$	no	$\dbinom{n}{k}$

A practical test for the first question: swap two of the chosen items. If that gives a different situation, order matters.

Exercises

The five kinds of question match the five formulas in the table above — Pascal's triangle and the binomial theorem are practised on the worked examples of those sections, because the generator here asks for a number of ways, not for a row or a coefficient. A prompt with an exclamation mark asks straight for a factorial — mind $0! = 1$ . Permutations for a given $n$ is also $n!$ , only phrased in words. Arrangements without repetition and arrangements with repetition both come with $n$ and $k$ ; they differ only in whether items may be taken more than once. Combinations ask for a choice of $k$ out of $n$ with order ignored — and here the symmetry is worth remembering. Every answer is a whole number.

Practice

Work through a set of exercises — they get harder as you go. At the end you'll see your score and the mistakes worth reviewing.

Exercise 1 of 8Score: 0

3! =

Common mistakes

Adding instead of multiplying — successive steps of a choice multiply the counts.
Confusing arrangements with combinations — if order does not matter, the result still has to be divided by $k!$ .
Forgetting $0! = 1$ — especially in the edge cases of the combination formula.
Cancelling factorials by eye — $\tfrac{8!}{5!}$ is $8 \cdot 7 \cdot 6$ , not $\tfrac{8}{5}$ and not $3!$ .
Assuming repetition — whether items may repeat is decided by the problem, not by which formula is more convenient.
Listing the cases — beyond $n = 5$ there are usually far too many to get through without a slip.
Counting a row from one — row $n$ has $n+1$ entries and they are numbered from zero, so $\binom{5}{2}$ is the third entry of row five, not the second.
The bare coefficient instead of the whole term — in the expansion of $(x+2)^5$ the coefficient of $x^3$ is $\binom{5}{2} \cdot 2^2 = 40$ , not $\binom{5}{2} = 10$ : it is the whole 2 that is raised to a power, not just the $x$ .

Formula card

Topic: Combinatorics

Rule of product
$N = k_1 \cdot k_2 \cdot \ldots \cdot k_m$
a choice made in several independent steps — multiply the counts
Factorial
$n! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n, \qquad 0! = 1$
the product of the first n naturals; 0! equals 1 by definition
Permutations
$P_n = n!$
the number of orderings of all n items
Arrangements without repetition
$\frac{n!}{(n-k)!} = n(n-1)\ldots(n-k+1)$
choose k out of n, order matters, nothing repeats
Arrangements with repetition
$n^k$
k times over, we choose from the same n options
Combinations
$\binom{n}{k} = \frac{n!}{k! \, (n-k)!}$
choose k out of n, order does NOT matter
Symmetry of combinations
$\binom{n}{k} = \binom{n}{n-k}$
choosing k items is the same as discarding the other n − k
Pascal's rule
$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
every entry of the triangle is the sum of the two above it
The binomial theorem
$(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k$
the coefficients of the expansion are row n of Pascal's triangle

Factorials for n from 1 to 6. At this scale the first three bars are practically invisible — 6! is already a hundred and twenty times 3!. This is what combinatorial growth looks like.

The number of ways of choosing k items out of six. The picture is symmetric, because choosing k items is the same as discarding the other 6 − k; picking half the set gives the most options.

Frequently asked questions

Luminous histogram bars settling into the soft bell of a distribution, one outlying point brighter than the rest, against a cosmic nebula in violet and magenta

Statistics and probability

The average person does not exist

All of descriptive statistics rests on a single trade: you give up information about a crowd and receive one number in return. The trade is often worth making, but it is never free — and it pays to know exactly what gets lost in it. From the mortality tables of 1662, through Quetelet's average man, to the aircraft nobody ever saw.

16 min