[Common Math 1 Part 23] Repeated Permutations and Repeated Combinations (Advanced)

In the previous post, we studied permutations and combinations without repetition. Now we allow the same object to be chosen more than once.

Note: repeated permutations and repeated combinations are advanced extension topics rather than part of the basic Common Math 1 scope. Read this post as optional enrichment after the core permutation and combination ideas.

Understand what repetition means, and distinguish repeated permutations from repeated combinations depending on whether order matters.

The key ideas are:

• Allowing repetition means that an object can be chosen again after it is chosen once.
• A repeated permutation allows repetition and considers order.
• A repeated combination allows repetition but does not consider order.
• Repeated combinations can be interpreted as deciding how many of each type to choose.
• After understanding the formulas and recurrences, we can generate actual arrays with Python.

1. What does repetition mean?

Allowing repetition means that the same object can be chosen multiple times.

For example, suppose we make a three-digit password using 1, 2, 3.

If repetition is allowed,

are all possible.

If repetition is not allowed, $111$ is impossible because the digit 1 is used three times.

Again, we must ask:

Does order matter?

For a password, order matters. $123$ and $321$ are different passwords. But if we are only choosing a multiset such as "two apples and one banana," order does not matter.

2. Repeated permutations

A repeated permutation is an ordered selection where repetition is allowed.

Suppose we choose 2 letters from A, B, C with repetition allowed, and order matters.

For the first position, there are 3 choices. For the second position, there are again 3 choices, because the first chosen letter can be chosen again.

So the number of arrays is

The arrays are:

The notation is

and the formula is

because each of the $r$ positions has $n$ choices.

3. A recurrence view of repeated permutations

To build a repeated permutation of length $r$, first build a repeated permutation of length $r-1$, then attach one more element at the end.

Since repetition is allowed, every element can be attached to every previous array.

with

This recurrence directly describes the generation process.

4. Repeated combinations

A repeated combination is a selection where repetition is allowed but order does not matter.

Suppose we choose 3 fruits from apple, banana, and cherry, and repetition is allowed.

Then these are the same selection:

and

because order does not matter. What matters is how many of each fruit we choose.

So a repeated combination can be written as numbers:

where

• $a$ = number of apples
• $b$ = number of bananas
• $c$ = number of cherries

If we choose 3 fruits total, then

where $a,b,c$ are nonnegative integers.

5. Stars and bars

The standard method for repeated combinations is stars and bars.

For example, choosing 3 fruits from 3 types means distributing 3 identical stars into 3 boxes.

Use stars for chosen objects and bars for boundaries between types.

For 3 fruits and 3 types, we need:

• 3 stars
• 2 bars

For example,

means:

• 2 apples
• 1 banana
• 0 cherries

Another example,

means:

• 0 apples
• 1 banana
• 2 cherries

There are 5 total positions: 3 stars and 2 bars. Choose where the 2 bars go.

In general, the number of repeated combinations is

6. Why the formula works

Choosing $r$ objects from $n$ types with repetition allowed is the same as solving

in nonnegative integers.

Here $x_i$ is the number of objects of type $i$.

We represent the $r$ objects as stars and use $n-1$ bars to divide them into $n$ groups.

So there are

positions, and we choose either the positions of the $r$ stars or the positions of the $n-1$ bars.

Therefore,

7. A recurrence view of repeated combinations

Repeated combinations can also be generated by deciding whether to use the first type.

For the first type A:

1. Use at least one A.
2. Use no A.

If we use at least one A, we put A in the result and still may use A again. So the remaining problem is to choose $r-1$ objects from the same $n$ types.

If we use no A, we choose $r$ objects from the remaining $n-1$ types.

Thus,

with suitable boundary cases.

8. Comparing the four types

The most important questions are always:

1. Is repetition allowed?
2. Does order matter?

9. Math first, code later

The following code generates actual arrays.

def repeated_permutations(items, r):
    if r == 0:
        return [[]]

    result = []
    for prev in repeated_permutations(items, r - 1):
        for item in items:
            result.append(prev + [item])
    return result

print(repeated_permutations(['A', 'B', 'C'], 2))
print(len(repeated_permutations(['A', 'B', 'C'], 2)))

def repeated_combinations(items, r):
    if r == 0:
        return [[]]
    if not items:
        return []

    first = items[0]
    rest = items[1:]

    with_first = [[first] + tail for tail in repeated_combinations(items, r - 1)]
    without_first = repeated_combinations(rest, r)
    return with_first + without_first

print(repeated_combinations(['A', 'B', 'C'], 3))
print(len(repeated_combinations(['A', 'B', 'C'], 3)))

def permutations(items, r):
    if r == 0:
        return [[]]
    result = []
    for i, item in enumerate(items):
        rest = items[:i] + items[i+1:]
        for tail in permutations(rest, r - 1):
            result.append([item] + tail)
    return result


def combinations(items, r):
    if r == 0:
        return [[]]
    if not items:
        return []
    first, rest = items[0], items[1:]
    return [[first] + tail for tail in combinations(rest, r - 1)] + combinations(rest, r)


def repeated_permutations(items, r):
    if r == 0:
        return [[]]
    return [prev + [item] for prev in repeated_permutations(items, r - 1) for item in items]


def repeated_combinations(items, r):
    if r == 0:
        return [[]]
    if not items:
        return []
    first, rest = items[0], items[1:]
    return [[first] + tail for tail in repeated_combinations(items, r - 1)] + repeated_combinations(rest, r)

10. Summary

• Repetition means an object can be chosen again.
• ${}_n\Pi_r$ counts repeated permutations, where order matters.
• ${}_n\Pi_r=n^r$
• ${}_nH_r$ counts repeated combinations, where order does not matter.
• ${}_nH_r={}_{n+r-1}C_r={}_{n+r-1}C_{n-1}$
• Repeated combinations are equivalent to nonnegative integer solutions of $x_1+\cdots+x_n=r$.
• Recurrence relations show how the arrays can actually be generated.