# Sum up to number $N$ using $1,2$ and $3$

So the question asked was finding out the number of ways(combinations), a given number $N$ can be formed using the sum of $1,2$ or $3$. (eg) For $n = 8$, the answer is $10$

The given solution for this is simply $$\left\lfloor\frac{(N+3)^2}{12}\right\rfloor$$ But I don't understand how this is working ?

-
–  kaine Mar 19 '13 at 17:59
Is $1+2+3=1+3+2$ considered the same sum, or different? I'm guessing the same, but not sure. –  Thomas Andrews Mar 19 '13 at 18:00
@Shu Xiao Li: I won’t change it back, but in general I think that it’s better to keep the OP’s expression when it’s not actually wrong. –  Brian M. Scott Mar 19 '13 at 18:01
Do you know about generating functions? –  Thomas Andrews Mar 19 '13 at 18:05
@Ross: Given the statement that for $n=8$ the answer is $10$, $1+2$ and $2+1$ must be considered the same. The OP is counting partitions whose parts are at most $3$, not compositions. –  Brian M. Scott Mar 19 '13 at 18:05

Essentially, you need to find the number of non-negative integers $(a,b,c)$, such that $$a+2b+3c = n$$Note that $c \in \left\{0,1,\ldots, \left\lfloor\dfrac{n}3 \right\rfloor \right\}$. For a fixed $c$, $b \in \left\{0,1,\ldots, \left\lfloor\dfrac{n-3c}2 \right\rfloor \right\}$. Hence, the number of ways is $$S(n) = \sum_{c=0}^{\lfloor n/3 \rfloor} \left(1 + \left\lfloor\dfrac{n-3c}2 \right\rfloor\right) = 1 + \lfloor n/3 \rfloor + \sum_{c=0}^{\lfloor n/3 \rfloor} \left\lfloor\dfrac{n-3c}2 \right\rfloor$$

If $n=6k$, we have $$S(n) = 1 + 2k + \sum_{c=0}^{2k} \left \lfloor\dfrac{6k-3c}2\right \rfloor$$ \begin{align} \sum_{c=0}^{2k} \left \lfloor\dfrac{6k-3c}2\right \rfloor &= \sum_{c=0,2,}^{2k} \dfrac{6k-3c}2 + \sum_{c=1,3}^{2k-1} \dfrac{6k-3c-1}2 = \sum_{c=0}^{2k} \left(3k - \dfrac32 c \right) - \dfrac{k}2\\ & = 3k(2k+1) - \dfrac32 \times k(2k+1) - \dfrac{k}2 = k \left(6k+3-3k-\dfrac32 - \dfrac12\right)\\ & = k(3k+1) = \dfrac{n(n+2)}{12} \end{align} Hence, $$S(n) = 1 + \dfrac{n}3 + \dfrac{n(n+2)}{12} = 1 + \dfrac{n(4+n+2)}{12} = \dfrac{n^2 + 6n + 12}{12}$$ (Note: If $n=0$, there is one way to represent $0$ as a sum of $1$, $2$ and $3$ i.e. $0=0 \times 1 + 0 \times 2 + 0 \times 3$.)

If $n=6k+1$, we have $$S(n) = 1 + 2k + \sum_{c=0}^{2k} \left \lfloor\dfrac{6k+1-3c}2\right \rfloor$$ \begin{align} \sum_{c=0}^{2k} \left \lfloor\dfrac{6k+1-3c}2\right \rfloor &= \sum_{c=0,2,}^{2k} \dfrac{6k-3c}2 + \sum_{c=1,3}^{2k-1} \dfrac{6k+1-3c}2 = \sum_{c=0}^{2k} \left(3k - \dfrac32 c \right) + \dfrac{k}2\\ & = 3k(2k+1) - \dfrac32 \times k(2k+1) + \dfrac{k}2 = k \left(6k+3-3k-\dfrac32 + \dfrac12\right)\\ & = k(3k+2) = \dfrac{n-1}6 \cdot \dfrac{n+3}2 = \dfrac{n^2 + 2n - 3}{12} \end{align} Hence, $$S(n) = 1 + \dfrac{n-1}3 + \dfrac{n^2 + 2n - 3}{12} = \dfrac{n^2 + 6n + 5}{12}$$

If $n=6k+2$, we have $$S(n) = 1 + 2k + \sum_{c=0}^{2k} \left \lfloor\dfrac{6k+2-3c}2\right \rfloor$$ \begin{align} \sum_{c=0}^{2k} \left \lfloor\dfrac{6k+2-3c}2\right \rfloor &= \sum_{c=0,2,}^{2k} \dfrac{6k+2-3c}2 + \sum_{c=1,3}^{2k-1} \dfrac{6k+1-3c}2 = \sum_{c=0}^{2k} \left(3k + 1 - \dfrac32 c \right) - \dfrac{k}2\\ & = (3k+1)(2k+1) - \dfrac32 \times k(2k+1) - \dfrac{k}2 = (2k+1)(3k/2+1) - \dfrac{k}2\\ & = 3k^2 + 3k+ 1 = 3k(k+1) + 1 = \dfrac{n-2}2 \cdot \dfrac{n+4}6 + 1 = \dfrac{n^2 + 2n + 4}{12} \end{align} Hence, $$S(n) = 1 + \dfrac{n-2}3 + \dfrac{n^2 + 2n + 4}{12} = \dfrac{n^2 + 6n + 8}{12}$$

Argue similarly, for $n = 3,4,5 \pmod 6$.

-
Doesn't it suffice to show that the constant remaining will always disappear on rounding off for all modulo 6 ? –  user1907531 Mar 20 '13 at 7:55

One approach to this sort of problem is generating functions. If $f(n)$ is the answer for $n$, then we have the formula:

$$\sum_{n=0}^\infty f(n)x^n =\frac{1}{1-x}\frac{1}{1-x^2}\frac{1}{1-x^3} = \frac{1}{(1-x)^3(1+x)(1+x+x^2)}$$

This in turns lets us see that there must be $a,b,c,d,e,f$ such that:

$$f(n)=an^2 + bn + c + d(-1)^n + ew^n + f\bar w^n$$

Where $w=\frac{-1+\sqrt{-3}}{2}$ is a primitive cube root of unity. We can then compute the first $6$ values, $f(0),f(1),\dots, f(5)$ to solve for $a,b,c,d,e,f$. I suspect it will then becomes clear that $|d(-1)^n + ew^n + f\bar w^n|$ is always negative and less than $\frac{1}{2}$, so that you get $f(n)=\lfloor an^2+bn+c +\frac{1}{2}\rfloor$.

This is the math nerd brute force technique. There might be a more inductive approach.

Wolfram alpha helps us compute the partial fractions:

$$\frac{1}{(1-x)(1-x^2)(1-x^3)} = \\\frac{17}{72}\frac{1}{1-x} +\frac{1}{4}\frac{1}{(1-x)^2} + \frac{1}{6}\frac{1}{(1-x)^3}+\frac{1}{8}\frac{1}{1+x} +\frac{1}{9}\frac{2+x}{1+x+x^2}$$

You then see that $$\frac{2+x}{1+x+x^2} = \frac{2-x-x^2}{1-x^3} = \sum w_n x^n$$ has the property that $w_0=2, w_1=-1, w_2=-1, w_{k+3}=w_k$.

This gives us the terms:

$$f(n) = \frac{17}{72} + \frac{1}{4}(n+1) +\frac{1}{12}(n+1)(n+2) + \frac{1}{8}(-1)^n + \frac{1}{9}w_n$$

$\frac{1}{8}(-1)^n + w_n$ is periodic of degree $6$, and we can easily show that $$|\frac{1}{8}(-1)^n + w_n|\leq \frac{25}{72}<\frac{1}{2}$$

So this gives us that $f(n)$ is the nearest integer to:

$$\frac{17}{72} + \frac{1}{4}(n+1)+\frac{1}{12}(n+1)(n+2)=\frac{n^2+6n+9}{12}-\frac{7}{72}$$

This still doesn't get you quite what you want, but it gets you very close.

-
Brilliant solution , when rounded off to the nearest integer will give the result OP wants in every case. –  user1907531 Mar 20 '13 at 7:53