Suppose you start with N objects, you want to choose M of them, M <= N, repeating is allowed. How many possibilities are there?

(An application of this question: a pizza store carries 30 ingredients. You are allowed to put only one kind on a slice. A pizza has 8 slices. How many kinds of pizza can you make? Assuming pizza is served by the slice, it doesn't matter what order you put the ingredients on it, and it doesn't matter whether the same ingredient appears on more than one slice)

The answer: (N+M - 1) Ch (M) , or written as a fraction

(N+M-1)! / (N-1)! M!

How do we arrive at that answer?

We do it by the following: suppose we have N cards, numbered 1 to N. We make M-1 more cards, number them -1 to -M+1. We choose M cards from the entire deck, non-repeating. How many choices do we have? It is by definition (N+M-1) Ch (M). Now we want to show that this situation is the same as my original proposal.

For each hand you choose from the deck of N+M-1 cards, you can have anywhere from 0 to M-1 of the "negative" cards. Suppose you are dealt a hand of M cards from the deck. You arrange the cards in increasing order, for example, let N = 30 and M = 8:

-5 -2 1 9 11 13 19 20

Starting from the one closest to zero, replace each negative number with the number in that position in the hand (using clockface arithmetic), so we replace the card -2 with the one in the position that is 2nd to last, which is 19. And we replace the -5 with the one in the position that is 5th to last, which is 9. So our hand becomes

9 19 1 9 11 13 19 20

What if the position of a negative card is taken by another negative card? Let's say we have the following hand

-7 -5 -3 -1 10 14 16 22

After replacing -1 and -3 with the corresponding numbers, we get

-7 -5 14 22 10 14 16 22

So now we replace -5 by 22 (the "value" of the -1 card) and then the -7 by, also, 22 (the "value" of the -5 card), and end up with

22 22 14 22 10 14 16 22

It is easy to see that with this procedure, we can relate to each hand from our deck of N+M-1 cards to a hand from N cards with repeating allowed.

Notice that, also, it is impossible for a negative card to point to itself. We have only (M-1) negative cards in total. For a negative card to point to itself, we need the negative card, after sorted, to be sitting on the spot it points to. Suppose we are dealt the card (-m). And suppose it happens to sit on the (-m)th position. That means that there are another M-m cards sitting before it. But that is impossible, since there are only (M-1 - m) cards that have values less than (-m) (the smallest number in our deck is -M+1...). So we can safely say that no infinite recursion will occur.

For our model to be complete, we need to show two things:

1. Surjectivity: that every "repeatable" hand from N cards can be arrived from a "unique-card" hand from N+M-1 cards.
2. Injectivity: that every hand from N+M-1 cards correspond to a unique hand from N cards.

if those two conditions are satisfied, we know that for each possible "choice" in the original problem, there is exactly one corresponding hand from N+M-1 cards; which is to say, the total number of possibilities are the same. And we know the how many choices are available for N+M-1 cards....

So... we first show that for each possible choice in the original problem, there exists a hand from N+M-1 cards.

We label, as usual, the original available objects 1 to N. We pick a possible choice (possibly with repeated objects) of M objects. We arrange them by the following:

1. Take the largest number in the list. Put it to the far right. And if there are any number as large as it, put those away in a separate pile.
2. Now what was the second largest number in the list is now that largest number, so we do the same thing, put it to the far right, immediate left of the first number, and if there are any number as large as it, put those away in our discard pile.
3. Keep repeating until we get to the smallest number in the pile.
4. Then we take the discard pile, and do the same thing again.

So, back to our "choose 8 from 30" situation, suppose our initial choice is

1 5 5 8 16 17 17 19

We first put down 19 at the far right. There are no more numbers as big as 19, so the discard pile is empty. We put 17 next to 19. And put the other 17 into the discard pile. We proceed down all the way to 1. And we end up with

1 5 8 16 17 19

in that order, and a 5 and a 17 in the discard pile. Now we repeat the procedure for the discard pile. And first we put 17 next to the 1, and then 5 next to it. So we end up with

5 17 1 5 8 16 17 19

Lastly, we start from the left, and replace each number by the position number of the first time it occurs after it. For example, the first time 5 occurs after the left-most position is on the 5th spot from the right, so we replace 5 by -5. And for 17, we replace by -2.

Let's do another example.

2 2 2 2 19 23 23 23

After sorting, it gets rearranged like the following

2 2 23 2 23 2 19 23

The first 2 gets replaced by -7. The second 2 by -5.... and eventually we get

-7 -5 -4 -3 -1 2 19 23

So with this explicit construction, we see that we can find a hand in our (N+M-1) deck of cards that corresponds to a choice of M repeatable objects from a set of N.

The fact that this explicit algorithm produces a hand sorted in order can be easily used to show injectivity. This is an exercise left for the reader.