If I understood you correctly your problem is the following:
Given n items choose k from them. And replacement means you are allowed to choose an item more than once.
-------------------------
You can interpret the problem in the following way:
Imagine you have n=3 boxes. Each box stands for a fruit:
Apple-Box (Box #1)
Banana-Box (Box #2)
Orange-Box (Box #3)
You have k=10 balls and have to throw the balls into the boxes. Suppose you did the following:
Apple-box: 3 balls
Banana-box: 2 balls
Orange-box: 5 balls
This means you get 3 apples, 2 bananas and 5 oranges.
So, one combination is:
In box 1 we have 3 balls
In box 2 we have 2 balls
In box 3 we have 5 balls
---
We can model this by dividing the 10 balls into 3 blocks:
o o o
| o o
| o o o o o
The blue bars are the
dividers.
Other combinations are:
All balls in box 1 (only apples):
o o o o o o o o o o
| |
0 balls in box 1,
3 balls in box 2,
7 balls in box 3
| o o o
| o o o o o o o
1 ball in box 1,
4 balls in box 2,
5 balls in box 3
o
| o o o o
| o o o o oFor n blocks (boxes) we need (n-1) dividers, e.g. n=3 requires (n-1)=2 dividers.
Now, how many "spots" do
dividers and
balls occupy? We have (n-1) dividers and
k balls, so in total we have (n-1+k) spots.
Then, let's analyze how many different positions there are for the balls:
Since we have (n-1+k) spots and k balls there are (n-1+k)Choose(k) different positions.
\binom {n-1+k} {k}
Of course, you could also ask:
How many different positions are there for the (n-1)
dividers?
Since we have (n-1+k) spots and (n-1) dividers there are (n-1+k)Choose(n-1) different positions. But this is the same as above:
\binom{n-1+k}{n-1} = \binom {n-1+k} {k}
----
Further readings:
1.
Counting selections with replacement
The derivation is given in the end.
2.
Combinations - order doesn't matter, repetitions allowed
This is a PF thread.
