Stuck on generating operating functions.

38 Views Asked by At

Find the ordinary generating function associated with the problem of finding the number of solutions in nonnegative integers of the equation

$$2a + 3b + 2c + d = r.$$

1

There are 1 best solutions below

0
On

Given any finite sequence of positive integers

$$[k] \stackrel{def}{=} (k_1, k_2, \ldots k_m), \quad k_1, k_2, \ldots, k_m \in \mathbb{Z}_{+}$$

Let $\mathcal{N}_{[k]}(r)$ be the number of non-negative integer solutions for the equation

$$k_1 x_1 + k_2 x_2 + \ldots + k_m x_m = r, \quad x_1, x_2, \ldots, x_m \in \mathbb{N}$$

Let $f_{[k]}(t)$ be the corresponding ordinary generating function:

$$f_{[k]}(t) = \sum_{r=0}^\infty \mathcal{N}_{[k]}(r) t^r$$

If we have two finite sequences of positive integers $[k] = (k_1, k_2,\ldots,k_m)$ and $[\ell] = (\ell_1, \ell_2,\ell,\ell_m)$, we can concatenate them to form another finite sequence $$[k\ell]\stackrel{def}{=} (k_1,k_2,\ldots,k_m,\ell_1,\ell_2,\ldots,\ell_n)$$

The corresponding generating functions simply multiply. More precisely.

$$f_{[k\ell]}(t) = f_{[k]}(t) f_{[\ell]}(t)$$

When the finite sequence $[k] = (\alpha)$ consists of a single entry, i.e the underlying equation has the form $\;\alpha x = r\;$, the corresponding generating function is $$f_{(\alpha)}(t) = 1 + t^\alpha + t^{2\alpha} + \cdots = \frac{1}{1 - t^\alpha}$$
This implies the generating function for the equation $$\color{red}{2 a} + \color{orange}{3 b} + \color{green}{2c} + \color{blue}{d} = r$$ is simply $$ \left(\color{red}{\frac{1}{1-t^2}}\right) \left(\color{orange}{\frac{1}{1-t^3}}\right) \left(\color{green}{\frac{1}{1-t^2}}\right) \left(\color{blue}{\frac{1}{1-t}}\right) = \frac{1}{(1-t)(1-t^2)^2(1-t^3)}$$