Counting Principles, Permutations, and Combinations: Free Response

Filling a leg uses up a sprinter, so each leg offers one fewer option than the leg before it, and the multiplication principle applies because that shrinking count does not depend on which particular sprinters were already placed. Filling the four legs in order gives

$P(12,4) = 12 \times 11 \times 10 \times 9.$

Multiplying the four factors in order,

$12 \times 11 = 132, \qquad 132 \times 10 = 1{,}320, \qquad 1{,}320 \times 9 = 11{,}880.$

There are $11{,}880$ ways to fill the relay.

Here every one of the five symbol slots offers all $10$ digits again, because a digit that was already used is still available for the next slot. That is five stages that each contribute the same option count $10$, so

$10 \times 10 \times 10 \times 10 \times 10 = 10^5 = 100{,}000.$

There are $100{,}000$ keypad codes.

The multiplication principle needs one thing at each stage: whatever the earlier decisions were, the number of ways to make the next decision is the same. It says nothing about the options staying the same set.

In the relay, placing a sprinter in one leg removes that sprinter from the pool available to every later leg. The set of sprinters left over does depend on who ran earlier, but the SIZE of that set does not: it is always exactly one smaller than before. That is why the option count shrinks by one at every stage, giving the product $12 \times 11 \times 10 \times 9$.

In the keypad code, using a digit does not remove it. Whatever digits were typed into the earlier slots, the next slot still has all $10$ digits available, so the option count is the constant $10$ at every stage, giving $10^5$. The two products side by side make the difference visible:

$12 \times 11 \times 10 \times 9 \qquad \text{versus} \qquad 10 \times 10 \times 10 \times 10 \times 10.$

So the difference between a shrinking product and a constant power is not about how the counting was carried out, since both were built the same way, slot by slot with the multiplication principle. It comes entirely from a single fact about the situation: whether an object, once used, is available again. That fact is exactly the "repetition allowed or not" question that decides between $P(n,k)$ and $n^k$.

Filling three distinct time slots without repeating a finalist is a permutation of $3$ objects chosen from $7$. Fill the slots one at a time; each slot loses one finalist from the pool available to the next:

$P(7,3) = 7 \times 6 \times 5.$

Multiplying the three factors,

$7 \times 6 = 42, \quad 42 \times 5 = 210.$

There are $210$ ways to schedule the morning.

Now every finalist gets a slot, so $n = 7$ and $k = 7$: this is $P(7,7)$, filling all $7$ slots from all $7$ finalists with none left over.

A permutation that uses every object is exactly what the factorial counts,

$P(7,7) = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 7!.$

Multiplying it out,

$7! = 5{,}040.$

So there are $5{,}040$ full-day schedules.

Start from the closed form with $n = 7$ and $k = 3$:

$P(7,3) = \frac{7!}{(7-3)!} = \frac{7!}{4!}.$

Write $7!$ out far enough to see the cancellation, since $7! = 7 \times 6 \times 5 \times 4!$ and the trailing $4!$ is exactly the denominator:

$\frac{7 \times 6 \times 5 \times 4!}{4!} = 7 \times 6 \times 5 = 210.$

This is the same $210$ found in part A, computed a second way.

Why does the division work out so cleanly? Write $7!$ as the product $7 \times 6 \times 5 \times 4!$, splitting off the last four factors as the single block $4!$, which is by definition $(7-3)!$. The numerator and the denominator then carry the SAME symbol $4!$, not merely two numbers that happen to share a factor, so it cancels to $1$ exactly the way $\frac{x \cdot 4!}{4!}$ cancels to $x$ for any $x$. That is the whole content of the closed form: it is a shortcut for writing down $n!$ and immediately cutting off the tail you never wanted, by naming that tail $(n-k)!$ and dividing it away.

A packet is a set of $6$ problems chosen from $15$, and rearranging the list changes nothing, so this is a combination:

$\binom{15}{6} = \frac{15!}{6!\,9!}.$

Cancel the $9!$ against the tail of $15!$, leaving six factors on top and $6!$ on the bottom:

$\binom{15}{6} = \frac{15 \times 14 \times 13 \times 12 \times 11 \times 10}{6 \times 5 \times 4 \times 3 \times 2 \times 1} = \frac{3{,}603{,}600}{720} = 5{,}005.$

There are $5{,}005$ possible packets.

Build the packet in two independent stages: choose which $4$ of the $9$ algebra problems go in, and choose which $2$ of the $6$ geometry problems go in. Neither stage is ordered, so each is a combination:

$\binom{9}{4} = 126, \qquad \binom{6}{2} = 15.$

Whichever $4$ algebra problems are chosen, there are still $15$ ways to choose the geometry problems, so the multiplication principle applies to the two stages:

$126 \times 15 = 1{,}890.$

There are $1{,}890$ packets with exactly $4$ algebra and $2$ geometry problems.

In part A, a packet is any $6$-element subset of a single pool of $15$ problems, with no restriction on where the problems come from. There is exactly one decision to make, choose $6$ items out of $15$, so it is a single combination.

Part B is different because the requirement, exactly $4$ algebra and $2$ geometry, splits the pool into two separate pools before any choosing happens, and it fixes how many come from each one. Building such a packet is genuinely two decisions: choose the algebra problems, and separately choose the geometry problems. Each decision is itself unordered, so each is a combination, $\binom{9}{4}$ for the first and $\binom{6}{2}$ for the second.

The two decisions are independent in exactly the sense the multiplication principle needs: no matter which $4$ algebra problems were chosen, there are still $\binom{6}{2} = 15$ ways to choose the geometry problems, so the number of options at the second stage does not depend on the outcome of the first. That is why the two combination counts multiply rather than add,

$\binom{9}{4} \times \binom{6}{2} = 126 \times 15 = 1{,}890,$

and it is also why part A never split into stages: with no requirement on where the $6$ problems come from, there was only one pool and only one decision to make.

If all $9$ pots were different there would be $9! = 362{,}880$ orders, but every row here is overcounted, once for each way the identical pots within a herb could be shuffled among themselves without changing what is visible. Divide by the factorial of each repeat count:

$\frac{9!}{3!\,4!\,2!} = \frac{362{,}880}{6 \times 24 \times 2} = \frac{362{,}880}{288} = 1{,}260.$

There are $1{,}260$ distinguishable rows.

The colleague's division removes far too little. Dividing $9!$ by $3 \times 4 \times 2 = 24$ instead of by $3! \times 4! \times 2! = 6 \times 24 \times 2 = 288$ leaves

$\frac{362{,}880}{24} = 15{,}120,$

which is twelve times too large, since $288/24 = 12$.

The reason the raw repeat counts are the wrong divisor is that they undercount how many ways the identical pots within one herb can be shuffled with no visible effect. Three rosemary pots are not interchangeable in $3$ ways, they are interchangeable in $3! = 6$ ways, once for every ordering of the three of them, and every one of those six orderings produces the identical-looking row. The same holds for the $4$ lavender pots ($4! = 24$ internal shuffles) and the $2$ sage pots ($2! = 2$ internal shuffles). The true overcount factor is the product of these, $6 \times 24 \times 2 = 288$, not $3 \times 4 \times 2 = 24$, and dividing by the smaller number leaves most of the overcounting in place. The correct value is $1{,}260$, as found in part A.

Give every one of the $n$ objects a temporary tag so that all $n$ are distinguishable, exactly as the lesson tags the A's in BANANA. With every object now different, there are $n!$ tagged arrangements in total.

Group the $n!$ tagged arrangements by the visible row they produce once the tags are erased. Two tagged arrangements erase to the same visible row exactly when they place the same TYPE in the same position throughout, differing only in which tagged copy of a type sits in which of that type's own positions.

Fix one visible row and count how many tagged arrangements erase to it. The positions holding type $1$ can be filled by the $n_1$ tagged copies of type $1$ in any of their $n_1!$ orders, and every one of those orders erases to the same visible placement of type $1$, since the tags themselves are invisible in the final row. The same holds for type $2$, with $n_2!$ orders, and so on through type $r$. These choices are made independently, one per type, so by the multiplication principle the number of tagged arrangements erasing to this one visible row is

$n_1! \times n_2! \times \cdots \times n_r!.$

This count is the same for every visible row, because it depends only on the type sizes $n_1, \ldots, n_r$, never on which row is being examined. So the division principle applies directly, with $N = n!$ tagged arrangements and $d = n_1!\cdots n_r!$ arrangements per visible row, giving

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

distinguishable rows. The plain product $n_1 n_2 \cdots n_r$ would only be correct if each type's copies could be reordered among their own positions in just $n_i$ ways rather than $n_i!$ ways, and an ordering of $n_i$ tagged copies is itself a permutation of all $n_i$ of them, which is $n_i!$, not $n_i$, exactly as counted for one herb in part B.

Each of the $4$ light positions independently shows any of the $7$ colors, with repetition allowed, so the total count is

$7^4 = 2{,}401.$

A pattern with no color repeated is an ordered choice of $4$ different colors out of $7$, a permutation:

$P(7,4) = 7 \times 6 \times 5 \times 4 = 840.$

Every pattern either repeats a color at least once or it does not, and those two cases overlap nowhere and cover everything, so subtracting gives the count with at least one repeat:

$2{,}401 - 840 = 1{,}561.$

There are $1{,}561$ patterns with at least one repeated color.

The method names one color as "the" repeated color, but a signal pattern is not required to have only one repeated color, and it is not required to repeat a color exactly twice.

Take the pattern red, red, blue, blue. The technician's method builds this pattern once by choosing red as the repeated color, placing it in positions $1$ and $2$, and filling positions $3$ and $4$ with blue and blue. It also builds the exact same pattern a second time by choosing blue as the repeated color, placing it in positions $3$ and $4$, and filling positions $1$ and $2$ with red and red:

$\text{(red chosen)} \to \text{red, red, blue, blue} \quad\text{and}\quad \text{(blue chosen)} \to \text{red, red, blue, blue}.$

Nothing distinguishes these two constructions once the pattern is finished, so this one pattern is counted twice.

A pattern with one color appearing three or four times causes a related problem: choosing that color and only $2$ of its $3$ or $4$ matching positions to be "the repeated pair" can be done in more than one way, so that pattern is counted several times as well, and by a different amount than a pattern with two separately repeated colors. Because different patterns are overcounted by different amounts, there is no single number to divide by afterward, which is exactly the situation the division principle cannot repair.

The complement method in part A never runs into this. It asks a single yes-or-no question, does this pattern repeat a color at all, and the two answers to that question split every pattern into two piles that overlap nowhere.

"No repeats at all" describes one uniform kind of pattern: an ordered choice of $4$ different colors from $7$, with no further structure to sort through. That is precisely what $P(7,4)$ counts, in one clean step.

"At least one repeat" is not one kind of pattern, it is a name for many different kinds bundled together: a pattern could repeat exactly one color twice, repeat one color three or four times, or repeat two different colors each twice, and so on. Counting it directly means breaking it into cases like these and adding, and the addition principle only adds case counts cleanly when the cases overlap nowhere and miss nothing. Here they do not overlap cleanly, because a naive way of building one case, such as "choose the repeated color, then place it," can build the same finished pattern from what looks like more than one starting choice, exactly as part B showed for red-red-blue-blue. Getting the cases right without overlap is possible in principle but is real, delicate work.

The complement sidesteps all of it. "Has at least one repeat" and "has no repeats" are two cases that, between them, cover every pattern and share none, so the addition principle applies to THEM in its cleanest form:

$\text{total} = (\text{no repeats}) + (\text{at least one repeat}).$

Since the total and the "no repeats" count are both single clean counts, the case that was hard to build directly is found by subtraction instead, with no casework ever attempted on it.