5

Given $n \in \mathbb{N}$ how many ways can one write $n=a+2b+3c$ for $a,b,c \in \mathbb{N}$.

I have an idea as if I use a a 3-tuple to represent $(a,b,c)$, I can list all of them using two functions $f((a,b,c)) = (a-2,b+1,c)$ and $g((a,b,c)) = (a-1,b-1,c+1)$. Which makes a nice pattern that should be easy to compute for any n however I'm struggling finding an actual equation that works everytime. Right now I have one that works sometimes being; Let $x = \left \lfloor{n/2}\right \rfloor $, $y = \left \lfloor{n/6}\right \rfloor $ and $z = x-y$. Then the function $f(n)$ is the count. $f(n) = 1+x+(c/2)(c+1)+bc-b(b+1)$. However I know it's wrong.

EDIT: Sorry forgot to add that f(n) should be a function of just n.

jjhhbb9
  • 93
  • What do you know about generating functions? – user Apr 21 '19 at 20:37
  • Not an extensive amount, always just managed to figure it out. – jjhhbb9 Apr 21 '19 at 20:39
  • and to kingW6, taking the first few terms $f(1) = 1, f(2)= 2, f(3)= 3$ we see that $f(4) = f(3) + 2f(2) + 3f(1) = 3 + 4 + 3 = 10$ but $f(4) = 4$ – jjhhbb9 Apr 21 '19 at 20:41
  • A previous effort i had $f(n) = 1 + \left \lfloor{n/2}\right \rfloor + \left \lfloor{n/3}\right \rfloor + f(n-5)$ where $f(n) = 0$ for $n \leq 0$ – jjhhbb9 Apr 21 '19 at 20:45

2 Answers2

0

$f(n)$ satisfies the recurrence $$ f(n) = f(n-1)+f(n-2)-f(n-4)-f(n-5)+f(n-6)\tag{$n\ge 1$} $$ This can be proven using the principle of inclusion exclusion, similarly to this answer. Let $E^n$ be the set of triples $(a,b,c)$ for which $a+2b+3c=n$, so $f(n)=|E^n|$. Furthermore, let

  • $E^n_1=\{(a,b,c)\in E^n\mid a\ge 1\}$
  • $E^n_2=\{(a,b,c)\in E^n\mid b\ge 1\}$
  • $E^n_3=\{(a,b,c)\in E^n\mid c\ge 1\}$

Using the principle of inclusion exclusion, you can show for any $n\ge 1$ that $$ |E^n|=|E^n_1|+|E^n_2|+|E^n_3|-|E^n_1\cap E^n_2|-|E^n_1\cap E^n_3|-|E^n_2\cap E^n_3|+|E^n_1\cap E^n_2\cap E^n_3| $$ Furthermore, you can show $|E^n_1|=|E^{n-1}|$, via the bijection $(a,b,c)\mapsto (a-1,b,c)$, and $|E^n_1\cap E^n_2|=E^{n-3}$ via $(a-1,b-2,c)$. Using similar bijections, you get the recurrence advertised above.

Anyways, solving the above linear recurrence after determining the base cases yields $$ f(n)= \frac1{72}(6n^2+36n+9(-1)^n+16\cos(2\pi n/3) + 47) $$ I got this from Wolfram|Alpha.

Mike Earnest
  • 75,930
0

Let $f(n)$ be the number of ways of making $n$ as a sum of only $1$s, $g(n)$ be the number of ways of making $n$ as a sum of only $1$s and $2$s, and $h(n)$ be the number of ways of making $n$ as a sum of only $1$s, $2$s, and $3$s.

It should be obvious that $f(n) = 1$.

$g(0) = f(0) = 1$ and $g(1) = f(1) = 1$, since there will not be any $2$s for these small numbers. For $n \ge 2$, $g(n) = f(n) + g(n - 2) = 1 + g(n-2)$.

For $n \lt 3$, $h(n) = g(n)$. For $n \ge 3$, $h(n) = g(n) + h(n-3)$.

$$ h(n) - h(n-3) = g(n)\\ g(n) - g(n-2) = 1\\ h(n) - h(n-3) - (h(n-2) - h(n-5)) = 1\\ h(n) - h(n-2) - h(n-3) + h(n-5) = 1\\ h(n-1) - h(n-3) - h(n-4) + h(n-6) = 1\\ h(n) - h(n-1) - h(n-2) - h(n-3) + h(n-3) + h(n-4) + h(n-5) - h(n-6) = 1 - 1 = 0\\ h(n) = h(n-1) + h(n-2) - h(n-4) - h(n-5) + h(n-6)\\ $$

So now we've got a linear recurrence. For the Fibonacci linear recurrence, $F(n) = F(n-1) + F(n-2)$, which has a related polynomial of $x^2 - x - 1$, and that polynomial has roots $\frac{1 \pm \sqrt{5}}{2}$, and the closed form of the Fibonacci series is based on a linear combination of exponentials of those roots, $Fib(n) = k_1 \left(\frac{1 + \sqrt{5}}{2}\right)^n + k_2\left(\frac{1 - \sqrt{5}}{2}\right)^n$.

So the polynomial associated with the $h(n)$ recurrence is $x^6 - x^5 - x^4 + x^2 + x - 1$. That factors to $ (x + \frac12 + \frac{\sqrt{3}}{2}i)(x + \frac12 - \frac{\sqrt{3}}{2}i) (x - 1)^3 (x + 1)$ That translates into a closed form expression of the form $(k_1 + k_2 n + k_3 n^2)(1)^n + k_4(-1)^n + k_5(-\frac12 - \frac{\sqrt{3}}{2}i)^n + k_6(-\frac12 + \frac{\sqrt{3}}{2}i)^n$.

NovaDenizen
  • 4,216
  • 15
  • 23