How would you find the number of solutions to $m_1+2m_2+3m_3=n$?

Question

Assuming $m_i$ are nonnegative integers

I understand that we need to use $C(n+k-1,n-1)$ here but I am not sure how the coefficients of $m_i$ affect the equation?

For example to find the number of solutions to $m_1+m_2+m_2=n$, we could use the equation above to find that it is $C(n+2,2)=\frac{1}{2}(n+2)(n+1)$

Answer 1

I'm presuming $n$ is given. The answer (call it $f(n)$) is the coefficient of $x^n$ in the Taylor expansion of the generating function $$ g(x) = (1+x+x^2 + \ldots)(1+x^2 + x^4 +\ldots)(1 + x^3 + x^6 + \ldots) = \frac{1}{(1-x)(1-x^2)(1-x^3)}$$ Using partial fractions, $$ g(x) = \frac{1}{6(1-x)^3} + \frac{1}{4(1-x)^2} + \frac{1}{8(1+x)} + \frac{17}{72(1-x)} + \frac{2+x}{9(1+x+x^2)}$$ and we can write $$ f(n) = \frac{47}{72} + \frac{n}{2} + \frac{n^2}{12} + \frac{(-1)^n}{8} + \frac{\omega^n + \overline{\omega}^n}{9} $$ where $\omega = (-1 + i \sqrt{3})/2$.

Hmm, seems to be OEIS sequence A001399

Answer 2

We can write a statement that is not easy to calculate and try to simplify:

We know $0\le m_3 \le \left\lfloor \dfrac{n}{3}\right\rfloor$ and once we have chosen $m_3$, $0\le m_2 \le \left\lfloor\dfrac{n-3m_3}{2}\right\rfloor$. And for every choice of $m_3$ and $m_2$, there is exactly one choice of $m_1$, which yields the summation:

$$\sum_{m_3=0}^{\left\lfloor \tfrac{n}{3}\right\rfloor}\sum_{m_2=0}^{\left\lfloor \tfrac{n-3m_3}{2}\right\rfloor} 1 = \sum_{m_3=0}^{\left\lfloor \tfrac{n}{3}\right\rfloor}\left(\left\lfloor\dfrac{n-3m_3}{2}\right\rfloor+1\right)$$

Plugging this into Wolframalpha gives:

$$ = \left\lfloor \dfrac{n}{3} \right\rfloor + \left\lfloor \dfrac{n - 3}{2} \right\rfloor \left(\left\lfloor \dfrac{ \left\lfloor \dfrac{n}{3} \right\rfloor-1 }{2} \right\rfloor+1\right) + \dfrac{1}{2} \left( -3 \left\lfloor \dfrac{ \left\lfloor \dfrac{n}{3} \right\rfloor -1 }{2} \right\rfloor^2 - 3 \left\lfloor \dfrac{ \left\lfloor \dfrac{n}{3} \right\rfloor -1 }{2} \right\rfloor - 3 \left\lfloor \dfrac{ \left\lfloor \dfrac{n}{3} \right\rfloor }{2}\right\rfloor^2 - 3 \left\lfloor\dfrac{ \left\lfloor \dfrac{n}{3} \right\rfloor }{2} \right\rfloor + 2 \left\lfloor\dfrac{n}{2}\right\rfloor \left( \left\lfloor \dfrac{ \left\lfloor \dfrac{n}{3}\right\rfloor }{2}\right\rfloor + 1\right) + 2\right)$$

Answer 3

Getting a closed form requires a bit more than elementary counting techniques, but it’s not too hard to find a fairly simple recurrence for the number of solutions.

Let $a_n$ be the number of solutions in non-negative integers to $m_1+2m_2+3m_3=n$. Every solution with $m_2>0$ can be obtained from a unique solution to $a+2b+3c=n-2$ by setting $m_1=a$, $m_2=b+1$, and $m_3=c$. Similarly, every solution with $m_3>0$ can be obtained from a unique solution to $a+2b+3c=n-3$ by setting $m_1=1$, $m_2=b$, and $m_3=c+1$. We can’t simply add these two figures, because every solution with both $m_2$ and $m_3$ positive is counted in both of those calculations. However, each of these can be obtained from a unique solution to $a+2b+3c=n-5$ by setting $m_1=a$, $m_2=b+1$, and $m_3=c+1$, so $m_1+2m_2+3m_3=n$ has $a_{n-2}+a_{n-3}-a_{n-5}$ solutions with at least one of $m_2$ and $m_3$ positive. It has exactly one solution with $m_2=m_3=0$, namely, $m_1=n$, so we have the recurrence

$$a_n=1+a_{n-2}+a_{n-3}-a_{n-5}\;.$$

By direct calculation we find the initial conditions $a_0=1$ and $a_n=n$ for $n=1,2,3,4$.