Determine Coefficient from Generating Functions

Question

Let $G\colon \mathbb{N}^3\to \mathbb{N}$ be such that $$ \sum_{n=1}^\infty \bigg(\sum_{i=1}^\infty x^i \bigg)^n \bigg(\sum_{j=1}^\infty y^j \bigg)^n\bigg( \sum_{k=1}^\infty z^k\bigg)^n = \sum_{i=1}^\infty \sum_{j=1}^\infty \sum_{k=1}^\infty G(i,j,k) x^i y^j z^k. $$

How can I find a closed form for $G$? This question is related to this one. I am not well versed with generating functions. Any hints are well appreciated.

Answer 1

At first we derive a closed form of the generating function $\mathcal{G}(x,y,z)$ and then we extract the coefficient $G(i,j,k)$ from it.

Generating function: $\mathcal{G}(x,y,z)$

We obtain \begin{align*} \mathcal{G}(x,y,z)&=\sum_{n=1}^\infty\left(\sum_{i=1}^\infty x^i \right)^n \left(\sum_{j=1}^\infty y^j\right)^n\left(\sum_{k=1}^\infty z^k\right)^n\\ &=\sum_{n=1}^\infty\left(\frac{x}{1-x}\right)^n\left(\frac{y}{1-y}\right)^n\left(\frac{z}{1-z}\right)^n\tag{1}\\ &=\sum_{n=1}^\infty\left(\frac{xyz}{(1-x)(1-y)(1-z)}\right)^n\\ &=\frac{xyz}{(1-x)(1-y)(1-z)}\left(1-\frac{xyz}{(1-x)(1-y)(1-z)}\right)^{-1}\tag{2}\\ \end{align*}

We apply in (1) and (2) the formula for the geometric series expansion.

Coefficient extraction: $G(i,j,k)$

We denote with $[x^i]$ the coefficient of $x^i$ in a series. This way we can write \begin{align*} G(i,j,k)&=[x^iy^jz^k]\mathcal{G}(x,y,z)\\ &=[x^i][y^j][z^k]\mathcal{G}(x,y,z) \end{align*}

We obtain \begin{align*} G(i,j,k)&=[x^iy^jz^k]\mathcal{G}(x,y,z)\\ &=\sum_{n=1}^\infty[x^i]\left(\frac{x}{1-x}\right)^n[y^j]\left(\frac{y}{1-y}\right)^n[z^k]\left(\frac{z}{1-z}\right)^n\tag{3} \end{align*}

We have three similar parts and put the focus on the first one.

We obtain \begin{align*} [x^i]\left(\frac{x}{1-x}\right)^n&=[x^i]x^n\sum_{p=0}^\infty\binom{-n}{p}(-x)^p\tag{4}\\ &=[x^{i-n}]\sum_{p=0}^\infty\binom{n+p-1}{p}x^p\tag{5}\\ &=\begin{cases} \binom{i-1}{i-n}\qquad&\qquad 1\leq n\leq i\\ 0\qquad&\qquad\text{otherwise} \end{cases} \end{align*}

Comment:

• In (4) we apply the binomial series expansion

• In (5) we use the rule $[x^{i-n}]A(x)=[x^i]x^nA(x)$. Note that $[x^{i-n}]$ is zero if $i<n$. We also use the binomial identity $\binom{-n}{p}=\binom{n+p-1}{p}(-1)^p$.

Putting all together in (3) we finally obtain

\begin{align*} G(i,j,k)=\sum_{n=1}^{\min\{i,j,k\}}\binom{i-1}{i-n}\binom{j-1}{j-n}\binom{k-1}{k-n}\qquad\qquad 1\leq n\leq i,j,k \end{align*}