# What's the number of natural solutions of $x_1 + 2x_2 + 3x_3 = n$?

$$x_1 + 2x_2 + 3x_3 = n, \qquad x_1, x_2, x_3 \geq 0$$

Find a regression formula (or a recursive function, not sure how it's called in English) to calculate the number of solutions for all $$n≥0$$.

Find the number of solution for $$n=7$$.

So far I only got the following generating function

$$f(x) = \left( \sum_{i=0}^\infty x^i \right) \left( \sum_{i=0}^\infty x^{2i} \right) \left( \sum_{i=0}^\infty x^{3i} \right)$$

• Your last formula seems to be incorrect because these sums diverge. – Hume2 May 26 '19 at 9:44

Your generating function $$f(x)=\sum_{i\geq0}x^i\>\sum_{j\geq0}x^{2j}\>\sum_{k\geq0}x^{3k}={1\over(1-x)(1-x^2)(1-x^3)}$$is correct and leads to the numbers found by @quasi . Write $$f$$ in the partitioned form $$f(x)={1\over6}{1\over(1-x)^3}+{1\over4}{1\over(1-x)^2}+{1\over8}{1\over1-x}+{1\over8}{1\over 1+x}+{1\over3}{1\over 1-x^3}\ .$$ Each of the fractions on the RHS has a simple power series expansion.

• Thanks for the affirmation, could you please explain how to get from the generating function to the final result/formula – Oak Coral May 26 '19 at 15:22
• It's more or less the partial fraction decomposition. – Christian Blatter May 26 '19 at 15:49

I'm not too sure the generating function helps in this case.

Recursively, it is obvious that the number of ways of solving it $$x_1+2x_2=n$$ is just $$\lfloor\frac{n}{2}\rfloor+1$$. Thus the number of ways for solving $$x_1+2x_2+3x_3=n$$ is just $$\sum_{i=0}^{\lfloor \frac{n}{3}\rfloor}\lfloor\frac{i}{2}\rfloor+1$$

(summing over $$i$$s where $$x_3=i$$)

which you can split into cases depending on the parity of $$\lfloor\frac{n}{3}\rfloor$$ and find a closed form expression for.

• The sum should be $$\sum_{\large{{i=0}}}^{\large{\lfloor\frac{n}{3}\rfloor}} \left(\left\lfloor\frac{n-3i}{2}\right\rfloor+1\right)$$ – quasi May 27 '19 at 6:50
• Do you agree with my suggested correction? – quasi May 28 '19 at 10:12

For each integer $$n$$, let $$a(n)$$ be the number of nonnegative integer triples $$(x,y,z)$$ such that $$x+2y+3z=n$$ From the data, the following recursion appears to hold $$a(n)= \begin{cases} \text{if}\;n<0,\;\text{then}\\[3.5pt] \qquad 0\\[2.5pt] \text{else if}\;n=0,\;\text{then}\\[3.5pt] \qquad 1\\[.6pt] \text{else}\\[.4pt] \qquad a(n-1)+a(n-2)-a(n-4)-a(n-5)+a(n-6)\\ \end{cases}$$ In particular, for $$0\le n\le 15$$, we get $$\begin{array} { c|c| c|c|c|c|c| c|c|c|c|c| c|c|c|c|c| } \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline a(n) & 1 & 1 & 2 & 3 & 4 & 5 & 7 & 8 & 10 & 12 & 14 & 16 & 19 & 21 & 24 & 27 \\ \hline \end{array}$$

Note:

I initially thought the recursion could be justified via a straightforward application of the principle of inclusion-exclusion, but the argument eludes me now.

Update:

Using the OP's generating function approach, together with a key idea from the solution by @Christian Blatter, the claimed recursion can be justified as follows . . .

Clearly, $$a(0)=1$$, and $$a(n)=0$$ when $$n < 0$$.

Working formally, we get \begin{align*} &\sum_{n\in\mathbb{Z}}\;a(n)x^n = 1+\sum_{n=1}^\infty\;a(n)x^n \\[6pt] & \phantom{\sum_{n\in\mathbb{Z}}\;a(n)x^n} \,= \left(\prod_{i=0}^\infty x^i\right) \left(\prod_{i=0}^\infty x^{2i}\right) \left(\prod_{i=0}^\infty x^{3i}\right) \\[6pt] & \phantom{\sum_{n\in\mathbb{Z}}\;a(n)x^n} \,= \left(\frac{1}{1-x}\right) \left(\frac{1}{1-x^2}\right) \left(\frac{1}{1-x^3}\right) \\[6pt] \implies\;&\left(\sum_{n\in\mathbb{Z}}\;a(n)x^n\right)\bigl((1-x)(1-x^2)(1-x^3)\bigr)=1 \\[6pt] \implies\;&\left(\sum_{n\in\mathbb{Z}}\;a(n)x^n\right)(1-x-x^2+x^4+x^5-x^6)=1 \\[6pt] \implies\;&a(n)-a(n-1)-a(n-2)+a(n-4)+a(n-5)-a(n-6)=0,\;\text{for all}\;n \ge 1 \\[6pt] \end{align*} which confirms the claimed recursion.

New Update:

Here's another way to justify the claimed recursion . . .

As previously noted, it's clear that for $$n < 0$$, we have $$a(n)=0$$.

By direct evaluation, we get the values $$\begin{array} { c|c|c|c|c|c|c| } \hline n & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline a(n) & 1 & 1 & 2 & 3 & 4 & 5 \\ \hline \end{array}$$ and it's then easily verified that the claimed recursion holds for $$n\le 5$$.

Thus, in what follows, assume $$n\ge 6$$.

Let $$b(n)$$ be the number of nonnegative integer ordered pairs $$(x,y)$$ such that $$x+2y=n$$.

Then for $$a(n)$$, we have the recursion $$a(n)=a(n-3)+b(n)\tag{eq1}$$ and for $$b(n)$$ we have the recursion $$b(n)=b(n-2)+1\tag{eq2}$$ Then from $$(\text{eq}1)$$, we get $$b(n)=a(n)-a(n-3)\tag{eq3}$$ hence $$b(n-2)=a(n-2)-a(n-5)\tag{eq4}$$ Using $$(\text{eq}3)$$ and $$(\text{eq}4)$$ to make replacements for $$b(n)$$ and $$b(n-2)$$ in $$(\text{eq}2)$$ and then solving for $$a(n)$$, we get $$a(n)=a(n-2)+a(n-3)-a(n-5)+1\tag{eq5}$$ hence $$a(n-1)=a(n-3)+a(n-4)-a(n-6)+1\tag{eq6}$$ Subtracting $$(\text{eq}6)$$ from $$(\text{eq}5)$$ and then solving for $$a(n)$$, we get $$a(n)=a(n-1)+a(n-2)-a(n-4)-a(n-5)+a(n-6)$$ which completes the proof of the claimed recursion.