# Selection of balls with Generating Functions

There is an unlimited number of red, white and green balls. How many ways can we select $$~n~$$ balls with each selection having an even number of green balls?

How to decide whether the function to be used is ordinary or exponential?

• I'd have thought it was best to work recursively. Either the first $n-1$ are a "good" selection and the $n^{th}$ choice is red or white, or the first $n-1$ is a bad selection and the $n^{th}$ is green.
– lulu
Jun 26 '19 at 22:35
• Do you care about order?
– amd
Jun 27 '19 at 0:43

We typically use ordinary generating functions when counting unlabelled objects and exponentially generating functions when counting labelled objects.

Since here we have unlabelled (not marked e.g. with numbers) red, white and green balls we use ordinary generating functions and obtain \begin{align*} \color{blue}{[x^n]}&\color{blue}{\left(1+x+x^2+\cdots\right)^2\left(1+x^2+x^4+\cdots\right)}\tag{1}\\ &=[x^n]\left(\frac{1}{1-x}\right)^2\frac{1}{1-x^2}\\ &=[x^n]\sum_{j=0}^\infty\binom{-2}{j}(-x)^j\sum_{k=0}^\infty x^{2k}\tag{2}\\ &=[x^n]\sum_{j=0}^\infty(j+1)x^j\sum_{k=0}^\infty x^{2k}\tag{3}\\ &=\sum_{j=0}^n (j+1)[x^{n-j}]\sum_{k=0}^\infty x^{2k}\tag{4}\\ &=\sum_{j=0}^n (n-j+1)[x^j]\sum_{k=0}^\infty x^{2k}\tag{5}\\ &=\sum_{j=0}^{\lfloor n/2\rfloor} (n-2j+1)[x^{2j}]\sum_{k=0}^\infty x^{2k}\tag{6}\\ &=\sum_{j=0}^{\lfloor n/2\rfloor} (n-2j+1)\tag{7}\\ &=(n+1)\left(\left\lfloor\frac{n}{2}\right\rfloor+1\right)-2\sum_{j=0}^{\lfloor n/2\rfloor} j\\ &=(n+1)\left(\left\lfloor\frac{n}{2}\right\rfloor+1\right)-\left\lfloor\frac{n}{2}\right\rfloor\left(\left\lfloor\frac{n}{2}\right\rfloor+1\right)\\ &\,\,\color{blue}{=\left(\left\lfloor\frac{n}{2}\right\rfloor+1\right)\left(n+1-\left\lfloor\frac{n}{2}\right\rfloor\right)} \end{align*}

Comment:

• In (1) we encode the unlimited number of red and white balls with $$1+x+x^2+\cdots$$ and unlimited even number of green balls with $$1+x^2+x^4+\cdots$$. We use the coefficient of operator $$[x^n]$$ to denote the coefficient of $$x^n$$ of a series.

• In (2) we use the binomial and geometric series expansion.

• In (3) we use the binomial identity $$\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$$.

• In (4) we apply the rule $$[x^{p-q}]A(x)=[x^p]x^qA(x)$$ and set the upper limit of the series to $$n$$ since other terms do not contribute.

• In (5) we change the order of summation $$j\to n-j$$.

• In (6) we use even indices $$j$$, since other terms do not contribute.

• In (7) we select the coefficient of $$x^{2j}$$.

Note: This answer provides some basic information regarding the difference of ordinary and exponential generating functions. It is based upon the great presentation of admissible structures in chapter 1 and 2 of Analytic Combinatorics by P. Flajolet and R. Sedgewick.

One way to decide whether an ordinary or exponential generating function is more appropriate is to look at the way that it will be, in Wilf’s words, “stitched together” from other generating functions. Assuming that you’re interested in combinations rather than permutations, we’re looking for the number of ways to express $$n$$ as the sum $$2r+g+b$$ for $$r,g,b\ge0$$, or, loosely, to compute $$\sum_{2r+b+g=n}1.$$ This matches the pattern for products of o.g.f.s: if $$f$$ is the o.g.f. for the sequence $$\{a_n\}$$ and $$g$$ the o.g.f. for $$\{b_n\}$$, then $$fg$$ is the o.g.f. for $$\left\{\sum_{r=0}^na_rb_{n-r}\right\}$$. In contrast, the product of two e.g.f.s is the e.g.f. for $$\left\{\sum_{r=0}^n\binom nr a_rb_{n-r}\right\}$$.

Continuing, then, the sequence that we want is the convolution of $$(1,1,1,1,\dots)$$, $$(1,1,1,1,\dots)$$ and $$(1,0,1,0,\dots)$$, which has the o.g.f. $$g(z) = \frac1{1-z}\frac1{1-z}\frac1{1-z^2} = \frac1{(1-z)^3}\frac1{1+z}.$$ Now, $$f(z)/(1-z)$$ is the o.g.f. for the sequence of partial sums of the sequence represented by $$f(z)$$, so we immediately have the triple sum $$[z^n]\,g(z) = \sum_{i=0}^n \sum_{j=0}^i \sum_{k=0}^j (-1)^k.$$ To derive a closed formula for $$[z^n]\,g(z)$$, a standard way to proceed is to rewrite $$g(z)$$ as $${A\over 1+z} + {B+Cz+Dz^2\over(1-z)^3}$$ so that \begin{align} [z^n]\,g(z) &= A [z^n]\frac1{1+z} + B [z^n]\frac1{(1-z)^3} + C [z^{n-1}]\frac1{(1-z)^3} + D [z^{n-2}]\frac1{(1-z)^3} \\ &= A(-1)^n + B\binom{n+2}2+C\binom{n+1}2 + D\binom n2.\end{align} I’ll leave determining the coefficients to you.