Number of ways to write $n$ as sum of positive odd integers less than 10

Question

Let $f(n)$ be the number of ways to write $n$ as sum of positive odd integers that each one of them is less than $10$, without any importance to their order. For example: $f(6)=4$ as you can write it as $1+1+1+1+1+1,5+1,3+3,3+1+1+1$. Find a generating function for the series ${f(n)}$.

I've tried finding a recursive relation for $f(n)$ but I got stuck. Thanks

Answer 1

Your $f(n)$ is the coefficient of $x^n$ (I will use the Wilf's notation $[x^n]$) in the product: $$ g(x)=\prod_{k=0}^{4}\sum_{n\geq 0}x^{(2k+1)n} = \prod_{k=0}^{4}\frac{1}{1-x^{2k+1}}\tag{1}$$ $g(x)$ is a meromorphic function with a pole of order $5$ at $x=1$, a pole of order $2$ at $x=\omega$ etc.
You may use the residue theorem to find a partial fraction decomposition for $g(x)$, then recover $[x^n]$ through stars and bars: $$ \frac{1}{(1-\zeta x)^{k+1}}=\sum_{m\geq 0}\binom{k+m}{k}\zeta^m x^m \tag{2}. $$ The main contribute comes from the pole at $x=1$, hence $f(n)$ behaves like a polynomial with degree $4$ in $n$, plus some arithmetical perturbations due to the presence of lower-order poles at the unit circle. Have also a look at restricted partitions.

Answer 2

Hint:
$f(n)=f(n-9)+g(n)$, where $g(n)$ is the number of ways using only 1,3,5,7.
$g(n)=g(n-7)+h(n)$ and so on.

Answer 3

Here is how I would go about it. It doesn't need recursion relations.

First, define $$F(x)\equiv x^1+x^3+x^5+x^7+x^9$$

The coefficient of $x^n$ in $F(x)$ says how many ways there are of making $n$ out of one odd number less than $10$.

The coefficient of $x^n$ in $F(x)^2$ says how many ways there are of making $n$ out of two odd numbers. For instance, for $n=8$, this covers $x^1x^7$, $x^3x^5$, $x^5x^3$, and $x^7x^1$. And indeed, there are four ways of making $8$ out of two odd numbers less than $10$.

In general, the coefficient of $x^n$ in $F(x)^m$ says how many ways there are of making $n$ out of $m$ odd numbers less than $10$.

Thus the generating function which says how many ways there are of making $n$ out of any number of odd numbers less than $10$ is $$\sum_{i=0}^\infty {f(i)x^i}=\sum_{i=0}^\infty{F(x)^i}$$

This is $$\frac{1}{1-F(x)}$$

and $F(x)$ itself is $$F(x)\equiv x\frac{x^{10}-1}{x^2-1}$$

…though I'd check that last equation if I were you!

EDIT: Jack D'Aurizio's answer looks good if you actually want to compute $f(n)$, but your question asked for the generating function.

Answer 4

Each partition can be uniquely identified by how many copies of each number it uses. Hence, we get the generating function:

$$\left(1+x+x^2+\dots\right)\left(1+x^3+x^6+\dots\right)\cdots\left(1+x^9+x^{18}+\dots\right)=\frac{1}{\left(1-x\right)\left(1-x^3\right)\cdots\left(1-x^9\right)}$$