Permutations and Combinations Explained

The fundamental counting principle

Counting problems ask how many ways something can happen. The foundation is the fundamental counting principle: if one choice can be made in $m$ ways and a second, independent choice in $n$ ways, the two together can be made in $m \times n$ ways. The idea extends to any number of stages.

If you own 3 shirts, 4 pairs of trousers and 2 pairs of shoes, you can make $3 \times 4 \times 2 = 24$ different outfits. A four-digit PIN using the digits 0 to 9, with repeats allowed, has $10 \times 10 \times 10 \times 10 = 10^4 = 10{,}000$ possibilities. Every formula in this article is a shortcut for this multiplication, so when a problem feels unfamiliar, going back to stage-by-stage counting is always a safe fallback.

Factorials

Arranging all $n$ distinct objects in a row gives $n$ choices for the first position, $n - 1$ for the second, and so on down to 1. This product is called $n$ factorial:

So $5! = 120$: five books can be lined up on a shelf in 120 orders. By definition $0! = 1$, which keeps the formulas below consistent, since there is exactly one way to arrange nothing. Factorials grow astonishingly fast: $10! = 3{,}628{,}800$, and a shuffled deck of cards has $52!$ possible orders, a number with 68 digits.

Permutations: order matters

A permutation is an ordered arrangement of $r$ objects chosen from $n$ distinct objects. Because order matters, first-second-third is different from third-second-first. The number of permutations is

Arranging people around a circular table is a special case. Rotating everyone one seat gives the same arrangement, so $n$ people can be seated in $(n-1)!$ distinct ways. Six people around a round table have $5! = 120$ arrangements, not 720.

Combinations: order does not matter

A combination is a selection where only membership counts. Choosing Ana, Ben and Cara for a committee is the same committee in any order. Each group of $r$ objects corresponds to $r!$ permutations, so we divide them out:

Combinations are symmetric: $\binom{n}{r} = \binom{n}{n-r}$, because choosing 3 people to include is the same as choosing 5 to leave out. They are also the entries of Pascal's triangle and the coefficients in the binomial expansion of $(a + b)^n$.

How to tell which one to use

Ask a single question: if I swap two of the chosen items, do I get a different result? If yes, order matters and you need permutations. If no, use combinations.

• Positions, rankings, passwords, seating plans and schedules: permutations.
• Teams, committees, hands of cards, lottery tickets and pizza toppings: combinations.
• Roles inside a group, such as a president and a treasurer, make order matter even though the people come from one pool.

A quick check: the permutation count is always $r!$ times the combination count. If your two answers do not satisfy that relationship, one of them is wrong.

Counting with repetition and repeated letters

When items may be reused, the formulas change. Ordered selections with repetition number $n^r$, as in the PIN example. Unordered selections with repetition, such as choosing 3 scoops of ice cream from 5 flavours where you may repeat a flavour, number

Arranging letters with repeats needs one more adjustment: divide by the factorial of each repeated count, because swapping identical letters changes nothing. The word MISSISSIPPI has 11 letters, with 4 I's, 4 S's and 2 P's, so it has $\frac{11!}{4!\,4!\,2!} = 34{,}650$ distinct arrangements.

Using counting to find probabilities

When outcomes are equally likely, a probability is a count of favourable outcomes divided by a count of all outcomes, so permutations and combinations do most of the work. The basics of that ratio are covered in probability basics.

Card games give more practice. There are $\binom{52}{5} = 2{,}598{,}960$ possible five-card hands. A hand containing all four aces needs only one more card, chosen from the other 48, so the probability is $\frac{48}{2{,}598{,}960} = \frac{1}{54{,}145}$.

Common mistakes

• Using permutations for a team or committee, which overcounts by a factor of $r!$.
• Forgetting that $0! = 1$, which breaks formulas such as $\binom{n}{n}$.
• Ignoring identical items, as in arrangements of letters with repeats.
• Multiplying stages that are not independent without adjusting the later counts.

The permutation and combination calculator evaluates ${}_nP_r$ and ${}_nC_r$ with the factorial steps shown, and the probability calculator turns those counts into probabilities.

Pascal's triangle and subsets

Each entry of Pascal's triangle is the sum of the two entries above it, and row $n$ lists the values $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. Row 4 reads 1, 4, 6, 4, 1, which are exactly the coefficients in $(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$. The rule that builds the triangle is itself a counting fact:

To see why, fix one particular item. Every selection of $r$ items either includes it, leaving $r - 1$ to choose from the other $n - 1$, or excludes it, leaving all $r$ to choose from the other $n - 1$. Adding a whole row gives $2^n$, the total number of subsets of an $n$-item set, since each item is either in or out. A pizza shop with 8 toppings can therefore make $2^8 = 256$ different pizzas, counting the plain one.

Practice problems

1. In how many ways can 4 of 7 different books be arranged on a shelf? Answer: ${}_7P_4 = 7 \times 6 \times 5 \times 4 = 840$.
2. How many ways can you pick 4 toppings from 10? Answer: $\binom{10}{4} = 210$.
3. How many distinct arrangements does BANANA have? Answer: $\frac{6!}{3!\,2!} = 60$.
4. How many five-letter codes can be made from 26 letters if repeats are allowed? Answer: $26^5 = 11{,}881{,}376$.

Frequently asked questions