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.

I have a general question about numbers:

How many ways can we write $n$ as the sum of the numbers $1$,$2$ and $3$?

I know that we start with the following functions: $$\frac{1}{1-z} = 1+z+z^2+ \dots$$ $$\frac{1}{1-z^2} = 1+z^2+ z^4+ z^6 + \dots$$ $$\frac{1}{1-z^3} = 1+ z^3+ z^{6}+ z^{9} + \dots$$

Multiplying these together we get $$\sum C(n) z^n = \frac{1}{(1-z)(1-z^2)(1-z^3)}$$ where $C(n)$ is our answer. In other words, by multiplying out the polynomials and looking at the coefficients, I can verify that I get the answer. But how do I know that this gives me the answer? How would I get an explicit formula for $C(n)$? I think I have to do something with partial fractions. So $$\frac{1}{(1-z)(1-z^2)(1-z^3)} = \frac{A}{1-z} + \frac{B}{1-z^2}+ \frac{C}{1-z^3}$$ and we have to solve for $A$, $B$ and $C$?

share|improve this question
add comment

6 Answers

Read any book on generating functions to understand why $1/(1-z)(1-z^2)(1-z^3)$ is the correct generating function.

The partial fraction decomposition is more complicated than what you describe. First we need to find all the roots in the denominator and their multiplicities. These are $1$ (multiplicity $3$), $-1$ and $\frac{1}{2} \pm \frac{\sqrt{3}}{2} i$ (each appearing with multiplicity $1$). Therefore the partial fraction decomposition is of the form $$ \frac{A}{1-z} + \frac{B}{(1-z)^2} + \frac{C}{(1-z)^3} + \frac{D}{1+z} + \frac{E}{1 + z + z^2}. $$ The last term incorporates both roots $\frac{1}{2} \pm \frac{\sqrt{3}}{2} i$. Once you find $A,B,C,D,E$, you need to find the formulas for all these generating functions, and then you'll get a formula for $C(n)$.

share|improve this answer
    
What happens if we are given the numbers $a_1, \dots, a_k$? –  Damien Jul 15 '11 at 16:31
    
You do the same thing but it gets messier. If all you want is asymptotics, there might be a way out. –  Yuval Filmus Jul 15 '11 at 22:55
add comment

You can write down a relativity explicit formula for $C(n)$. First of all, write

$$ \frac{1}{1-z}=1+z+z^2+\cdots =\sum _{n=0}^\infty a_nz^n $$ $$ \frac{1}{1-z^2}=1+z^2+z^4+\cdots =\sum _{n=0}^\infty b_nz^n $$ $$ \frac{1}{1-z^3}=1+z^3+z^4+\cdots =\sum _{n=0}^\infty c_nz^n. $$

Then, we see that $$ C(n)=\sum _{i+j+k=n}a_ib_jc_kz $$

Thus, you are summing over all positives ways of adding $i$, $j$, and $k$, to get $n$. However, $b_j$ is nonzero iff $j$ is a multiple of $2$, in which case $b_j=1$, and similiary $c_k$ is nonzero iff $k$ is a multiple of $3$, in which case $c_k=1$. It follows that the term $a_ib_jc_k$ is nonzero, in which case it evaluates to just $1$, iff $j$ is a multiple of $2$ and $k$ is a multiple of $3$, so that $n=i+j+k$ is a sum of $i$ ones, $j$ twos, and $k$ threes. You can check that, given such a decomposition of $n$ into $i$ ones, $j$ twos, and $k$ threes, there exists a corresponding term in the above sum that evaulates to $1$, and conversely, every such term corresponds to exactly one such decomposition. Thus, you are indeed summing a $1$ for each possibly way of writing $n$ as a sum of ones, twos, and threes, and hence $C(n)$ is the desired result.

Hope that helps. I think it might be a little confusing the first time you read it. Let me know if you have any questions about what I meant.

share|improve this answer
1  
I wouldn't consider this "a relatively explicit formula for $C(n)$"; it's pretty much a restatement of the question IMHO. –  ShreevatsaR Jul 24 '11 at 12:23
    
The OP said "But how do I know that this gives me the correct answer>" That is the only part of his question that you meant to address, as you are correct, I would not consider what I said to be a relatively explicity formula for $C(n)$. –  Jonathan Gleason Jul 24 '11 at 15:54
add comment

Since I have it worked out, and it hasn't been posted, here is the explicit decomposition of the partial fractions. We have

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

Personally, I don't know the generating series for $\frac{1}{z^{2}+z+1}$, but I do know it for $\frac{1}{\omega-z}$ and $\frac{1}{\overline{\omega}-z}$, so lets go one step further. We can derive

$$\frac{z+2}{9\left(z^{2}+z+1\right)}=\frac{1}{9}\left(\frac{\omega}{\omega-z}+\frac{\overline{\omega}}{\overline{\omega}-z}\right).$$

Since we know the expansion

$$\frac{1}{\left(a-z\right)^{k+1}}=\frac{1}{a^{k+1}\left(1-\frac{z}{a}\right)^{k+1}}=\frac{1}{a^{k+1}}\sum_{n=0}^{\infty}\tbinom{n+k}{k}\frac{z^{n}}{a^{n}},$$

we can sum all of these to get the explicit formula for $C_{n}$.

Hope that helps,

share|improve this answer
add comment

For the first part of the question: As Yuval points out, this is a typical use of generating functions, you are supposed to read about them to understand why $C(n)$ can be expressed in that way.

A (slightly marginal) way of seeing it, in case you are familiar with discrete sequences (signals), convolutions and Fourier transforms:

Say $C_1(n)$ gives us, for each $n$ the number of ways of expressing the number $n$ as a sum of ones; and $C_2(n)$ the same, as a sum of twos.

Say we want to compute $C_{12}(n)$, number of ways of expressing the number $n$ as a sum of 1's and 2's. We can partition $n = n_1 + n_2$, with $n_1$ being the sum of 1's, etc; for that particular partition, the total number of ways would be $C_1(n_1) C_2(n_2)$. But we must count all possible partitions, so that

$$C_{12}(n) = \sum_{n_1+n_2=n} C_1(n_1) C_2(n_2) = \sum_{n_1=0}^n C_1(n_1) C_2(n-n_1) $$

You might recognize this a convolution of sequences, and recall that a convolution translates as product in the Fourier transform domain (or the Laplace transform, or the Z transform - basically the same as the generating function). But $C_1(n)$ and $C_2(n)$ are easy to find out, as well as its generating functions, so it's also easy to find out the generating function of $C_{12}$, as their product. And there you go.

share|improve this answer
add comment

Denote by $N_3=\{1,2,3\}\,$ then your question can be reformulated:

Find the number of partitions of natural number n in parts over set $N_3$ that number we denote

$p(n,N_3)$, $n=6k+l$, where $ k\in \{0,1,2,...\}$,and $ l\in \{0,1,2,3,4,5\}\,$

Using recurrences (no generating functions) I find that exact solution is.

[1] $p(6k,N_3)=3k^2+3k+1$

[2] $p(6k+1,N_3)=3k^2+4k+1$

[3] $p(6k+2,N_3)=3k^2+5k+2$

[4] $p(6k+3,N_3)=3k^2+6k+3$

[5] $p(6k+4,N_3)=3k^2+7k+4$

[6] $p(6k+5,N_3)=3k^2+8k+5$

To explain each formula is needed a lot of introduction

example: $p(10,N_3)=14$ because

[1,1,1,1,1,1,1,1,1,1]

[1,1,1,1,1,1,1,1,2]

[1,1,1,1,1,1,1,3]

[1,1,1,1,1,1,2,2]

[1,1,1,1,1,2,3]

[1,1,1,1,2,2,2]

[1,1,2,2,2,2]

[1,1,1,1,3,3]

[1,1,1,2,2,3]

[1,1,2,2,2,2]

[1,2,2,2,3]

[2,2,2,2,2]

[1,3,3,3]

[2,2,3,3]

From our formulas we have

$p(10,N_3)=p(6\times 1+4)=3\times 1^2+7\times 1+4=14$ there $k=1$

share|improve this answer
add comment

Here is a derivation of a really explicit formula for $C(n)$, which I've below called $p_{123}(n)$.

Let $p_{23}(n)$ denote the number of partitions of $n$ into $2$s and $3$s. If you use $k$ $2$s, then you must make up $n-2k$ using $3$s, so we must have $n - 2k \equiv 0 \pmod 3$, and also $2k\le n$. So,

  • If $n \equiv 0 \pmod 3$, then $k \equiv 0 \pmod 3$, so every $k = 3l$ from $l=0$ to $l=\lfloor n/6 \rfloor$ works.
    If $n = 6m$ or $n=6m + 3$ then $p_{23}(n) = m+1$.

  • If $n \equiv 1 \pmod 3$, then $k \equiv 2 \pmod 3$, so every $k = 3l+2$ from $l=0$ to $l=\lfloor (n-4)/6 \rfloor$ works.
    If $n = 6m+1$ then $p_{23}(n) = m$ and if $n=6m+4$ then $p_{23}(n) = m+1$.

  • If $n \equiv 2 \pmod 3$, then $k \equiv 1 \mod 3$, so every $k = 3l+1$ from $l=0$ to $\lfloor (n-2)/6 \rfloor$ works.
    If $n = 6m+2$ or $n=6m+5$ then $p_{23}(n) = m+1$.

So now we have a closed-form expression for $p_{23}(n)$.

Let $p_{123}(n)$ denote the number of ways of writing $n$ as a sum of $1$s, $2$s and $3$s. Then, by summing over the number of $1$s we use, $$ p_{123}(n) = \sum_{i=0}^{n} p_{23}(n-i) = \sum_{i=0}^{n} p_{23}(i).$$

Now the sum over $p_{23}(i)$ is easy to calculate for each consecutive bunch of 6 numbers: $$p_{23}(6r) + p_{23}(6r+1) + p_{23}(6r+2) + p_{23}(6r+3) + p_{23}(6r+4) + p_{23}(6r+5)$$ $$ = (r+1) + r + (r+1) + (r+1) + (r+1) + (r+1)$$ $$ = 6r + 5 $$

So if $\lfloor n/6 \rfloor = m$, then

$$\begin{align} p_{123}(n) &= \sum_{i=0}^{n} p_{23}(i) \\ &= \sum_{i=0}^{6m-1} p_{23}(i) + \sum_{i=6m}^{n} p_{23}(i)\\ &= \sum_{r=0}^{m-1} (6r+5) + \sum_{i=6m}^{n} p_{23}(i) \\ &= 6\frac{(m-1)m}{2} + 5m + \sum_{i=6m}^{n} p_{23}(i) \\ &= 3m^2 + 2m + \sum_{i=6m}^{n} p_{23}(i) \end{align}$$

Specifically,

  • If $n = 6m$ then $p_{123}(n) = (3m^2 + 2m) + (m+1) = 3m^2 + 3m + 1$

  • If $n = 6m+1$ then $p_{123}(n) = (3m^2 + 3m + 1) + m = 3m^2 + 4m + 1$

  • If $n = 6m+2$ then $p_{123}(n) = (3m^2 + 4m + 1) + (m+1) = 3m^2 + 5m + 2$

  • If $n = 6m+3$ then $p_{123}(n) = (3m^2 + 5m + 2) + (m+1) = 3m^2 + 6m + 3$

  • If $n = 6m+4$ then $p_{123}(n) = (3m^2 + 6m + 3) + (m+1) = 3m^2 + 7m + 4$

  • If $n = 6m+5$ then $p_{123}(n) = (3m^2 + 7m + 4) + (m+1) = 3m^2 + 8m + 5.$

This can be written as $\frac{n^2}{12} + \frac{n}{2} + c$ where $c$ is $1$, $\frac5{12}$, $\frac23$, $\frac34$, $\frac23$, or $\frac5{12}$ depending on whether $n$ modulo $6$ is $0$, $1$, $2$, $3$, $4$ or $5$ respectively.


Although all this looks very ad hoc, I believe it can be generalised to any general set $\{a_1, a_2, \dots, a_k\}$. You'll still have to take cases and evaluate sums about $k$ times, and you'll get a polynomial of degree $k-1$, and (I guess) at most $\mathrm{lcm}(a_1, \dots, a_k)$ cases. I don't think this is necessarily messier to do by hand than actually carrying out the generating functions -> partial fractions -> … approach to completion.

share|improve this answer
add comment

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.