Combination calculator (nCr) with step-by-step working

The combination formula

The number of ways to choose $r$ items from $n$ distinct items, ignoring order and without using any item twice, is the binomial coefficient

All four notations mean the same number; textbooks and calculators use whichever is easiest to type. It is read “$n$ choose $r$”. The exclamation mark is the factorial: $n! = n \times (n-1) \times \cdots \times 2 \times 1$, with $0! = 1$.

Why the formula works

Start by counting ordered selections. There are $n$ ways to pick the first item, $n-1$ for the second, and so on, which gives $n!/(n-r)!$ ordered lists: the permutations $P(n, r)$. A combination is one of these lists with the order forgotten. Each set of $r$ items can be put in order in $r!$ ways, so every combination was counted $r!$ times. Dividing gives the formula:

Step 2 is the trick for calculating by hand: never compute the large factorials. Keep only the top $r$ factors of $n!$ and divide by $r!$. The calculator does the same, and it uses the symmetry $\binom{n}{r} = \binom{n}{n-r}$ first when that gives a shorter product, so $C(100, 97)$ is worked as $C(100, 3)$.

Combination or permutation?

Ask one question: would rearranging the chosen items give a different outcome?

The same objects can fall on either side depending on the question. Three people chosen from ten form $\binom{10}{3}$ groups, but if you then line them up for a photo, each group gives $3! = 6$ photos.

Combinations with repetition

Tick Repetition allowed when the same kind can be chosen more than once and only how many of each you take matters: six donuts from four flavours, or three coins from pennies, nickels and dimes. The answer is

The reason is the stars and bars picture. Write the $r$ chosen items as stars and separate the $n$ kinds with $n-1$ bars: ★★|★||★★★ means two of the first flavour, one of the second, none of the third and three of the fourth. Every selection is one such row of $n + r - 1$ symbols, and a row is fixed once you choose which $r$ of the positions hold stars. For six donuts from four flavours that gives $\binom{9}{6}$ = 84 different boxes.

Common combination problems

Lottery odds

In a 6-from-49 lottery the order the balls are drawn in doesn’t matter, so there are $\binom{49}{6}$ = 13,983,816 possible tickets. One ticket wins the jackpot with probability 1 in 13,983,816. Try it with the “Lottery” example above.

Card hands

A five-card hand from a standard deck: $\binom{52}{5}$ = 2,598,960. To count hands with at least one ace, count the complement: hands with no ace come from the 48 other cards, so the answer is $\binom{52}{5} - \binom{48}{5}$ = 886,656. Subtracting the complement is almost always easier than adding up “exactly one, exactly two, …”.

Choosing from two groups

A class has 6 girls and 5 boys. A team of two girls and two boys can be picked in $\binom{6}{2} \times \binom{5}{2}$ = 150 ways, by the product rule. A team of 4 with at least one boy: $\binom{11}{4} - \binom{6}{4}$ = 315.

Subsets

Twelve toppings and you want exactly three: $\binom{12}{3}$ = 220 pizzas. Any number of toppings at all: $2^{12} = 4096$, because each topping is independently in or out. Summing $\binom{12}{r}$ over every $r$ gives the same 4096, which is the row-sum identity of Pascal’s triangle.

Useful identities

• Symmetry: $\binom{n}{r} = \binom{n}{n-r}$. Choosing what to take is choosing what to leave.
• Pascal’s rule: $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$, the addition rule of Pascal’s triangle.
• Row sum: $\sum_{r=0}^{n} \binom{n}{r} = 2^n$, the number of subsets of an $n$-element set.
• Edge cases: $\binom{n}{0} = \binom{n}{n} = 1$, and $\binom{n}{r} = 0$ when $r > n$.
• Binomial theorem: $(x+y)^n = \sum_{r} \binom{n}{r} x^r y^{n-r}$, which is where the name “binomial coefficient” comes from.

How the calculator works

Everything runs in your browser with JavaScript’s BigInt, so results are exact integers with no rounding. To avoid ever building a huge factorial, it multiplies and divides alternately: after step $i$ the running value is exactly $\binom{n-r+i}{i}$, which is always a whole number, so every division is exact. Values with ten or more digits are also shown in scientific notation, and the page address updates as you type so you can bookmark or share a calculation.

For the theory behind the four basic counting formulas, with Pascal’s triangle drawn interactively, see permutations, combinations and Pascal’s triangle. For ordered selections, use the permutation calculator.

References

1. R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994. Chapter 5, “Binomial coefficients”.
2. K. H. Rosen, Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019. Sections 6.3 and 6.5.
3. “Combination”, Wikipedia.