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.

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|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 at 21:38
Are two balls with the same label considered distinct? –  user2357112 Jun 17 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 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 at 22:56

1 Answer 1

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|improve this answer
Nice. Is there an even simpler construction, say with just one variable? –  Hans Jun 17 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 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.