Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
up vote 10 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|cite|improve this answer
This is neat, is there a closed form? – Listing Jul 18 '11 at 11:57
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

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$












share|cite|improve this answer

Your Answer


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.