Ordinary Generating Function for the number of solution :$ x_1 + x_2 + \cdot\cdot\cdot + x_k = n$

Question

Let $a_n$ be the number of solutions of the equation:

$$x_1 + x_2 + \cdot\cdot\cdot + x_k = n$$

where $x_i$ is the positive odd integer.

Hereto I would like to find the ordinary generating function for the sequence $a_n$

ODG has is a function satisfies the below :

$$G(a_n;n) = \sum_0^\infty a_nx^n$$

But what is the typical algorithm to find the ordinary generating function that uniquely determines its coefficient that corresponds to the regarding combinatorial situation?

Anyone can guide me where to start from?

Answer 1

Let $X$ be the set of positive odd numbers.

For any formal power series $f(t) = \sum_{j=0}^\infty f_k t^k$, let $[t^k]f(t)$ be the coefficient $f_k$.

When one expand following product into a series of $t$.

$$\left(\sum_{x_1\in X} t^{x_1}\right)\cdots\left(\sum_{x_k\in X} t^{x_k}\right) = \sum_{x_1,\ldots,x_k \in X} t^{x_1+\ldots + x_k} = \sum_{n=1}^\infty \alpha_n t^n$$

One will notice there is a one-one correspondence between terms contributing to $\alpha_n$ and solution $x_1 + \ldots + x_k = n$ for $(x_1,\ldots,x_k) \in X^k$. For example, in the expansion of $$(t + t^3 + t^5 + \cdots)(t + t^3 + t^5 + \cdots)(t + t^3 + t^5 + \cdots) = x^3+3x^5+6x^7+10x^9 + \cdots $$ There are $6$ terms that contribute to $\alpha_7 = 6$. Namely,

$$ \begin{array}{lcr} (t + t^3 + \color{blue}{t^5} + \cdots) (\color{blue}{t} + t^3 + t^5 + \cdots) (\color{blue}{t} + t^3 + t^5 + \cdots) &\leftrightarrow & 5+1+1 = 7\\ (\color{blue}{t} + t^3 + t^5 + \cdots) (t + t^3 + \color{blue}{t^5} + \cdots) (\color{blue}{t} + t^3 + t^5 + \cdots) &\leftrightarrow & 1+5+1 = 7\\ (\color{blue}{t} + t^3 + t^5 + \cdots) (\color{blue}{t} + t^3 + t^5 + \cdots) (t + t^3 + \color{blue}{t^5} + \cdots) &\leftrightarrow & 1+1+5 = 7\\ (\color{blue}{t} + t^3 + t^5 + \cdots) (t + \color{blue}{t^3} + t^5 + \cdots) (t + \color{blue}{t^3} + t^5 + \cdots)&\leftrightarrow & 1+3+3 = 7\\ (t + \color{blue}{t^3} + t^5 + \cdots) (\color{blue}{t} + t^3 + t^5 + \cdots) (t + \color{blue}{t^3} + t^5 + \cdots)&\leftrightarrow & 3+1+3 = 7\\ (t + \color{blue}{t^3} + t^5 + \cdots) (t + \color{blue}{t^3} + t^5 + \cdots) (\color{blue}{t} + t^3 + t^5 + \cdots)&\leftrightarrow & 3+3+1 = 7\\ \end{array} $$ In general, this leads to

$$\alpha_n = \sum_{n = \sum_{j=1}^k x_j} 1 = a_n \quad\leftarrow \text{ the number of solutions we seek. } $$ Since $\displaystyle\;\sum_{x\in X}t^x = \sum_{j=0}^\infty t^{2j+1} = t \sum_{j=0}^\infty (t^2)^j = \frac{t}{1-t^2},$ the OGF at hand is simply

$$\sum_{n=0}^\infty a_n t^n = \frac{t^k}{(1-t^2)^k} \quad\implies\quad a_n = [t^n] \frac{t^k}{(1-t^2)^k} = [t^{n-k}]\frac{1}{(1-t^2)^k} $$ In order for $a_n \ne 0$, we need $n \ge k$ and $n$ and $k$ has same parity. When this happens, we have $$a_n = [t^{(n-k)/2}] \frac{1}{(1-t)^k} = \binom{\frac{n-k}{2} + k - 1}{\frac{n-k}{2}} = \binom{\frac{n+k}{2}-1}{\frac{n-k}{2}}$$

Note

Above answer is under the assumption we want the number of solutions for a fixed $k$. If one want the number of solutions for a given $n$ but the number of $k$ can vary, the corresponding OGF will be

$$1 + \frac{t}{1-t^2} + \frac{t^2}{(1-t^2)^2} + \cdots = \sum_{k=0}^\infty \left(\frac{t}{1-t^2}\right)^k = \frac{1}{1 - \frac{t}{1-t^2}} = 1 + \frac{t}{1 - t - t^2} $$ The rightmost expression is the famous OGF for Fibonacci numbers. $$\frac{t}{1 - t - t^2} = \sum_{n=1}^\infty F_n t^n$$ This means for any $n > 0$, the number of ways of breaking $n$ into an ordered list of odd numbers $(x_1, \ldots, x_k)$ which sum to $n$ is simply $F_n$.

Answer 2

The generating function is $$ \begin{align} &\left(\sum_{j=0}^\infty x^{2j+1}\right)^k\tag1\\ &=\left(\frac{x}{1-x^2}\right)^k\tag2\\ &=x^k\sum_{j=0}^\infty(-1)^j\binom{-k}{j}x^{2j}\tag3\\ &=\sum_{j=0}^\infty\binom{k+j-1}{j}x^{2j+k}\tag4\\ &=\sum_{n=k}^\infty\binom{\frac{n+k-2}2}{\frac{n-k}2}x^n\ [2|(n-k)]\tag5 \end{align} $$ Explanation:
$(1)$: the exponent of $x$ chosen for each factor
$\phantom{(1)\text{: }}$represents the value chosen for each summand
$(2)$: sum the geometric series
$(3)$: apply the Binomial Theorem
$(4)$: $\binom{-n}{k}=(-1)^k\binom{n+k-1}{k}$ see this answer
$(5)$: $n=2j+k\implies j=\frac{n-k}2\ [2|(n-k)]$ where $[\cdots]$ are Iverson brackets

In step $(1)$, the exponent of $x$ chosen for each factor represents the value chosen for each summand. For example, if $k=4$, $$ \scriptsize\left(\color{#CCC}{x^1+x^3+}x^5\color{#CCC}{+x^7+\cdots}\right)\left(\color{#CCC}{x^1+}x^3\color{#CCC}{+x^5+x^7+\cdots}\right)\left(\color{#CCC}{x^1+x^3+}x^5\color{#CCC}{+x^7+\cdots}\right)\left(\color{#CCC}{x^1+x^3+x^5+}x^7\color{#CCC}{+\cdots}\right) $$ represents the sum $5+3+5+7=20$, and $$ \scriptsize\left(\color{#CCC}{x^1+x^3+}x^5\color{#CCC}{+x^7+\cdots}\right) \left(x^1\color{#CCC}{+x^3+x^5+x^7+\cdots}\right) \left(\color{#CCC}{x^1+x^3+x^5+}x^7\color{#CCC}{+\cdots}\right)\left(\color{#CCC}{x^1+x^3+x^5+}x^7\color{#CCC}{+\cdots}\right) $$ represents the sum $5+1+7+7=20$.