What is the Equation for Combinations with Repetition in Combinatorics?

[iScience]

Homework Statement

if there are k spots for n balls, what are the number of possible arrangements? each spot can hold n number of balls and each ball is indistinguishable from one another.

Homework Equations

$$\frac{n+k-1}{k!(n-1)!}$$

The Attempt at a Solution

I just wanted to know if this was the right equation, since i don't understand the equation.

 

[andrewkirk]

The question is unclear. Does it mean the following?

We have m>nk indistinguishable balls and k buckets, labeled 1 to k. We then put a number of balls between 0 and n inclusive in each bucket.
How many different arrangements of number of balls in the numbered buckets are there?

 

[iScience]

yup, that's what i meant. I'm actually trying to recreate all the possibilities visually (well, conceptually) but the number i get is different from the one the below eqn yields. $$\frac{n+k-1}{k!(n-1)!}$$
basically, I'm either not covering all possible arrangements with the way I'm going about it, or the expression i came up with is just incorrect. Either way i'd like someone to point out what I'm doing wrong.so here's how I'm doing it visually, just bear with me:

first, only one of the balls traverse all possible spots leaving us so far with:
$$Arrangements = k$$

then, for each spot it occupied, we find the number of additional arrangements it can make with an additional ball:

+1

+2

+3

for each time we move the red over, we traverse the green from position 2 to the red. (I do this because I'm trying to find the combination and not the permutation)

so now we have $$Arrangements = k + \sum^{k-1}_{i=1}(i)$$

again, being careful not to include any doubles of the same arrangement, i go from left to right.

i move the blue over to position 2, we have the same situation we had earlier, just with k-1 spots now.repeating the previous process we should end up with..

$$Arrangements = k-1 + \sum^{k-2}_{i=1}(i)$$

repeating the process till the end we get:

$$Arrangements = \sum^{k-1}_{j=0}[ (k-j) + \sum^{k-1-j}_{i=1}(i)]$$

So...
this was the case for 3 choose k. using my formula for say.. 3 choose 10, i get 121, whereas $$\frac{n+k-1}{k!(n-1)!}$$
says it should be 220. how does this not cover every possible arrangement?

 

[andrewkirk]

I think you're doing it in a more difficult way than necessary. Your pictures seem to be treating the balls as distinguishable by colour, whereas the problem says they are indistinguishable. That reduces the problem to the following:

How many different sequences of k numbers are there, where each number is an integer in {0, 1, 2, ..., n}?

 

[iScience]

Your pictures seem to be treating the balls as distinguishable by colour, whereas the problem says they are indistinguishable.

my apologies! the colors were just for me to keep track of what spots i already traversed. just makes it easier for me. but yes they are indistinguishable and so the colors are irrelevant.

k!, actually i have a simpler question, what i did above, is that "combination with repetition" or is it something completely different?

 

[haruspex]

my apologies! the colors were just for me to keep track of what spots i already traversed. just makes it easier for me. but yes they are indistinguishable and so the colors are irrelevant.

k!, actually i have a simpler question, what i did above, is that "combination with repetition" or is it something completely different?

First, your equation is not quite right. It should be $\frac{(n+k-1)!}{(k-1)!n!}$. To verify that, consider 1 ball, 2 spots. There are two possible arrangements, not 1.
The easiest way to understand this equation is to think in terms of separators between the 'spots', rather than the spots themselves. There are k-1 of these.
Next, blur the distinction between the balls and the separators. There are just n+ k-1 'things' in a line, of which k-1 are separators. The possible arrangements of undistinguished balls into the slots is then just the number of ways of deciding which of the n+k-1 things are the k-1 separators.