1. ## Counting problem

Hey everyone,

here is a little problem, I know that there are many ways of solving it and I'm interested to know how you would solve it:
there are k bags numbered from 1 to k ( you can tell the difference between the bags), and you have n balls ( you can't make the difference between the balls). also $k \leq n$
a)how many possibilities you have of putting all the balls in the bags with each bag having at least 1 ball in it.
b)how many possibilities you have of putting all the balls in the bags.

a) $\binom{n-1}{k-1}$
b) $\binom{n+k-1}{k-1}= \binom{n+k-1}{n}$
tell me if you can prove me wrong and if you find the same thing, well in both case tell me how you found it.

Thank you so much in advance!!!

2. ## Re: Counting problem

Originally Posted by sunmalus
there are k bags numbered from 1 to k ( you can tell the difference between the bags), and you have n balls ( you can't make the difference between the balls). also $k \leq n$
a)how many possibilities you have of putting all the balls in the bags with each bag having at least 1 ball in it.
b)how many possibilities you have of putting all the balls in the bags.
a) $\binom{n-1}{k-1}$
b) $\binom{n+k-1}{k-1}= \binom{n+k-1}{n}$

3. ## Re: Counting problem

If you can say that so quickly i'm very impressed. It took me ages to come up with that. I'm terrible at counting problems.

4. ## Re: Counting problem

Originally Posted by sunmalus
If you can say that so quickly i'm very impressed. It took me ages to come up with that. I'm terrible at counting problems.
Well there is really only one basic rule.
These are called multi-selections .
If we select N items from K different types there are $\binom{N+K-1}{N}$ ways to do it.
But some types may not be chosen.
If we want to have at least one of each type then $N\ge K$ and the formula becomes $\binom{(N-K)+K-1}{N-K}$.

5. ## Re: Counting problem

That is interesting! Can you tell me where I can find a full proof of this? ( book, website etc).

6. ## Re: Counting problem

Originally Posted by sunmalus
That is interesting! Can you tell me where I can find a full proof of this? ( book, website etc).
Here is a good discussion.

Thanks!