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.

How do I find the number of ways to represent a number as a sum of only $1$’s and $2$’s and $3$’s?

I think the title is self-explanatory.

E.g., if I have to represent $13$ as a sum of only $1$'s and $2$'s, or $1$'s, $2$'s and $3$'s, what will the formula for finding the number of unordered ways this can be done, i.e., $2 + 2 + 1 = 2 + 1 + 2$?

I'm sorry if this is an easy question, but it's been a long time since I used any permutations and combinations, and it's all hazy.

P.S. Can you tell me a good online resource to brush up advanced permutations and combinations?

share|improve this question
    
It's partitions or compositions that you want, not permutations. –  J. M. Dec 5 '11 at 9:17
    
@J.M. Hmm.. can you give me a hint of what do I ask, or read? –  Skkard Dec 5 '11 at 9:20
3  
See for instance this question (and all the other questions with the tag partitions). In your case, you're interested in the coefficient of $x^{13}$ in the series expansion of $\dfrac1{(1-x)(1-x^2)(1-x^3)}$. –  J. M. Dec 5 '11 at 9:21
add comment

2 Answers

up vote 1 down vote accepted

This is done very nicely on pages 57 to 58 of Andrews and Eriksson, Integer Partitions, published by Cambridge University Press in 2004. As J. M. says in the comments, one wants the series expansion of $${1\over(1-x)(1-x^2)(1-x^3)}$$ The 1st-year Calculus partial fractions approach will get you there, but Andrews and Eriksson give a slightly different partial fractions decomposition, namely, $${1/6\over(1-x)^3}+{1/4\over(1-x)^2}+{1/4\over1-x^2}+{1/3\over1-x^3}$$ and from that they get a very simple formula for the number of partitions of $n$ into parts not exceeding 3.

share|improve this answer
    
Thanks a lot! I'll look it up. –  Skkard Dec 7 '11 at 6:26
add comment

Let $S(x)$ be the number of ways to represent $x$ as a sum of only 1s, 2s, and 3s. We can calculate a couple of values by hand: $S(1) = 1$, $S(2) = 2$, and $S(3) = 4$. Now, what's $S(4)$? Well, we can divide 4 into pieces three ways: we can divide 3 into pieces and stick a 1 on; we can divide 2 into pieces and stick a 2 on; or we can divide 1 into pieces and stick a 3 on, meaning that $S(4) = S(1) + S(2) + S(3) = 6$. Likewise, there are three ways to divide 42 into pieces, depending on whether we stick a 1, a 2, or a 3 on the end, meaning that $S(42) = S(39) + S(40) + S(41)$. In general, we have $S(n) = S(n-3) + S(n-2) + S(n-1)$, which is a linear recurrence relation. Solving a linear recurrence relation is a neat little process that others have described better than I could. This handout has nice description of it; there's also a Google search.

In short, the answer is going to be $S(x) = A \alpha^x + B \beta^x + C \gamma^x$, where $\alpha$, $\beta$ and $\gamma$ are the roots of $x^3 - x^2 - x - 1$, and $A$, $B$, and $C$ are constants.

share|improve this answer
    
I get $S(3)=3$; $3, 2+1, 1+1+1$. Also, $S(4)=4$; $3+1,2+2,2+1+1,1+1+1+1$. It seems we do not agree on the interpretation of the problem. –  Gerry Myerson Dec 7 '11 at 6:01
    
The question asks for the number of unordered ways. That aside, you first say that $S(4) = 3$; you then go on to say that $S(4) = S(1)+S(2)+S(3) = 6$, but $S(1)+S(2)+S(3) = 1+2+4 = 7$. Confusing! –  Théophile Apr 4 '12 at 20:21
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.