8
$\begingroup$

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.

  • 0
    Thanks for all the input. I am exploring each avenue.2012-11-06

3 Answers 3

2

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

1

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.

1

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.