Generating function for picking j balls without replacement from an urn

326 Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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$.