Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
    
This is neat, is there a closed form? –  Listing Jul 18 '11 at 11:57
1  
Not 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{\pro‌​d_{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) –  Dennis Gulko Jul 18 '11 at 12:22
    
-Dennis ok, generating functions, u reminded me something i learned years ago. –  colinfang Jul 18 '11 at 12:22
add comment

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$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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