1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Your last formula seems to be incorrect because these sums diverge. $\endgroup$ – Hume2 May 26 at 9:44
3
$\begingroup$

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.

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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) $$ $\endgroup$ – quasi May 27 at 6:50
  • 1
    $\begingroup$ Do you agree with my suggested correction? $\endgroup$ – quasi May 28 at 10:12
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.