7
$\begingroup$

I'm trying to get a closed form for the generating function which counts the number of non-negative integer solutions to

$2e_1+3e_2+5e_3 = N$

I note that we have something like:

$\frac{1}{(1-x^2)(1-x^3)(1-x^5)}$

but can't get something to translate nicely. I've thought of using $e^{2x} e^{3x} e^{5x}$, but is it valid?

3 Answers 3

7

If you are willing to deal with complex numbers, you can use a partial fraction expansion.

For any polynomial $\displaystyle P(x) = \prod_{j=1}^{n}(x-\alpha_j)$ with distinct roots, we have that

\frac{1}{P(x)} = \sum_{j=1}^{n} \frac{1}{P'(\alpha_j)(x-\alpha_j)} = -\sum_{j=1}^{n} \frac{1}{\alpha_jP'(\alpha_j)(1- \frac{x}{\alpha_j})}

You can expand out every $\displaystyle \frac{1}{1 - \frac{x}{\alpha_j}}$ in an infinite power series and add them to give on single series, giving a formula for the coefficients, in terms of the $\displaystyle \alpha_j$.

In your case, we can write the denominator as $\displaystyle (1-x)^3 P(x)$, where $\displaystyle P(x)$ is a polynomial with distinct complex roots, and the above partial fraction expansion can be used as

\frac{1}{(1-x)^3 P(x)} = \frac{1}{(1-x)^3}\sum_{j=1}^{n} \frac{1}{P'(\alpha_j)(x-\alpha_j)}

Now you can use the binomial theorem (yes, it works for negative numbers, but you get an infinite series) for the $\displaystyle \frac{1}{(1-x)^3}$ portion and you get a closed form formula, involving complex numbers, which you can ultimately convert into a "real number only" formula using $\displaystyle \cos$ and $\displaystyle \sin$.

Or if you want to simplify it further, you can try using an expansion of the form

$\frac{1}{(1-x)^3 P(x)} = \frac{A}{1-x} + \frac{B}{(1-x)^2} + \frac{C}{(1-x)^3} + \sum_{j=1}^{n} \frac{D_j}{x-\alpha_j}$

which should give a closed form, which uses a "constant number of terms" to compute the coefficient of $x^N$.

3

You can use the multinomial theorem to expand: $ f(x)=\frac1{(1-x^2)(1-x^3)(1-x^5)} =\prod_{d\in\{2,3,5\}}\left(\sum_{n=0}^\infty x^{dn}\right) =\sum_{n=0}^\infty c_n x^n $ for $c_n=\sum_{2a+3b+5c=n}{n\choose{a,b,c}}.$ However, this doesn't give us the closed form that you want. I admit, I prefer @Aryabhata's answer. In any case, the above shows (and particularly the summations in parentheses) how to expand $(1-x^d)^{-1}$ as power series, and that they're not exponentials but geometric series.

The way above (here) is just showing how the generating function answers the combinatorial question. But it doesn't give us any advantage when it comes time to calculate, say, the number of ways to get $N=12$. We still need to enumerate the set $ \{(a,b,c)\in\mathbb{N}^3 \mid 2a+3b+5c=12 \} =\{ (1,0,2),~ (2,1,1),~ (0,4,0),~ (3,2,0),~ (6,0,0) \} $ used to find $c_{12}=5$ ourselves.

  • 0
    the partial fraction stuff would be used, but I a$m$ lost on that setup also2012-03-28
3

According to Maple:

convert(1/(1-x^2)/(1-x^3)/(1-x^5),parfrac,x);

$-1/30\, \left( x-1 \right) ^{-3}+1/8\, \left( x+1 \right) ^{-1}-{ \frac {77}{360}}\, \left( x-1 \right) ^{-1}+1/5\,{\frac {2+x+{x}^{2}+{ x}^{3}}{{x}^{4}+{x}^{3}+{x}^{2}+x+1}}+{\frac {7}{60}}\, \left( x-1 \right) ^{-2}+1/9\,{\frac {-x+1}{{x}^{2}+x+1}}$

map(convert, %, FPS, x);

$\sum _{k=0}^{\infty } \left( \sum _{{\it \alpha}={\it RootOf} \left( {{\it \_Z}}^{4}+{{\it \_Z}}^{3}+{{\it \_Z}}^{2}+{\it \_Z}+1 \right) }- 1/25\,{\frac {{x}^{k} \left( -2\,{\it \alpha}+1+{{\it \alpha}}^{2} \right) }{{{\it \alpha}}^{k+1}}} \right) +\sum _{k=0}^{\infty } \left( -{\frac {1}{54}}\, \left( -\sqrt {3}+3\,i \right) \sqrt {3} \left( -1/2-1/2\,i\sqrt {3} \right) ^{k}-{\frac {1}{54}}\,i\sqrt {3} \left( -3+i\sqrt {3} \right) \left( -1/2+1/2\,i\sqrt {3} \right) ^{k } \right) {x}^{k}+\sum _{k=0}^{\infty }{\frac {77}{360}}\,{x}^{k}+ \sum _{k=0}^{\infty } \left( {\frac {7}{60}}+{\frac {7}{60}}\,k \right) {x}^{k}+\sum _{k=0}^{\infty }1/8\, \left( -1 \right) ^{k}{x}^ {k}+\sum _{k=0}^{\infty } \left( 1/30+1/20\,k+{\frac {1}{60}}\,{k}^{2} \right) {x}^{k}$