Counting problem

**sunmalus** · Oct 3rd 2012, 12:29 PM

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.

My answers
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!!!

**Plato** · Oct 3rd 2012, 12:44 PM

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

Those answers are correct.

**sunmalus** · Oct 3rd 2012, 12:51 PM

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.

**Plato** · Oct 3rd 2012, 01:27 PM

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

**sunmalus** · Oct 3rd 2012, 01:31 PM

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

**Plato** · Oct 3rd 2012, 01:34 PM

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.

**sunmalus** · Oct 3rd 2012, 01:41 PM

Thanks!

Thread: Counting problem

LinkBack

Thread Tools

Display

Counting problem

Re: Counting problem

Re: Counting problem

Re: Counting problem

Re: Counting problem

Re: Counting problem

Re: Counting problem

Similar Math Help Forum Discussions

A counting problem

Counting Problem

counting problem

[SOLVED] Counting Problem - just a quick question with this problem

counting problem

Search Tags