Say, I got $1$ red ball, $1$ blue, $2$ yellow, $3$ green, totally $7$ balls. I wanna select $3$ balls from them. How many ways I can do this?I counted manually $$123, 124, 133, 134, 144, 233, 234, 244, 334, 344, 444,$$ so $11$ combinations.Is there a formula for it?
number of combinations without repetition with limited supply
2 Answers
Yes, you can do it with generating functions:
For the blue or red balls: $1+x$ (either you take none or one).
For the yellow ball: $1+x+x^2$ (either you take none or one or two).
For the green ball: $1+x+x^2+x^3$ (either you take none or one or two or three).
Hence the generating function for this problem would be:
$$(1+x)^2(1+x+x^2)(1+x+x^2+x^3)=1+4x+8x^2+11x^3+11x^4+8x^5+4x^6+x^7$$
The coefficient of $x^n$ is exactly the number of options to choose exactly $n$ balls.
Here, the coefficient of $x^3$ is $11$, which is the number of options to choose $3$ balls.
-
0This is neat, is there a closed form? – 2011-07-18
-
1Not really, but you can reduce it in the following sense: If you have $t$ different classes of objects with $k_i$ objects of type $i$, then the generating function would be $$\prod_{i=1}^t(1+x+...+x^{k_i})=\prod_{i=1}^t\frac{1-x^{k_i+1}}{1-x}=\frac{\prod_{i=1}^t(1-x^{k_i+1})}{(1-x)^t}$$ Remembering that $$\frac{1}{(1-x)^t}=\sum_{n=0}^\infty\binom{n+t-1}{t-1}x^n$$ You can find the desired coefficient (which involves a lot of calculations) – 2011-07-18
-
0-Dennis ok, generating functions, u reminded me something i learned years ago. – 2011-07-18
Your problem is equivalent with this one.
$x_1+x_2+x_3+x_4=3$ where
$0\le x_1\le 1,~0\le x_2\le 1, 0\le x_3\le 2,~0\le x_4\le 3$
$0+0+0+3=3$
$0+0+1+2=3$
$0+1+0+2=3$
$1+0+0+2=3$
$0+0+2+1=3$
$0+1+2+0=3$
$1+0+2+0=3$
$0+1+1+1=3$
$1+0+1+1=3$
$1+1+0+1=3$
$1+1+1+0=3$