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.

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

In an urn, each balls is labeled with one of $\{0,1,2,...,k\}$. For each $i\in{0,1,2,...,k}$, there are exactly $n_i$ balls labeled $i$. Let $f(x)=\sum\limits_{i=0}^k n_ix^i$. Let $g(x)=\sum\limits_{i=0}^{jk}a_ix^i$ where $a_i$ is the number of ways drawing uniformly randomly without replacement $j$ balls from the urn with a sum of $i$.

For drawing with replacement $g(x)=f(x)^j$. Is there a nice generating function $g$ dependent on $f$ for the case of drawing without replacement?

share|cite|improve this question
The first sentence is sort of unclear. The urn has $\sum_{i=0}^{k}n_i$ balls in it, not $n_i$, right? – user2357112 Jun 17 '14 at 21:38
Are two balls with the same label considered distinct? – user2357112 Jun 17 '14 at 21:42
@user2357112 Judging from the OP's statement that drawing with replacement gives $g=f^j$, it seems the answers to your questions are "yes" and "yes." – angryavian Jun 17 '14 at 21:48
@angryavian's answer is what I intended. user2357112, however, I have edited the problem statement to make it clearer. – Hans Jun 17 '14 at 22:56
up vote 2 down vote accepted

Let $B$ be the set of balls and $\mathrm{label}(b)$ be the label of a ball. Then we have the following multivariable generating function:

$$\prod_{b\in B}(1+xy^{\mathrm{label}(b)})$$

The number of ways to choose $j$ balls with a sum of $i$ is the coefficient of $x^jy^i$.

share|cite|improve this answer
Nice. Is there an even simpler construction, say with just one variable? – Hans Jun 17 '14 at 22:54
@Hansen: Not that I could find. There doesn't seem to be a simple way to build the values for a given $j$ without using the values for lower $j$. – user2357112 Jun 18 '14 at 0:23

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.