11.7. Combinations With Repetitions

Now we will consider the case where even in the selection the repetitions are allowed as well. So we are now interested to first find out the number of n-permutations of a set of objects where I am allowed to have repetitions. So for instance if I consider a set with 3 persons: person 1, person 2, and person 3.

In this chunk, we introduce the concept of combinations with repetitions. This means that when selecting items (or people, in the example), we can choose the same item multiple times. For instance, if we draw 2 names from a group of 3 people, we might end up picking 'person 1' twice, which was not allowed in previous cases. This leads to a higher total number of possible selections.

Imagine a fruit basket where there are 3 different kinds of fruits: apples, bananas, and cherries. If you're allowed to pick any fruit more than once, you could choose 2 apples, or 1 banana and 1 cherry, or even 2 bananas. Each of these combinations is unique as we can repeat our selections.

So now again if I want to find out the number of n-permutations of a set of k distinct elements where repetitions are allowed, then it turns out to be the product of k, n times. Because I have to fill n slots and the first slot can be occupied in k ways.

When repetitions are allowed and we wish to find out how many ways we can select n items from k distinct items, the formula becomes k^n. This is because for each of the n slots we have k choices. The first choice can be any of the k items, and similarly for the second, third, and so on. Thus, we multiply the number of options available for each slot.

Consider a password that is to be made using 3 letters from the English alphabet (let's say A, B, and C) and the same letter can be used more than once. For example, valid passwords could be 'AAA', 'AAB', 'ABC', 'BAC', etc. Since we can choose any letter for each of the 3 positions, we have 3 choices for the first letter, 3 for the second, and 3 for the third, resulting in 3^3 = 27 possible passwords.

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

This chunk introduces the concept of counting combinations when items can be repeated. Unlike permutations where order matters, combinations focus on selection without regard to the order. We want to find out the number of ways to select a certain number of items from a set when it is permissible to select the same item multiple times. This situation is equivalent to placing items in separate categories, which we'll explore through examples.

Consider a situation at an ice cream shop where you can choose 3 scoops of ice cream from 4 different flavors (vanilla, chocolate, strawberry, mint). Here, you can select the same flavor multiple times, like having three scoops of vanilla or two scoops of chocolate and one scoop of strawberry. The different selections represent combinations rather than permutations because it doesn't matter in which order the scoops are stacked. The formula to calculate these combinations is C(n+r-1, r), where n is the number of distinct flavors and r is the total number of scoops.

This is because you can interpret this problem as follows. Consider the example of cash registers with slots for bills. You have 4 slots available: bills of 1 dollar, 2 dollars, 5 dollars, 10 dollars.

Here, we derive the formula for combinations with repetitions allowed. The example uses a cash register analogy, where each bill represents distinct items (or types). To determine how many ways we can choose a set total from these denominations while allowing for repetitions, we can use a concept involving vertical lines separating groups of similar items. By treating each selection scenario as a series of crosses (picked items) and vertical dividers (between categories), we develop our counting framework.

If you have a cash box with different denominations and you are tasked with selecting 3 total bills (like 1 dollar bills, 2 dollar bills, and so on) while keeping track of how many are picked, you can picture dividing them visually with lines. Each unique layout of chosen bills and dividers corresponds to a unique selection of bills. For instance, if you choose 2 one-dollar bills and 1 two-dollar bill, that can be represented as crossing off 2 lines under the 1 dollar category and 1 under the 2 dollar category.

So that is why the general formula for n-combinations where repetitions are allowed is C(n+r-1, r).

This chunk concludes the section by presenting the generalized formula for combinations when repetitions are allowed. It highlights the relationship between the number of items chosen and the allowance for selections without order and repetition. The formula C(n+r-1, r) establishes a systematic way to count the number of possible combinations through a combinatorial approach.

Think of this as a situation where you want to distribute candies (r) in different flavors (n) but you can use each flavor multiple times without restriction. The formula helps us predict how many unique sets of candies can result when drawing from a variety of flavors where it's as if the candies belong to distinguishable groups.

--