Find number of solutions $m+3n+5p \le 600$

Question

Generally, I am solving this task:

Find number of solutions $m+3n+5p \le 600$

My try

$$(1+t+t^2...)(1+t^3+t^6+...)(1+t^5+t^{10}+...) = \frac{1}{1-t}\frac{1}{1-t^3}\frac{1}{1-t^5} $$

Now I should have $\frac{1}{1-t}\frac{1}{1-t^3}\frac{1}{1-t^5}$ in form of sum of terms like $\frac{C}{(1-\lambda t)^n}$ so I want to partition my product. But how can I do this effectively? In that post author state that like this is easy observation, but I don't know how to start with that.

Answer 1

A few comments. First, since you are looking for the number of solutions where $m+3n+5p\leq 600$, you want the sum of the coefficients of $1,t,\ldots, t^{600}$ in the power series

$$f(t)=\frac{1}{(1-t)(1-t^3)(1-t^5)},$$

but it is easier to say that you want the coefficient of $t^{600}$ in

$$g(t)=\frac{f(t)}{1-t}=\frac{1}{(1-t)^2(1-t^3)(1-t^5)}.$$

Second, the whole point of having a partial fraction decomposition is so that you have an easy way to determine the coefficients, and you can do that for $\frac{p(t)}{(1-t^n)^k}$ for any polynomial $p$ and any $n,k$, so breaking things up into linear terms isn't necessary.

Factoring the denominator into relatively prime components (which essentially just means factoring $(1-t)$ from each factor), we have

$$g(t)=\frac{f(t)}{1-t}=\frac{1}{(1-t)^4(1+t+t^2)(1+t+t^2+t^3+t^4)}.$$

This suggests looking for a partial fraction decomposition of the form

$$\frac{A}{(1-t)} + \frac{B}{(1-t)^2}+\frac{C}{(1-t)^3}+\frac{D}{(1-t)^4}+\frac{E+Ft}{(1+t+t^2)}+\frac{G+Ht+It^2+Jt^3}{(1+t+t^2+t^3+t^4)}$$

and then multiplying the last two terms by $(1-t)$ on both the top and the bottom.

In this form, you will be able to find the coefficient of $t^{600}$ from standard formulas.

I'm not sure if there is a better way to do this than to pick 10 values of t to set up 10 linear equations in 10 variables and solve by row reduction, at least if you're doing it by hand.

Edit: I want to briefly add an explanation for why I divided by $1-t$.

If $f(t)=\sum a_i t^i$ and $(1-t)^{-1}=\sum t^i$, then

$$\frac{f(t)}{1-t)}=(1+t+t^2+t^3+\ldots)(a_0+a_1t+a_2t^2+a_3t^3+\ldots)=(a_0+(a_0+a_1)t+(a_0+a_1+a_2)t^2+(a_0+a_1+a_2+a_3)t^3+\ldots$$

So dividing the generating function of a sequence by $(1-t)$ gives the generating function of the partial sums.

Answer 2

COMMENT.-It seems to me that you use a Combinatorial technique to find the number of solutions of your linear equation with three unknowns. I would be interested to know how the matter is. On the other hand in your search of fractions "like $\frac {C} {(1- \lambda t) ^ n}$" as you say, I can only find the following $$\frac{t+2}{9(t^2+t+1)}+\frac{t^3+t^2+2t+1}{5(t^4+t^3+t^2+t+1)}-\frac{14}{45(t-1)}+\frac{1}{5(t-1)^2}-\frac{1}{15(t-1)^3}$$ Can this decomposition help you find the number of solutions mentioned above? I thank you if you tell me the way it should be done.