# number of ways ?

• Dec 14th 2011, 05:47 AM
livinggourmand
number of ways ?
In how many ways can we place n+x balls in n boxes
with a condition that at least 1 ball is present in every box
when
1)balls r identical
2)balls r numbered from 1 to n+x
and x<n
• Dec 14th 2011, 07:10 AM
Plato
Re: number of ways ????
Quote:

Originally Posted by livinggourmand
In how many ways can we place n+x balls in n boxes
with a condition that at least 1 ball is present in every box
when
1)balls r identical
2)balls r numbered from 1 to n+x
and x<n

You failed to tell us if the boxes are all different.
So we assume they are.

There are $\displaystyle \binom{K+N-1}{K}$ ways to place K identical items into N different cell.
If we require that no cell is empty then it must be that case that $\displaystyle K\ge N$ and that multi-selection formula becomes
$\displaystyle \binom{K-1}{K-N}$.

For part b), we need to count the number of surjections (onto functions) from a set of N+x to a set of N.

If $\displaystyle K\ge N$ and then the number of surjections from a set of K to a set of N is $\displaystyle \sum\limits_{j = 0}^N {( - 1)^j \binom{N}{j} (N - j)^K }$.
• Dec 14th 2011, 07:19 AM
livinggourmand
Re: number of ways ????
n if boxes are identical??
• Dec 14th 2011, 07:39 AM
Plato
Re: number of ways ????
Quote:

Originally Posted by livinggourmand
n if boxes are identical??

If the boxes are identical then it becomes more difficult.

For part a), we have to count the numbers of ways to have K summands for the integer N+x. That is not easy.

Part b) is a bit easier that a). We count the number of unordered partitions of N+n individuals into N groupings.

However, I suspect that whoever wrote this question meant the boxes all different. Because, that is an easier question.