Thread: 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 $\displaystyle 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.

My answers
a)$\displaystyle \binom{n-1}{k-1}$
b) $\displaystyle \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!!!

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 $\displaystyle 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.
My answers
a)$\displaystyle \binom{n-1}{k-1}$
b) $\displaystyle \binom{n+k-1}{k-1}= \binom{n+k-1}{n}$

Those answers are correct.

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.

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 $\displaystyle \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 $\displaystyle N\ge K$ and the formula becomes $\displaystyle \binom{(N-K)+K-1}{N-K}$.

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

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!