5
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ related math.stackexchange.com/questions/334901/… $\endgroup$ – kaine Mar 19 '13 at 17:59
  • $\begingroup$ Is $1+2+3=1+3+2$ considered the same sum, or different? I'm guessing the same, but not sure. $\endgroup$ – Thomas Andrews Mar 19 '13 at 18:00
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Mar 19 '13 at 18:01
  • 1
    $\begingroup$ Do you know about generating functions? $\endgroup$ – Thomas Andrews Mar 19 '13 at 18:05
  • 1
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Mar 19 '13 at 18:05
3
$\begingroup$

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

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

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.

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

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.