# Counting problem

• Oct 3rd 2012, 12:29 PM
sunmalus
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!!!
• Oct 3rd 2012, 12:44 PM
Plato
Re: Counting problem
Quote:

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}$

• Oct 3rd 2012, 12:51 PM
sunmalus
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.
• Oct 3rd 2012, 01:27 PM
Plato
Re: Counting problem
Quote:

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}$.
• Oct 3rd 2012, 01:31 PM
sunmalus
Re: Counting problem
That is interesting! Can you tell me where I can find a full proof of this? ( book, website etc).
• Oct 3rd 2012, 01:34 PM
Plato
Re: Counting problem
Quote:

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.
• Oct 3rd 2012, 01:41 PM
sunmalus
Re: Counting problem
Thanks!