Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
1  
related math.stackexchange.com/questions/334901/… –  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
1  
@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
1  
Do you know about generating functions? –  Thomas Andrews Mar 19 '13 at 18:05
1  
@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

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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