Number of ways to pick balls from an urn if one type of ball runs out

171 Views Asked by At

Assumed you have balls with three different colors in an urn. From each type of ball you have four pieces that are not distinguishable. How many ways are there to pick five balls out of the urn?

Or in general with balls in $k$ different colors and $m$ balls of each of the color how many ways are there to pick $n$ balls out of the urn?

The problem is easy if $n \leq m$. Then it is just an unordered selection with repetition allowed. Therefore there are $\binom{k+n-1}{n}$ ways to pick. But if $n > m$ repetition is not necessarily allowed and I cannot find a beautiful way to calculate the number of ways. For small examples I might be able to find the solution step by step but on a larger scale I need help.

2

There are 2 best solutions below

0
On

If you compute $$f(x):=(1+x+x^2+\ldots+x^m)^k$$ by multiplying distributively you obtain for each legal pick of $m_1$, $m_2$, $\ldots$, $m_k$ balls with total $m_1+m_2+\ldots+m_k=n$ a term $x^{m_1+m_2+\ldots+m_k}=x^n$. We therefore have to compute the coefficient of $x^n$ in the expansion $$f(x)=\left({1-x^{m+1}\over1-x}\right)^k=\sum_{j=0}^k{k\choose j}\bigl(-x^{m+1}\bigr)^j\cdot\sum_{l=0}^\infty{k+l-1\choose l}\,x^l\ .$$ Collecting terms we obtain a finite alternating sum of products of binomial coefficients. This sum can be interpreted combinatorially as result of a certain inclusion/exclusion process. Maybe someone will put forward a solution in this other realm.

0
On

This is the same question as asking the number of ways to fit $n$ blocks into a Young diagram with sides of length $k$ and $m$, and involves q-binomials in the solution. So if you have $n$ blocks where $0\leq n\leq k m$, then the answer is the $n$th coefficient of the polynomial gained from the q-binomial term:

$\left[ \begin{array}{c} h+j \\ j \\ \end{array} \right]_q$

Here's some links, the first gives an example of how to work it.

http://mathworld.wolfram.com/q-BinomialCoefficient.html

https://www.math.upenn.edu/~pemantle/papers/Preprints/qBinomial.pdf

This paper by Dr. Proctor is just a fun read, and has a nice graphic showing the problem.

https://www.jstor.org/stable/pdf/2975833.pdf?refreqid=excelsior%3A0abe07e98cab72b8b5fe076b50358d86