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

Question

$$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)$$

Answer 1

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.

Answer 2

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.

Answer 3

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.