Counting Principles, Permutations, and Combinations

Intuition

Every counting problem you have solved so far was solved by building. Make the first decision, then the second, then the third, and multiply the number of ways to make each one, as long as that number of ways stays the same no matter what came before. That method works perfectly as long as each thing you are counting gets built exactly once. But the moment order stops mattering, the building goes wrong in a very specific way. If you seat three friends in three chairs you get six seatings. Yet if you only want to know who is in the room, all six of those seatings are the same answer, counted six times over. Nothing about the building was wrong. It simply counted each answer six times instead of once, so the repair is not a new construction, it is a division. That one move, count the ways and then divide by how many times you counted each thing, is what turns a permutation into a combination. That one move is the engine of this entire lesson.

Learning goals

Multiply stage counts that stay fixed no matter the earlier choices, or add across non-overlapping cases
Ask whether order matters and whether repeats are allowed before choosing a formula
Compute $P(n,k)$ as a product of exactly $k$ factors
Divide by $k!$ to forget the order, giving $\dbinom{n}{k}$
Correct for repeated objects by dividing out their type factorials, to count arrangements like MISSISSIPPI
Count the unwanted and subtract, for at least one

The multiplication principle

Start with a small case. A diner offers $4$ soups and $3$ sandwiches, and a lunch is one soup with one sandwich. Pick a soup any of $4$ ways. Whichever one you pick, all $3$ sandwiches are still on offer, so that choice leads to $3$ lunches, and the same is true for every soup. Four soups, each starting $3$ lunches of its own, and no lunch started twice, gives

4 \times 3 = 12 \text{ lunches}.

Now add a third stage, $2$ drinks. Whichever soup and sandwich you already picked, both drinks are still on offer, so each of the $12$ soup-and-sandwich combinations leads to $2$ full lunches. The same move that turned $4$ into $4 \times 3$ now turns $12$ into $12 \times 2 = 24$ , because the number of drinks on offer never depends on which soup or sandwich came before it. Add a fourth stage and the same move repeats again. That repeated stacking, one stage at a time, is the whole idea behind counting by stages. State it precisely enough to use in harder cases, because the precision is what lets it survive when a careless version fails.

The multiplication principle. Suppose each object you want to count is built by a sequence of $k$ decisions. Suppose decision $i$ can be made in $n_i$ ways no matter how the earlier decisions came out. Suppose finally that different sequences of decisions build different objects, and that every object is built by exactly one sequence. Then the number of objects is

n_1 \times n_2 \times \cdots \times n_k.

Read the hypothesis carefully, because the whole lesson leans on it. It says the number of options at each stage must not depend on the earlier choices. It does not say the options themselves must stay the same. When you seat people in chairs, which people remain for the second chair depends entirely on who took the first. But how many remain does not change with who took the first: it is always one fewer. That distinction is what makes permutations legal, and it is why “the choices are independent” undersells the rule: the choices themselves can depend on the past, as long as their number does not.

One companion rule handles problems that break into cases instead of stages. If the objects you want split into groups that overlap nowhere and leave nothing out, then the total is the sum of the group counts. That is the addition principle. A sequence of decisions multiplies (“this and then that”), while a split into separate cases adds (“either this kind or that kind”). Splitting a $2$ -digit number’s tens digit into ” $1$ through $4$ ” or ” $5$ through $9$ ” is one addition-principle split; if the cases instead shared a value, such as “even” and “under $6$ ” (both true of $2$ ), simply adding their counts would count that shared value twice.

Check your understanding

A school offers $5$ elective classes in the morning session and $6$ elective classes in the afternoon session, and no elective meets in both sessions. A student picks exactly one elective. How many electives can the student choose from?

11

30

5

6

The simplest use of the multiplication principle is the one where nothing changes between stages. Suppose you fill $k$ slots, and each slot freely takes any of $n$ values, with repetition allowed. Then every stage offers the same $n$ options, and the product collapses to a power:

\underbrace{n \times n \times \cdots \times n}_{k \text{ slots}} = n^k.

A four-digit PIN has $10^4 = 10{,}000$ settings, and a string of $k$ letters drawn from a $26$ -letter alphabet has $26^k$ possibilities. In both cases a digit or a letter can be reused as often as you like.

Permutations, or filling slots without repetition

Now forbid repetition. An arrangement, or permutation, of $k$ objects chosen from $n$ distinct objects is a way of filling $k$ ordered slots using each object at most once. Write $P(n, k)$ for how many there are.

Fill the slots left to right. The first slot accepts any of the $n$ objects. Whatever you put there is gone, so the second slot accepts any of the remaining $n - 1$ . The third accepts $n - 2$ , and so on. The counts shrink by one at every step, and the multiplication principle applies because the number remaining is the same no matter which particular objects were used up. By the time you reach the $k$ -th slot you have already placed $k - 1$ objects, so it accepts $n - (k-1) = n - k + 1$ of them:

P(n, k) = n(n-1)(n-2)\cdots(n-k+1).

Filling k ordered slots from n distinct objects. Each object placed is used up, so the counts drop by one. There are exactly k factors, and the last is n - k + 1 because k - 1 objects are already gone by the time the final slot is filled.

Count the factors, since this is where the formula is usually mangled. There is one factor per slot, so there are $k$ of them, and they run $n, n-1, \ldots$ down to $n-k+1$ . For $P(9, 4)$ that is four factors, $9 \times 8 \times 7 \times 6$ , stopping at $9 - 4 + 1 = 6$ and not at $5$ .

What the factorial counts. Set $k = n$ and you are arranging all $n$ objects, using every one of them:

P(n, n) = n(n-1)(n-2)\cdots 1 = n!.

You met $n!$ in the binomial theorem lesson as a piece of notation. This is what it counts: the number of ways to put $n$ distinct objects in a row. Five books have $5! = 120$ orders, and ten books have $10! = 3{,}628{,}800$ of them.

The closed form. The product $n(n-1)\cdots(n-k+1)$ is the top of a factorial with its tail chopped off, so put the tail back by multiplying and dividing by $(n-k)!$ :

P(n, k) = \frac{n(n-1)\cdots(n-k+1) \times (n-k)(n-k-1)\cdots 1}{(n-k)(n-k-1)\cdots 1} = \frac{n!}{(n-k)!}.

The numerator is now the full factorial $n!$ , and the denominator cancels precisely the factors you did not want. So

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

Why $0! = 1$ is forced. The cancellation above needs the tail $(n-k)(n-k-1)\cdots 1$ to be an honest product of positive whole numbers, so it only works for $k < n$ . The case $k = n$ , arranging every object, is the one it misses. The slot count there is not in doubt: $P(n,n) = n!$ . If one closed form is to cover that case too, it must return $n!$ there as well, and the closed form reads $n!/(n-n)! = n!/0!$ at $k = n$ . Setting the two equal, $n! = n!/0!$ , leaves exactly one possible value:

0! = 1.

The value is not picked for convenience: it is the only one under which the formula and the slot count agree. It also matches what a factorial means. Since $n!$ counts the arrangements of $n$ objects, $0!$ should count the arrangements of $0$ objects, and there is exactly one, the empty arrangement in which you place nothing. (The binomial theorem lesson used $0! = 1$ for the same reason, to keep its own formula correct at the edges.)

Worked example 1 Count the license plates

A plate shows three letters followed by three digits. The letters must all be different, but the digits may repeat. How many plates are possible?

Treat the six characters as six stages and watch which counts shrink. The letters cannot repeat, so the letter stages offer $26$ , then $25$ , then $24$ options. The digits may repeat, so every digit stage keeps all $10$ options.

26 \times 25 \times 24 \times 10 \times 10 \times 10.

The letters contribute $P(26, 3) = 26 \times 25 \times 24 = 15{,}600$ and the digits contribute $10^3 = 1{,}000$ , so

15{,}600 \times 1{,}000 = 15{,}600{,}000.

There are $15{,}600{,}000$ plates. The single question that decided every stage count was whether a character may be reused. Shrink the count when it may not, hold it fixed when it may.

Worked example 2 Line up 4 of 9 books

Nine different books sit in a box, and four of them will stand in a row on a shelf. How many different shelves are possible?

The shelf is ordered, since swapping two books produces a visibly different shelf, and no book can appear twice. That is a permutation of $4$ objects chosen from $9$ , so fill four slots with shrinking counts:

P(9, 4) = 9 \times 8 \times 7 \times 6 = 3{,}024.

The closed form gives the same number, and it is worth seeing the cancellation once:

P(9, 4) = \frac{9!}{(9-4)!} = \frac{9!}{5!} = \frac{9 \times 8 \times 7 \times 6 \times 5!}{5!} = 3{,}024.

In practice never expand $9!$ in full. Cancel $5!$ first and only four factors survive, which is the shrinking product you started with.

Check your understanding

A club of $10$ members elects a president, a secretary, and a treasurer, and no member may hold two offices. In how many ways can the three offices be filled?

720

120

1000

30

Combinations, or forgetting the order

A permutation cares about order. Very often you do not. A committee of three is the same committee however you list its members, and a hand of cards is the same hand however it was dealt. A set of three chosen factors is the same set however you name them. What you want to count then is not an ordered list but a set.

Notation. For $0 \le k \le n$ , the symbol $\binom{n}{k}$ , read ” $n$ choose $k$ ”, is the number of $k$ -element subsets of an $n$ -element set. This is not a new symbol. In the binomial theorem lesson it counted the ways to choose which $k$ of the $n$ factors of $(x+y)^n$ donate their $y$ . And a choice of factors is nothing more than a set of $k$ factors picked out of $n$ . Same act, same count, same number. What is new here is a way to compute it directly.

The tool that computes it directly is the mirror image of the multiplication principle: start from a count you already know, then divide away the overcounting.

Start from a small case. Choose $3$ letters from $\{A, B, C, D\}$ , filling $3$ ordered slots without repeats: there are $P(4,3) = 4 \times 3 \times 2 = 24$ ordered lists. But the six lists ABC, ACB, BAC, BCA, CAB, and CBA all name the same set, $\{A, B, C\}$ : they differ only in the order the letters were written down. The same is true of every $3$ -letter set drawn from these four letters, so the $24$ ordered lists split evenly into groups of $6$ .

The 24 ordered lists of 3 letters chosen from A, B, C, D, sorted by which set of letters they use. Every set appears exactly 3! = 6 times, once per ordering, so the number of sets is 24 divided by 6, which is 4.

\binom{4}{3} = \frac{24}{6} = 4.

That is the pattern behind every combination count: build the ordered version first, since you already know how to count that, then divide by however many orders share one unordered result.

The division principle. Suppose a procedure produces $N$ outputs in total, and suppose every output is produced by exactly one object. Suppose also that every object you actually want to count is produced exactly $d$ times, with the same $d$ for every object. Then the number of objects is $N / d$ .

Why an even overcount can simply be divided away#

Sort the $N$ outputs into piles, putting two outputs in the same pile exactly when they came from the same object. Every output lands in exactly one pile, since it came from exactly one object, so the piles overlap nowhere and together hold all $N$ outputs.

By hypothesis each object is produced exactly $d$ times, so each pile holds exactly $d$ outputs. Let $M$ be the number of piles, which is the number of objects. Counting the outputs pile by pile gives $M$ groups of $d$ , so $N = M \times d$ , and therefore $M = N / d$ .

The requirement that $d$ be the same for every object is the whole content of the rule. If some objects were produced twice and others three times, the piles would be uneven and no single division could repair the count.

Now count $\binom{n}{k}$ in general, the same way the $4$ -letter example did it: count the ordered lists two different ways.

The direct count of $\binom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$ #

Fix $n$ and $k$ with $0 \le k \le n$ , and count the ordered lists of $k$ distinct objects drawn from the $n$ available, twice.

First count: fill the slots. A list is $k$ ordered slots filled without repetition, so by the shrinking slot argument there are $P(n, k) = n!/(n-k)!$ lists in all.

Second count: choose, then order. Build the same list in two stages instead. First choose the set of $k$ objects that will appear in it, which by definition can be done in $\binom{n}{k}$ ways. Then choose the order in which to write that set out, which is an arrangement of $k$ distinct objects in $k$ slots, so it can be done in $P(k, k) = k!$ ways.

The multiplication principle applies to these two stages, because the second stage offers $k!$ orders no matter which set the first stage produced. And the two stages build every list exactly once. Each list determines its own set (its entries) and its own order (how they are written), so no list is built twice and none is missed. Hence the number of lists is also $\binom{n}{k} \times k!$ .

Equate the two counts. The same lists were counted both times, so

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

and dividing by $k!$ isolates the number we wanted:

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

Look at what the division did. Every set of $k$ objects was built $k!$ times, once for each order in which its members could be listed. Dividing by $k!$ collapses those $k!$ lists back into the single set they all describe. Dividing by $k!$ is the act of forgetting the order. That sentence is the difference between a permutation and a combination, and there is nothing else to it. It is exactly what the $4$ -letter example above did by hand: $24$ ordered lists, divided by the $6$ orders each set was written in, giving $4$ sets.

Two facts drop out for free. Choosing which $k$ objects to take is the same act as choosing which $n - k$ objects to leave, so $\binom{n}{k} = \binom{n}{n-k}$ . The formula agrees because swapping $k$ with $n-k$ just swaps the two factorials in the denominator. And at the edges, $\binom{n}{0} = \binom{n}{n} = 1$ , since there is one way to take nothing and one way to take everything. The formula produces those $1$ ‘s only because $0! = 1$ , which is the same forcing you saw a moment ago.

Here is the whole scheme on one page. Suppose you make $k$ picks from $n$ objects.

The $k$ picks are	Repetition	How many ways
ordered	allowed	$n^k$
ordered	not allowed	$P(n,k) = \dfrac{n!}{(n-k)!}$
unordered	not allowed	$\dbinom{n}{k} = \dfrac{n!}{k!\,(n-k)!}$

The missing fourth row, unordered picks with repetition allowed, needs a tool this lesson does not build, so leave it for a later course. The three rows above answer nearly everything. The two questions you must answer before choosing a row are whether rearranging your picks changes the outcome, and whether an object may be used twice. Neither question settles the row by itself. The first two rows are both ordered, so the order question alone leaves you stuck between them, and only the repetition question tells them apart.

Worked example 3 Choose a delegation of 5 from a club of 12

A club of $12$ members sends $5$ delegates to a conference. The delegates have no titles and no ranks, so the delegation is just a set of five people. How many delegations are possible?

Rearranging the same five people gives the same delegation, so order does not matter and this is $\binom{12}{5}$ . Use the closed form, canceling $7!$ against the tail of $12!$ before multiplying anything:

\binom{12}{5} = \frac{12!}{5!\,7!} = \frac{12 \times 11 \times 10 \times 9 \times 8}{5 \times 4 \times 3 \times 2 \times 1}.

Five factors on top counting down from $12$ , and $5!$ underneath. The numerator is $95{,}040$ and the denominator is $120$ :

\binom{12}{5} = \frac{95{,}040}{120} = 792.

There are $792$ delegations. Had the five delegates instead been given five distinct jobs, the answer would have been $P(12,5) = 95{,}040$ , which is exactly $120$ times larger. That factor of $120$ is one for each of the $5!$ ways to hand out the jobs to a fixed set of five people.

Check your understanding

The same club of $10$ members instead sends a committee of $3$ members, with no offices and no ranks. How many committees are possible?

720

120

30

1000

Worked example 4 Build a committee with a required mix

A department has $7$ women and $5$ men, and it must form a committee of $3$ women and $2$ men. How many committees are possible?

Break the build into two stages, choosing the women and then the men. Neither group is ordered, so each stage is a combination:

\binom{7}{3} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35, \qquad \binom{5}{2} = \frac{5 \times 4}{2 \times 1} = 10.

The multiplication principle now applies, because whichever three women are chosen, there are still $10$ ways to choose the men:

35 \times 10 = 350.

There are $350$ committees. Notice that the two stages multiply even though each stage was itself computed by a division. Combinations are ordinary numbers once you have them, and they slot into the multiplication principle like any other stage count.

Arranging objects that are not all distinct

The permutation formula assumed every object was distinguishable. Real problems break that assumption constantly, and the repair is the division principle again.

How many distinguishable arrangements does the word BANANA have? If the six letters were all different the answer would be $6! = 720$ , but they are not. There are three A’s and two N’s, and swapping two A’s produces the identical string. So $720$ is an overcount, and the question is by how much.

Arrangements of $n$ objects with repeats#

Suppose $n$ objects come in $r$ types, with $n_1$ copies of the first type, $n_2$ of the second, and so on up to $n_r$ , where $n_1 + n_2 + \cdots + n_r = n$ . Copies of the same type are identical. We count the distinguishable arrangements.

Tag the copies to make them temporarily distinct: call the three A’s of BANANA $A_1, A_2, A_3$ . All $n$ tagged objects are now different, so they have $n!$ arrangements.

Group those $n!$ tagged arrangements by the untagged word they produce. Two tagged arrangements produce the same word exactly when they place the same type in the same positions. Two arrangements that produce the same word differ only in how the tags are distributed among the positions of each type. For a fixed word, the tags of type $1$ can be scattered over its $n_1$ positions in $n_1!$ ways. The tags of type $2$ can be scattered over the word’s $n_2$ positions in $n_2!$ ways, and so on. Placing one type’s tags does not change how many ways the next type’s tags can be placed, so by the multiplication principle each word arises from exactly

n_1! \times n_2! \times \cdots \times n_r!

tagged arrangements. That number is the same for every word, since it depends only on the type counts.

The division principle now applies with $N = n!$ and $d = n_1!\,n_2!\cdots n_r!$ , so the number of distinguishable arrangements is

\frac{n!}{n_1!\,n_2!\,\cdots\,n_r!}.

For BANANA, $n = 6$ with three A’s, two N’s, and one B:

\frac{6!}{3!\,2!\,1!} = \frac{720}{6 \times 2 \times 1} = \frac{720}{12} = 60.

Sixty arrangements, not $720$ . Divide by the factorials of the repeat counts, not by the repeat counts themselves: the three A’s contribute $3! = 6$ , not $3$ .

This formula quietly contains the binomial coefficient. Take just two types, $k$ objects of one kind and $n - k$ of the other, say $k$ letters Y and $n-k$ letters X. The count of arrangements is

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

which is no coincidence at all. Arranging $k$ Y’s and $n-k$ X’s in a row is precisely choosing which $k$ of the $n$ positions hold a Y. Back in the binomial theorem those positions were the factors of $(x+y)^n$ that donate their $y$ . The same number keeps answering the same question in different clothes.

Worked example 5 Arrange the letters of MISSISSIPPI

The word MISSISSIPPI has $11$ letters. How many distinguishable arrangements are there?

Count the letters by type first, and check that the counts add to $11$ :

\text{M} \times 1, \qquad \text{I} \times 4, \qquad \text{S} \times 4, \qquad \text{P} \times 2, \qquad 1 + 4 + 4 + 2 = 11.

Had all $11$ letters been different there would be $11!$ arrangements. Each actual word is produced $1! \times 4! \times 4! \times 2!$ times by the tagged letters, so divide:

\frac{11!}{1!\,4!\,4!\,2!} = \frac{39{,}916{,}800}{1 \times 24 \times 24 \times 2} = \frac{39{,}916{,}800}{1{,}152}.

Carry out the division:

\frac{39{,}916{,}800}{1{,}152} = 34{,}650.

There are $34{,}650$ arrangements. The $1!$ for the single M is harmless, since $1! = 1$ , but writing it down is a cheap way to make sure the type counts really do add up to $11$ .

Check your understanding

How many distinguishable arrangements are there of the letters in the word LETTER?

720

360

180

90

Complementary counting

Some sets are far easier to count by counting what you do not want. If every object either has a property or fails to have it, then those two cases overlap nowhere and cover everything. So the addition principle says the two counts add to the total. Rearranged, that is complementary counting:

(\text{objects with the property}) = (\text{all objects}) - (\text{objects without it}).

The flagship case is at least one. The opposite of “at least one” is “none”. And “none” is usually a single clean count, while “at least one” splits into a pile of cases (exactly one, exactly two, exactly three, and so on). Counting the total and subtracting the “none” case replaces all of that work with one subtraction.

It is also a guard against a specific and very common error. Faced with “at least one woman on the committee”, the tempting move is to appoint one woman first, then fill the rest of the committee freely. That method builds a committee with two women twice, once for each woman it could have appointed first. The division principle cannot repair the damage, because committees with three women are built three times and the overcount is uneven. The next example shows the two answers side by side.

Worked example 6 At least one woman on the committee

A committee of $4$ is chosen from $6$ men and $5$ women. How many committees contain at least one woman?

The group has $11$ people in total, and a committee is an unordered set of $4$ , so there are

\binom{11}{4} = \frac{11 \times 10 \times 9 \times 8}{4 \times 3 \times 2 \times 1} = \frac{7{,}920}{24} = 330

committees in all. The committees without a woman are made entirely of the $6$ men:

\binom{6}{4} = \frac{6 \times 5 \times 4 \times 3}{4 \times 3 \times 2 \times 1} = 15.

Every committee either has at least one woman or has none, never both, so subtract:

330 - 15 = 315.

There are $315$ committees with at least one woman.

Now watch the tempting method fail. Appoint one of the $5$ women, then fill the remaining $3$ seats from the other $10$ people, giving $5 \times \binom{10}{3} = 5 \times 120 = 600$ . That is nearly double the truth, because a committee holding the women Ana and Bea is produced twice. That committee is produced once by appointing Ana first and once by appointing Bea first, while a committee holding three women is produced three times. The overcount is uneven, so no single division fixes it. Subtracting the complement never runs into this problem.

Check your understanding

A coin is flipped $6$ times, giving $2^6 = 64$ possible sequences of heads and tails. In how many of them does at least one head appear?

64

32

63

6

Common mistakes

Never asking whether order matters. This is the error that produces more wrong answers than every other error in counting combined. Ten people can shake hands in $\binom{10}{2} = 45$ ways but can fill a president and a vice-president post in $P(10,2) = 90$ ways. The difference is that a handshake is a set and an election result is an ordered pair. Decide first whether rearranging your picks changes the outcome, and only then reach for a formula.
Dividing by $k!$ when the order does matter. The $k!$ divides out the orderings of a chosen set. If the $k$ picks land in genuinely different roles (first prize and second prize, chair and secretary), those orderings are different outcomes and must not be divided away.
Using $n^k$ where objects cannot repeat, or a shrinking product where they can. Digits in a PIN may repeat, so a four-digit PIN has $10^4$ settings. Runners on a podium cannot repeat, so three medals from eight runners give $8 \times 7 \times 6$ . Both of those counts are ordered, so asking about the order will not tell them apart. You have to ask the second question as well, whether an object may be used twice.
Dividing by the repeat count instead of its factorial. BANANA has three A’s and two N’s, so the count is $6!/(3!\,2!) = 60$ . Dividing $6!$ by $3 \times 2 = 6$ gives $120$ , which counts nothing.
Handling “at least one” by reserving one in advance. Choosing a guaranteed woman and then filling the rest of the committee freely counts every committee once for each woman it could have started with. So committees with several women are counted several times. Use total minus none.
Miscounting the factors in $P(n,k)$ . There are exactly $k$ factors, running from $n$ down to $n-k+1$ . For $P(9,4)$ that is $9 \times 8 \times 7 \times 6$ , which stops at $6$ , not at $5$ .

Key takeaways

The multiplication principle: suppose an object is built by $k$ decisions, and suppose decision $i$ can be made in $n_i$ ways regardless of the earlier decisions. Then the number of objects is $n_1 n_2 \cdots n_k$ . The number of options at each stage must not depend on the past; the options themselves may.
The addition principle: if the objects split into cases that overlap nowhere and miss nothing, add the case counts.
Repetition allowed: $k$ slots each taking any of $n$ values give $n^k$ outcomes.
Two questions choose the formula, and neither is enough on its own: does rearranging the picks change the outcome, and may an object be used twice?
Permutations (order matters, no repeats): $P(n,k) = n(n-1)\cdots(n-k+1) = \dfrac{n!}{(n-k)!}$ , a product of exactly $k$ factors. Arranging all $n$ objects gives $P(n,n) = n!$ , which is what the factorial counts.
$0! = 1$ is forced, not chosen: it is the one value that keeps $P(n,k) = n!/(n-k)!$ correct at $k = n$ , and it matches the single empty arrangement of $0$ objects.
The division principle: if a procedure produces $N$ outputs, each output comes from exactly one object, and every object is produced exactly $d$ times, then there are $N/d$ objects.
Combinations (order does not matter): $\dbinom{n}{k} = \dfrac{P(n,k)}{k!} = \dfrac{n!}{k!\,(n-k)!}$ , because each set of $k$ objects was listed $k!$ times. Dividing by $k!$ is the act of forgetting the order, and this is the same $\dbinom{n}{k}$ that gave the binomial coefficients.
Objects that are not all distinct: $n$ objects in types of sizes $n_1, \ldots, n_r$ have $\dfrac{n!}{n_1!\,n_2!\cdots n_r!}$ distinguishable arrangements, as in $\dfrac{6!}{3!\,2!\,1!} = 60$ for BANANA.
Complementary counting: count the objects you do not want and subtract, which is nearly always the way to handle at least one.

Practice

Multiple Choice Questions (MCQ)

Progressively harder sets of questions. Each opens on its own page.

Level 1 Foundational 12 questions Start → Level 2 Intermediate 12 questions Start → Level 3 Challenge 12 questions Start →

Core practice

Practice problems at the level of the course, to be worked out on paper. Hints one at a time, then the answer or the full worked solution, with your progress kept in this browser.

More practice (optional)

Extra sets, as hard as the Challenge set. Each one opens on its own page.

More resources (optional)

Other explanations of this lesson, if you want a second take.

Counting, permutations, and combinations (Khan Academy)
Combinations and permutations (Math is Fun)
Counting principles (OpenStax)
Combination (Art of Problem Solving)

Go deeper (optional)

You can skip this and keep going. Read it if you want to know more.

Why a sequence of fixed-count decisions multiplies, proved by induction on the number of stages

The soup, sandwich, and drink example showed the pattern by hand for three stages. This is the same argument made once and for all, for any number of stages $k$ .

Why a sequence of fixed-count decisions multiplies#

Add the stages one at a time. With a single decision the count is $n_1$ , which is the claim for $k = 1$ .

Now suppose the first $k-1$ decisions produce exactly $N = n_1 n_2 \cdots n_{k-1}$ different partial objects, and bring in the last decision. Each of those $N$ partial objects can be finished in exactly $n_k$ ways, since that is the hypothesis. The hypothesis says the number of options at the last stage does not depend on what came before it.

Those completions are all different, and for two separate reasons. Two completions of the same partial object differ in the final decision, so they are different. Two completions of different partial objects already differed before the final decision was made, so they are different too. And nothing is missed: any finished object comes from exactly one partial object, namely its own first $k-1$ decisions, followed by one last decision.

So the finished objects fall into $N$ groups of $n_k$ , one group per partial object, and the total is $N \times n_k = n_1 n_2 \cdots n_k$ . Since each new stage multiplies the running total by its own option count, the product formula holds for every $k$ .

A bit of history (optional)

European gamblers had mostly solved each game by its own trick, one problem at a time, though the Italian mathematician Gerolamo Cardano had already worked out odds for several dice games a century earlier, in a manuscript that stayed unpublished until 1663. In 1654 Blaise Pascal took the idea further: he worked out general properties of $\binom{n}{k}$ and applied them to fairly splitting a gambler’s interrupted stake, among other problems. His findings became the Treatise on the Arithmetical Triangle, composed and substantially printed in 1654 but not published until 1665, three years after his death.

Gottfried Leibniz, a young German lawyer, gave the field its name at twenty. His 1666 essay De Arte Combinatoria took the art of combinations far beyond dice. He wanted to break every idea into parts and recombine them to reach all possible truths. The essay promised far more than it delivered. The phrase survived anyway, and combinatorics still carries it.

A broader theory came from a Swiss professor named Jacob Bernoulli. His Ars Conjectandi was printed in 1713, eight years after he died. Its second part walks through permutations and combinations in general, proving the rules rather than collecting them case by case.

Ordinary language never caught up. A combination lock will not open unless you enter its numbers in the one exact order set for it. By the words of this lesson that is not a combination at all: it is an ordered code of length $k$ over $n$ symbols, counted by $n^k$ if a symbol may repeat in the code and by $P(n,k)$ if it may not, but never by $\binom{n}{k}$ . The everyday name has stuck regardless.