11.4. Permutations Where Repetitions Are Allowed

Now, we will consider the case where even in the selection, repetitions are allowed as well. So we are now interested to first find out the number of $r$ permutations of a set of objects where I am allowed to have repetitions. For instance, if I consider a set with 3 persons; person 1, person 2, and person 3. Now if I ask you how many 2-permutations I can have over this set where I can repeat the person when I am forming the permutation...

In this part, we explore how permutations can change when we allow repeats. When forming permutations from a set of objects, allowing repetitions means that after choosing an object, you can choose it again for the next position. Using our previous example of 3 persons, let's say person 1, person 2, and person 3. If we want to create 2 permutations and repeating is allowed, we have increased our total potential arrangements. Now, every time we fill a position, we have three options instead of being restricted by the already chosen objects. Hence, the total number of 2-permutations would be $3^2 = 9$.

Imagine you're creating passwords using the characters 'A', 'B', and 'C'. If you're allowed to use the same character multiple times, for a 2-character password, you can have 'AA', 'AB', 'AC', 'BA', 'BB', 'BC', 'CA', 'CB', and 'CC'. This shows how repetitions present a larger combination than if you couldn't repeat characters.

So now again if I want to find out the number of $r$-permutations of $n$ distinct elements where repetitions are allowed then it turns out to be the product of $n$, $r$ number of times. Because I have to fill $r$ slots and the first slot can be occupied in $n$ ways. And for each of those $n$ ways in which I can occupy the first slot, I can fill the second slot also in $n$ ways...

The formula for calculating the number of $r$-permutations when repetitions are allowed is straightforward. Since every slot can contain any of the $n$ objects, for each of the $r$ slots, you have $n$ choices. Hence, the total number of permutations can be expressed mathematically as $n^r$. This exponential calculation represents how each independent choice increases the total outcomes drastically.

Think of making ice cream sundaes with three different toppings: chocolate, sprinkles, and nuts. If you can choose 2 toppings for your sundae, you can have 'chocolate on chocolate', 'chocolate and sprinkles', and so on, leading to the combinations like 'sprinkles and nuts' or 'nuts and nuts'. With three choices for each topping and two slots to fill, the total combinations become $3^2 = 9$.

Now let's try to find out the number of $r$-combinations where repetitions are allowed and this is slightly tricky. Before going into the derivation of this formula, let me give you a motivating example...

In this section, we explore the concept of combinations where repetition is allowed. Unlike permutations, combinations do not consider the order of selection. The challenge here is to count the selections correctly when you can choose each item multiple times. The general formula for $r$-combinations with repetitions is given by $C(n+r-1, r)$, which reflects the idea of filling slots while keeping track of boundaries between unique objects.

Imagine a candy jar that holds different types of candy (like chocolate, gummies, and hard candies). If you want to choose 3 candies from this jar but you can choose the same type more than once, it’s like putting a divider between each candy type and counting how many you pick. For instance, if you pick 3 pieces, you can have all three as chocolate, or one chocolate and two gummies. The challenge is figuring out how to count all the arrangements—including repetitions!

--