Number of ways to represent a number as a sum of only $1$’s and $2$’s and $3$’s

Question

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?

Answer 1

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.

Answer 2

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.