# Counting Different Ways of Summing Numbers

I am looking for information on counting the possible ways of summing numbers. For example, suppose you can use 1,2, and 4. How many possible combinations are there to create any number?

For instance,

For 1: $$1$$

For 2: $$2, 1+1$$

For 3: $$2+1, 1+1+1$$

For 4: $$4, 2+2, 1+1+2$$

For 5: $$4+1, 2+2+1, 2+1+1+1, 1+1+1+1+1$$

This is for a question I am working on a for a first year linear algebra class. We have just been introduced to writing proofs and logical reasoning etc. The numbers we are actually given are 1,2, and 3. However, I am trying to get background information first so I can attempt to solve it myself. I have taken some statistics so I am aware of combinations, but not in this form.

I realize that for every number $n$, there is a combination $\sum_{1}^{n}1$ that equals the number. I made some tables of different combinations for numbers 1-9. I am trying different ways of organizing the different combinations. Any help would be appreciated.

-
FYI: $4$ is missing $1 + 1 + 1 + 1$ –  Benjamin Dickman Nov 5 '12 at 20:58
If we are allowed to use any positive integer, you have discovered the partitions of $n$. The number of partitions is quite complicated. There are good estimate for the number of partitions of $n$ for large $n$, but no pleasant formula. –  André Nicolas Nov 5 '12 at 21:07
Give that this is a first year linear algebra class, I don't suppose you know what generating functions are? –  EuYu Nov 5 '12 at 21:08
Some of it may be a bit out of reach, but this article on partitions is at least a starting point. (And +1 for a very well-formulated question.) –  Brian M. Scott Nov 5 '12 at 21:14
In case you're interested in the sequence itself. A008642 –  EuYu Nov 5 '12 at 21:25

Let $a_n$ be the number of partitions of $n$ with summands only in $\{1,2,4\}$, $b_n$ the number of partitions with summands in $\{1,2\}$. Then we have $$b_n = \left\lfloor\frac n2\right\rfloor+1$$ because we may take between $0$ and $\left\lfloor\frac n2\right\rfloor$ twos and fill with ones. Then we have $$a_n=\sum_{k=0}^{\left\lfloor\frac n4\right\rfloor}b_n.$$ I won't give an explicit formula, but you can guess that $a_n$ is approximately quadratic.

You can also find $a_n$ as the coefficient of $x^n$ in the power series expansion of $$\frac1{(1-x)(1-x^2)(1-x^4)}.$$

-

Just a hint then : take any number, and start from the 'smallest' combination (the one that uses as few numbers as possible). For instance, 5 = 3 + 2.

-

Let the number of ways of creating the sum be T(n). You can often generate a recurrence which works.

Suppose you have notation $T_r(n)$ for the case in which the greatest component of the sum is $r$, then either the sum has a 4 in it, or the largest number is 2, or it is 1 (which is only one case), so:$$T(n)=T(n-4)+T_2(n-2)+1$$ This should enable you to make some sensible progress.

-