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

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 2

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.

Answer 3

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 4

A partition of a positive integer $n$ is a multiset of positive integers that sum to $n$. We denote the number of partitions of $n$ by $p(n)$. Also, let $p(n, k)$ be the number of partitions of $n$ into "exactly" $k$ parts. Then

$$p(n) = \sum_{k=1}^{n} p(n, k).$$

Now, consider Ferrers diagram, where the $n$th row has the same number of dots as the $n$th term in the partition.

A conjugate of a partition is the Ferrers diagram, where its rows and columns are flipped. For example,

This Ferrers diagram represents the partition $15 = 5 + 4 + 3 + 3$, and the conjugate partition of this is represented as :

where $15 = 4 + 4 + 4 + 2 + 1.$ Using this, we can easily recognize that the number of partitions of $n$ with largest part $k$ is the same as the number of partitions into $k$ parts, which is $p(n, k)$. Now we can conclude that the number of partitions of $n$ with all its parts equal or less than $k$, is the same as the number of partitions with equal or less than $k$ parts.

Now, back to the problem :

$$x+2y+3z = n.$$

Notice something? Now look at this :

$$x \cdot 1 + y \cdot 2 + z \cdot 3 = n.$$

We have to make $n$ with $x$ $1$s, $y$ 2s, and $z$ 3s. This equals the number of partitions of $n$, where each part is equal or less than $3$ - since we can only use $1, 2, 3$. Therefore, here's the final answer :

$$p(n, 3) + p(n, 2) + p(n, 1).$$

and one can easily show that $p(n, 1) = 1,\:\:p(n, 2) = \lfloor \frac{n}{2} \rfloor,\:\:p(n, 3) = \rm{round} \left( \frac{n^{2}}{12} \right)$ where the round function gives the nearest integer.

Finally the answer is :

$$\boxed{1 + \lfloor \frac{n}{2} \rfloor + \rm{round} \left( \frac{n^{2}}{12} \right)}$$

and we get $8$ for $n=7$. Read this for more explanation on the identity I used(and Ferrers diagram).