Скачать или смотреть Unizor - Combinatorics - Permutations with Repetitions

What if the initial set of objects is not diminishing with each new pick but remains exactly as it was before? For instance, we are asked to write different 3 characters words using only two letters A and B, and we can use these letters more than once in any word. For instance, AAA, AAB, BAA - are all legitimate words. How many such words can we write?
This is a problem of permutations with repetitions.

To calculate the number of such words, let's examine our choices, as we did for regular permutations. Since our set contains only two objects, we have two choices for the object #1. Then, for the object #2 we have exactly the same two choices because, as we defined this process, the original set remains the same after each step. So, for each of two choices for the object #1 we have two choices for the object #2. So far, the number of combinations (that is, the number of two characters words) equals to 2·2=4. Then the third step also has two choices of letters, bringing the total number of different three characters words to 4·2=8.

Let's generalize this approach. Our task is to calculate the number of possible permutations with repetition of N objects into ordered groups by K objects in each group. We will use the symbol PR(N,K) to designate this quantity.
For the object #1 we have N choices. Same for the object #2 for each choice of #1, bringing the total number of combinations of two objects to N·N=N^2. Same for the object #3 for each choice of a pair #1 and #2, bringing the total number of combinations of three objects to N·N·N=N^3, etc. So, on each step (and we need to make K steps to form a group of K objects) we have to multiply the total number of choices by N. The total number of different groups will, therefore, be
PR(N,K) = N^K.

This formula can very easily be proven by induction by the number of groups K. We leave it as a self-study exercise.

Here are a few other examples of the permutations with repetitions. It's important not just to use the above formula blindly, but proceed with the logical steps calculating the result.

Examples

1. You have six exam questions to answer "Yes" or "No". How many different answers to an exam are possible?
Since for each question we have only two answers, for a set of six questions we have 64 different answers. Why?

2. There are only three choices for dinner - beef stew, chicken parmesan or grilled salmon. We have one week to dine only from this set of dishes. How many different combinations of dinners during a one week period exist? The answer is 2,187. Why?

3. Every day in New York there is plenty of different performances. Assume that I like cinematography, jazz, musicales and drama, and each of these genres is well represented in New York, so I can pick anything I want at any time. Assume that once in a quarter I go to one of these performances (they are expensive, I cannot afford to go more often), so I attend four performances a year. How many different sets of four performances there exists? The answer is 256. Why?

4. This is a problem with a slight twist. How many three digit numbers you can write? Make sure you don't count the numbers that start with 0 as it's not really customary. The answer is, obviously, 900 (from 100 to 999. But try to get it using the logic of combinatorics.