1
$\begingroup$

Basically I have a urn with balls in different colors. For example $urn = \{r, r, r, b, b, y\}$ How many different outputs (order matters) if I take 3 balls.

The answer is $\#\{rrr, rrb, rry, rbr, rbb, rby, ryr, ryb, brr, brb, bry, bbr, bby, byr, byb, yrr, yrb, ybr, ybb\} = 19$

Other example: $urn = \{r, r, r, b\}$, the number of combinations of length 2 is $\#\{rr, rb, br\} = 3 $

My question: is there any nice formular to calculate this number of different combinations of a certain length. I want to use it for urns with much more colors, much more balls and larger lengths.

$\endgroup$
1
$\begingroup$

You can use generating functions:

If the urn contains $t$ types of balls and there are $n_j$ balls of type $j$, then you can get the number of ways to take $k$ balls from the urn as $k!$ multiplied by the coefficient of $x^k$ in the expansion of:

$$\prod_{i=1}^t\left(\sum_{j=0}^{n_j}\frac{x^j}{j!}\right)$$

Example:

For the first urn you mentioned, $\{r,r,r,b,b,y\}$, we have $k=3$ (we are picking $3$ balls), $t=3$ (number of types in the urn), $n_1=3$, $n_2=2$ and $n_3=1$ (number of balls of each type), so the formula gives us:

$$\left(1+x+\frac{x^2}{2}+\frac{x^3}{6}\right)\left(1+x+\frac{x^2}{2}\right)\left(1+x\right)$$

which, when expanded, equals:

$$1+3x+4x^2+\frac{19x^3}{6}+\frac{19x^4}{12}+\frac{x^5}{2}+\frac{x^6}{12}$$

The coefficient of $x^3$ is $\frac{19}{6}$. Now you just need to multiply by $k!=3!=6$ to get $\frac{19}{6}\cdot6=19$.

For smaller numbers this might be doable by hand, but for bigger ones I suggest a CAS (Computer Algebra System) like Mathematica, Maxima, Maple, Sage, etc.

Also, you should try to understand how GFs are used in enumeration, because they can solve many problems like this one very easily.

$\endgroup$
  • $\begingroup$ Thanks a lot. I know generating functions, but completely forget that they could be useful with such a problem. $\endgroup$ – Jakube Sep 19 '14 at 16:56
  • $\begingroup$ Oh, even better, then. :) $\endgroup$ – ryagami Sep 19 '14 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.