Combinatorics calculator: permutations, arrangements and combinations with working

Answer three questions (all or some, does order matter, can things repeat) and the solver picks the formula, explains it, computes the answer and, for small problems, lists every option.

Examples: 10 choose 3 P(8,3) anagrams of MATHEMATICS 10 identical balls into 4 boxes, at least 1 in each three-digit even numbers from digits 0, 1, 2, 3, 4, 5 without repetition from 1 to 1000 divisible by 2, 3 or 5 total 30, A = 18, B = 15, A∩B = 7 C(10,3)·C(5,2)

Loading the solver…

Three questions instead of a table of formulas

Combinatorics has hardly any difficult calculations: anyone can multiply $10 \cdot 9 \cdot 8$. The hard part is knowing which formula to use. Combinations and permutations differ by one word, yet their answers differ by a factor of $k!$. So the solver starts not with a formula but with three questions about the problem.

Do we take all the elements or only some? Seating six people on six chairs: all. Choosing three out of ten: some.
Does order matter? The test is simple: swap two of the chosen ones. If you get something different (gold and silver swapped, the code 172 became 712), order matters. If nothing changed (the same team, the same bunch of flowers), it doesn’t.
Can one element be taken more than once? Digits in a code can repeat; people on a committee can’t.

The answers lead straight to the formula:

All or some	Order	Repeats	What it is	Formula
all $n$	matters	no	permutations	$n!$
$k$ of $n$	matters	no	arrangements ($k$-permutations)	$P(n, k) = \frac{n!}{(n-k)!}$
$k$ of $n$	doesn’t matter	no	combinations	$\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$
$k$ places	matters	yes	arrangements with repetition	$n^k$
$k$ items	doesn’t matter	yes	combinations with repetition	$\binom{n+k-1}{k}$

Textbooks write combinations in two ways, $\binom{n}{k}$ and $C(n, k)$ (some also write $C_n^k$), and it’s the same number. Arrangements are written $P(n, k)$ or ${}^nP_k$ (in some textbooks $A_n^k$), and on calculators they correspond to the nPr and nCr buttons.

Where the formulas come from

All the formulas in the table follow from one rule, the product rule: if the first choice can be made in $a$ ways and, after it, the second in $b$ ways, the pair of choices can be made in $a \cdot b$ ways. Take three medal places and ten athletes. All ten are in the running for gold. Once gold is awarded, nine remain for silver and eight for bronze. That makes $10 \cdot 9 \cdot 8 = 720$ podiums.

How many we choose from.

How many places we fill. Each next place has one option fewer, because the element taken drops out.

Example: $P(10, 3) = 10 \cdot 9 \cdot 8 = 720$. With factorials it’s the same thing: $\frac{10!}{7!}$, which cuts off the “tail” $7 \cdot 6 \cdots 1$ of $10!$ that we don’t need.

Now let’s ask something else: in how many ways can we choose three of the same ten for a team where everyone is equal? Take one trio: Ann, Ben and Cat. Among the 720 podiums it appears six times: ABC, ACB, BAC, BCA, CAB, CBA, the $3! = 6$ orderings of three people. The same goes for every trio. So there are six times fewer trios than podiums.

How many we choose from.

How many we take.

The number of ways to order one chosen set. Each set is counted exactly $k!$ times among the arrangements, so we divide.

Example: $\binom{10}{3} = \frac{720}{6} = 120$. It’s convenient to compute it as $\frac{10 \cdot 9 \cdot 8}{3 \cdot 2 \cdot 1}$: $k$ decreasing factors on top, $k!$ below. And if $k$ is more than half of $n$, use $\binom{n}{k} = \binom{n}{n-k}$: choosing 7 of 10 is the same as choosing the 3 we leave out.

The same idea, “count with extras, then divide by the number of repeats”, works for words with repeated letters and for a round table. MATHEMATICS has eleven letters, but two M’s, two A’s and two T’s. If all the letters were different there would be $11!$ permutations. Swapping identical letters with each other doesn’t give a new word, so we divide by $2! \cdot 2! \cdot 2!$. At a round table you divide by $n$: all $n$ rotations of one seating are the same seating, which leaves $(n-1)!$.

Identical items: stars and bars

In how many ways can you put 10 identical sweets into 4 boxes? The sweets are indistinguishable, so a distribution is just four numbers adding up to 10, such as $(5, 1, 2, 2)$. Lay the sweets in a row and put three dividers between them: up to the first divider is the first box, between the first and second is the second, and so on. A string of 13 symbols is determined entirely by where the dividers stand.

How many identical items we distribute.

How many distinct boxes. There’s one divider fewer.

Example: $n = 10$, $k = 4$ gives $\binom{13}{3} = 286$. If every box must get at least one sweet, first put one in each, then distribute the remaining six however you like: $\binom{9}{3} = 84$. The same formula counts the solutions of $x_1 + x_2 + x_3 + x_4 = 10$ in non-negative integers, and combinations with repetition.

But if the items are distinguishable, say ten different postcards for four addressees, each postcard picks its box independently of the others, and the answer is $4^{10}$. Mixing up these two problems is one of the most common mistakes.

Inclusion–exclusion

How many numbers from 1 to 1000 are divisible by 2, 3 or 5? Multiples of two: 500; of three: 333; of five: 200. But you can’t just add them: the number 6 is counted both among the “twos” and among the “threes”. Subtract the multiples of 6, 10 and 15. Now the number 30 was first added three times and then subtracted three times, so it has dropped out of the count. Add back the multiples of 30. The signs alternate: single sets with a plus, pairs with a minus, triples with a plus.

The sizes of the sets: an element of two sets is counted twice here, an element of three sets three times.

The pairwise intersections remove the double counting, but elements of all three sets are subtracted three times.

We add them back. Now every element of the union is counted exactly once.

Example: $500 + 333 + 200 - 166 - 100 - 66 + 33 = 734$. The number of multiples of $d$ among the numbers from 1 to $N$ is $\lfloor N/d \rfloor$, and “divisible by both 2 and 3” means “divisible by $\operatorname{lcm}(2, 3) = 6$”.

Worked examples

Example 1. A team and a podium

A class has 25 pupils. In how many ways can three be chosen for a maths competition? We take some, order doesn’t matter (a trio is a trio), no repeats: combinations, $\binom{25}{3} = \frac{25 \cdot 24 \cdot 23}{3 \cdot 2 \cdot 1} = \frac{13{,}800}{6} = 2300$.

And if we need to choose a class president, a deputy and a treasurer? The posts are different, so swapping two people gives a different option. Order matters: $P(25, 3) = 25 \cdot 24 \cdot 23 = 13{,}800$. Exactly $3! = 6$ times as many.

Example 2. Anagrams of MATHEMATICS

There are 11 letters: two M’s, two A’s, two T’s, and the rest appear once each. If all the letters were different, there would be $11! = 39{,}916{,}800$ permutations. Each genuine word is counted $2! \cdot 2! \cdot 2! = 8$ times, so

$$\frac{11!}{2!\,2!\,2!} = \frac{39{,}916{,}800}{8} = 4{,}989{,}600.$$

A check another way: choose places for the two M’s, $\binom{11}{2} = 55$; then for the two A’s among the remaining nine, $\binom{9}{2} = 36$; for the T’s, $\binom{7}{2} = 21$; and the five different letters go into the last five places in $5! = 120$ ways. $55 \cdot 36 \cdot 21 \cdot 120 = 4{,}989{,}600$.

Example 3. Even three-digit numbers from the digits 0, 1, 2, 3, 4, 5 without repetition

Zero gets in the way twice: it can’t come first, but it can come last and make the number even. So let’s split into two cases.

The last digit is 0. Then the first is any of the other five, and the middle is any of the four left: $5 \cdot 4 = 20$.

The last digit is 2 or 4. The first digit is neither zero nor the last digit: 4 options. The middle is any of the four remaining (now zero is allowed): $4 \cdot 4 \cdot 2 = 32$.

The cases don’t overlap, so we add: $20 + 32 = 52$. If you skip the cases and write $5 \cdot 4 \cdot 3$ straight away, the answer is wrong: how many options remain for the first digit depends on whether zero has taken the last place.

Example 4. After-school clubs

A class has 30 pupils; 18 go to football, 15 to chess, and 7 to both. How many go to neither? At least one club is attended by $18 + 15 - 7 = 26$ pupils: otherwise we’d count the seven who go to both twice. So $30 - 26 = 4$ go to neither. A Venn diagram shows it at once: 11 only at football, 8 only at chess, 7 in the overlap and 4 outside, 30 in all.

Common mistakes

Combinations instead of arrangements, and vice versa. Before counting, swap two of the chosen ones. If something changed, order matters.
The product rule where a sum is needed. “Go by train (3 services) or by plane (2 flights)” is $3 + 2$, not $3 \cdot 2$. You multiply when you make the first choice and the second; you add when it’s one or the other.
Forgetting about zero in numbers made of digits. A three-digit number doesn’t start with zero. And if there’s a condition on the last digit, you almost always have to split into cases.
Dividing by $k!$ “just in case”. Divide only when the same option really has been counted $k!$ times. In a problem about a four-digit code there’s nothing to divide by: 1234 and 4321 are different codes.
Identical versus different items. Identical sweets into boxes is stars and bars; different postcards give $k^n$.
Adding the sizes of overlapping sets. If an object can have two properties at once, simple addition counts it twice: you need inclusion–exclusion.