# Number decomposition

Recently I encountered a problem I was not familiar with. So hope someone can help me for this.

Here is the problem. Given any odd integer, how many different ways of decomposition into sum of three differetn positive odd number?

-
Hint: Consider that you can first consider in how many ways you can write your number as a sum of an odd and an even number. And then compute how many ways you have to write an even number as the sum of two odd numbers. And then I have a question, do you want to distinguish sums which differ only by the order of the addends? –  Giovanni De Gaetano Nov 8 '12 at 14:03

I recently watched a video about a generalization of this problem. Euler proved that the number of partitions with odd parts always equals the number of partitions with distinct parts. In this video James Tanton discusses Euler's proof. I think it might help.

-

Lets start with the simpler: given an even positive integer $2m$, how many ways are there to write it as the sum of two different positive odd integers? The smaller can be anything up to $m-1$. Do you count $1+3$ and $3+1$ differently? I will not in what follows. Then there are $m-1$ ways. Let our odd integer be $p$. the largest odd integer can be as large as $p-4$, giving $(p-4)+3+1$. If $p=3k$, the largest odd integer can be as small as $k+2$, if $p=3k+1$ the largest can be as small as $k+3$, and if $p=3k+2$ the largest can be as small as $k+3$. So we have $k_{min}=\lfloor \frac {p+1}3\rfloor+2$, then the number you want is $\sum_{(2i+1)=k_{min}}^{p-4}\frac {p-(2i+1)}2-1$

-

This solution assumes you want ordering to not count as different ways.

First we'll find the number of solutions to $x+y+z=n$ where $0 \le x \le y \le z$. The solution for this is an excerpt from a post on Art of Problem Solving.

We can let $y=x+r$, $z=x+r+s$ where $m, n\in\mathbb{N}_0$ where $\mathbb{N}_0$ denotes the nonnegative integers. Then the equation is $3x+2r+s=n$ where $x, r, s\in\mathbb{N}_0$ with no restrictions. Then we can use generating functions. The generating function for $3x$ is $1+x^3+x^6+\ldots=\frac{1}{1-x^3}$, and similarly the generating function for $2r$ is $\frac{1}{1-x^2}$ and for $s$ it's just $\frac{1}{1-x}$. Now we multiply them together to get $\frac{1}{(1-x)^3(1+x)(1-\omega x)(1-\omega^2x)}$ where $\omega^3=1$.

So we can split this up into $\frac{A}{1-x}+\frac{B}{(1-x)^2}+\frac{C}{(1-x)^3}+\frac{D}{1+x}+\frac{E}{1-\omega x}+\frac{F}{1-\omega^2x}$ which is $$\frac{(1-x)^2(x+1)(x^2+x+1)A+(1-x)(x+1)(x^2+x+1)B+(x+1)(x^2+x+1)C}{(1-x)^3(1+x)(1+x+x^2)} +\frac{(1-x)^3(x^2+x+1)D+(1-x)^3(1+x)(1-\omega^2x)E+(1-x)^3(1+x)(1-\omega x)F}{(1-x)^3(1+x)(1+x+x^2)} =\frac{1}{(1-x)^3(1+x)(1+x+x^2)}$$.

The numerators must be the same for all $x$, so let $x=1$ to find that $6C=1$. We then subtract $\frac{1}{6(1-x)^3}$ from the right side to get

$$\frac{6-(1+x)(1+x+x^2)}{6(1-x)^3(1+x)(1+x+x^2)}=\frac{x^2+3x+5}{6(1-x)^2(1+x)(1+x+x^2)} =\frac{6(1-x)(x+1)(x^2+x+1)A+6(x+1)(x^2+x+1)B}{6(1-x)^2(1+x)(1+x+x^2)}+\frac{6(1-x)^2(x^2+x+1)D+6(1-x)^2(1+x)(1-\omega^2x)E+6(1-x)^2(1+x)(1-\omega x)F}{6(1-x)^2(1+x)(1+x+x^2)}$$.

The numerators must be the same for all $x$, so let $x=1$ to find that $36B=9$. We then subtract $\frac{1}{4(1-x)^2}$ from the right side to get

$$\frac{2(x^2+3x+5)-3(1+x)(1+x+x^2)}{12(1-x)^2(1+x)(1+x+x^2)}=\frac{3x^2+7x+7}{12(1-x)(1+x)(1+x+x^2)}=\frac{12(x+1)(x^2+x+1)A+12(1-x)(x^2+x+1)D+12(1-x)(1+x)(1-\omega^2x)E+12(1-x)(1+x)(1-\omega x)F}{12(1-x)(1+x)(1+x+x^2)}$$.

The numerators must be the same for all $x$, so let $x=1$ to find that $72A=17$. We then subtract $\frac{17}{72(1-x)}$ from the right side to get

$$\frac{6(3x^2+7x+7)-17(1+x)(1+x+x^2)}{72(1-x)(1+x)(1+x+x^2)}=\frac{17x^2+33x+25}{72(1+x)(1+x+x^2)} =\frac{72(x^2+x+1)D+72(1+x)(1-\omega^2x)E+72(1+x)(1-\omega x)F}{72(1+x)(1+x+x^2)}$$.

The numerators must be the same for all $x$, so let $x=-1$ to find that $72D=9$. We then subtract $\frac{1}{8(1+x)}$ from the right side to get

$$\frac{17x^2+33x+25-9(1+x+x^2)}{72(1+x)(1+x+x^2)}=\frac{x+2}{9(1+x+x^2)}=\frac{9(1-\omega^2x)E+9(1-\omega x)F}{9(1+x+x^2)}$$.

The numerators must be the same for all $x$, so let $x=\omega$ to find that $9(1-\omega^2)F=\omega+2=(1+\omega+\omega^2)+1-\omega^2=1-\omega^2$. We then subtract $\frac{1}{9(1-\omega^2x)}$ from the right side to get

$$\frac{x+2-(1-\omega x)}{9(1-\omega x)(1-\omega^2x)}=\frac{1}{9(1-\omega x)} =\frac{9E}{9(1-\omega x)}$$.

So of course $E=\frac{1}{9}$, and finally we get the expansion

$$\frac{1}{(1-x)^3(1+x)(1-\omega x)(1-\omega^2x)}=\frac{17}{72(1-x)}+\frac{1}{4(1-x)^2}+\frac{1}{6(1-x)^3}+\frac{1}{8(1+x)}+\frac{1}{9(1-\omega x)}+\frac{1}{9(1-\omega^2x)}$$.

The generating function for the first term is $\frac{17}{72}(1+x+x^2+\ldots)$, for the second is $\frac{1}{4}(1+2x+3x^2+\ldots)$, for the third is $\frac{1}{6}(1+3x+6x^2+\ldots)$, for the fourth is $\frac{1}{8}(1-x+x^2-\ldots)$, for the fifth is $\frac{1}{9}(1+\omega x+\omega^2 x^2+\ldots)$, and for the sixth is $\frac{1}{9}(1+\omega^2 x+\omega x^2+\ldots)$. Therefore the coefficient of any given term $x^n$ is

$$\frac{17}{72}+\frac{1}{4}(n+1)+\frac{1}{6}\frac{(n+1)(n+2)}{2}+\frac{1}{8}(-1)^n+\frac{1}{9}\omega^n+\frac{1}{9}\omega^{2n}$$

or, simplified further, $$\frac{6n^2+36n+47+9(-1)^n+8\omega^n+8\omega^{2n}}{72}$$.

Now let's return to the original problem. Let $(2x+1)+(2y+1)+(2z+1) = (2k+1)$. Then $x+y+z = k-1$. Now it is clear why our original problem connects with this. So to finish this problem we simply need to compute the number of solutions with $x,y,z$ not distinct. By performing easy casework it is easy to see there are $\lfloor n/2 \rfloor + 1$ solutions with $x,y,z$ not distinct. Thus our final answer to the number of distinct solutions to $(2x+1)+(2y+1)+(2z+1) = (2k+1)$ is simply: $$\frac{6(k-1)^2+36(k-1)+47+9(-1)^{k-1}+8\omega^{k-1}+8\omega^{2k-2}}{72} - 1 - \lfloor n/2 \rfloor$$

-