Counting Length-\(r\) Sequences with Repetition Allowed

Hello! Last time, you counted ordered positions filled without reuse: after each choice, one fewer object was available. Now keep the positions ordered but allow a choice to be used again. The change is small, but it replaces a decreasing product with a power.

This lesson derives the count of length-$r$ sequences from $n$ choices, then examines how to tell whether every position really has the same options. Allow about 30–35 minutes, including the short video and reading.

Why the count is a power

Suppose the available symbols are $A$, $B$, and $C$, and you want a four-symbol code. A code records what appears in each position, so $ABCA$ and $ACBA$ are different outcomes. Reuse is allowed: $AAAA$ is valid.

There are three choices for the first position. Whichever symbol you choose, there are still three choices for the second, three for the third, and three for the fourth. The multiplication principle gives $3\cdot 3\cdot 3\cdot 3=3^4=81$ codes. Unlike a permutation without reuse, choosing $A$ does not remove $A$ from consideration.

More generally, let $S$ be a set of $n$ distinct symbols. A length-$r$ sequence specifies one member of $S$ in each of $r$ numbered positions. We can describe the set of all such outcomes as $S^r$: each position has its own copy of the same $n$-choice set. Applying the product rule to those $r$ positions gives

This is also a short proof of the formula: every partial sequence of length $r-1$ has exactly $n$ possible final symbols, and adding that final symbol produces a different complete sequence for every choice.

Compare this with the previous lesson’s count:

Both count ordered outcomes. The difference is whether an earlier choice changes the number available later. For example, with five symbols and three positions, the counts are $5^3=125$ with reuse and $5\cdot 4\cdot 3=60$ without it.

There is no requirement that $r\le n$ when reuse is allowed: three symbols can fill ten positions. At $r=0$, there is exactly one sequence, the empty sequence, consistent with $n^0=1$ for $n\ge 1$.

Identify the choices at each position

Watch two short excerpts from MIT OpenCourseWare’s 4. Counting. The first uses letters and digits in different positions; the second uses repeated die rolls. Notice that the same multiplication principle handles both, even though only the die example has the same number of choices at every position.

For the license-plate format in the video, each of three letter positions has 26 choices, and each of four digit positions has 10. If repetition is permitted, the count is

This is not a single power $n^r$, because the permitted set changes between the letter and digit positions. The general multiplication principle still applies: multiply the number of choices at each position.

For six die rolls, each position has six possible face values, so there are $6^6=46,656$ recorded sequences of results. This is a count of possible sequences, not yet a claim that they have equal probabilities. Counting available outcomes and assigning probabilities to them are separate tasks we will connect later.

The exact description of an outcome matters, too. A four-digit code can begin with zero, giving $10^4$ codes if every digit may be reused. A four-digit number cannot begin with zero: its first position has nine choices and its remaining positions have ten each, giving $9\cdot 10^3$. Before writing $n^r$, check that every one of the $r$ positions really does have all $n$ choices.

Reuse allowed does not mean unrestricted

“Repetition is allowed” can describe several different rules. You might permit a symbol to appear anywhere, permit it to return only after another symbol intervenes, or forbid its return entirely. Those rules lead to different counts.

Read Example 7 in Doerr and Levasseur’s 2.2: Permutations on Mathematics LibreTexts. It places three rules side by side using the digits 1 through 5.

For three positions drawn from five digits, the unrestricted count is $5^3=125$. If no digit can appear twice anywhere, the counts by position are $5$, $4$, and $3$, giving $60$. If only an immediate repeat is forbidden, there are five choices initially and four for each later position, giving $5\cdot 4\cdot 4=80$. In that last case, the third digit may match the first; it just cannot match the second.

This gives a useful diagnostic for a new problem: after imagining a valid partial sequence, ask how many symbols may come next? The multiplication principle works when you can give the number of continuations at each position for every valid partial sequence. The formula $n^r$ is the particularly clean case in which that number stays $n$ throughout.

A final distinction will matter in the next lesson. Today, reusing $A$ means choosing the same symbol again from an unrestricted set. A problem that supplies a fixed collection containing, say, two identical $A$s has an inventory that can run out. Although its finished arrangements may also contain repeated symbols, it is a different counting model.

Key takeaways

A length-$r$ sequence from $n$ choices has $n^r$ possible outcomes when each numbered position can independently be filled by any of the same $n$ symbols—“independently” here means the available choices are unchanged, not that any probabilities have been specified. Order remains recorded, and reuse is permitted.

When the options differ by position or depend on earlier choices, return to the multiplication principle and count those options directly. Next, we’ll count arrangements drawn from a fixed supply of objects containing identical copies, where repetition in the finished arrangement does not mean unlimited reuse.