# Combination Question

I currently have an open question about counting the possible ways of summing numbers. I am still exploring all the ideas provided - those within my level of understanding. This is a question involving looking into one avenue and possible solution. The question involves finding the possible ways of creating a number $n\in \mathbb{I}$ only by adding 1, 2, or 3. For example, for the number 4:

$$1+1+1+1, 1+1+2, 2+2, 3+1$$

There are four possible combinations. My question involves breaking down the number $n$ using as many 3's as possible. For instance, the number 12 can be written $3+3+3+3.$ Any number greater than or equal to 3 can be broken into

$$3+3+\cdot \cdot \cdot+3$$ or $$3+3+\cdot \cdot \cdot+3+2$$ or $$3+3+\cdot \cdot \cdot+3+1$$

For the first case, it would be a number $n$ that when divided by three yields an integer. Suppose $n=12$, then $n$ can be written as $3+3+3+3$. However, each of these 3's can be written as $3$, $2+1$, or $1+1+1$. That is, there are three possible ways of summing to 3.

How can I calculate the possible combinations? I've thought for the case that $n=12$, there are four 3's that can be either $1+1$, or $1+2$, or $1+1+1$. Can any given number be broken down into a number of 3's, then the possible combinations of $3, 2+1, 1+1+1$ calculated? I would also have to take into account the cases where there would be a remainder of 1 or 2 after dividing by 3.

Does this make any sense?

-
What about $6=2+2+2$? You can’t get that partition by subdividing $6=3+3$. – Brian M. Scott Nov 7 '12 at 0:24
Oops, dont suppose I can delete this question now as I rethink this. – Jerzy_Gregor Nov 7 '12 at 0:28
Don’t delete it; it’s possible that someone will decide to think hard enough about the problem to make a useful suggestion. I may give it some thought myself a bit later. – Brian M. Scott Nov 7 '12 at 0:29
In case you are interested, here is a link to a lecture from 1920 in which the problem discussed is solved. The methods are beyond my current knowledge level unfortunately. Around page 8. ia600500.us.archive.org/15/items/somefamousproble00hardiala/… – Jerzy_Gregor Nov 7 '12 at 0:40
Thanks, Jerzy; I’ll take a look sometime this evening. – Brian M. Scott Nov 7 '12 at 0:43

This is not an answer to the problem itself; rather, it’s some ideas that you might find useful in attacking the problem.

Consider the set $P(n)$ of partitions of $n$ into parts no larger than $3$. They come in three flavors: those with smallest part $1$, those with smallest part $2$, and those with smallest part $3$. For $k=1,2,3$ let $P_k(n)$ be the set of $p\in P(n)$ with smallest part $k$.

• Each $p\in P_1(n)$ is of the form $1+q$, where $q\in P(n-1)$; conversely, each $q\in P(n-1)$ gives rise to a partition $1+q\in P_1(n)$. Thus, $|P_1(n)|=|P(n-1)|=p(n-1,3)$.

• Each $p\in P_2(n)$ is of the form $2+q$, where $q\in P_2(n-2)\cup P_3(n-2)$; conversely, each $q\in P_2(n-2)\cup P_3(n-2)$ gives rise to a partition $2+q\in P_2(n)$. Since $P_2(n-2)$ and $P_3(n-2)$ are disjoint, $|P_2(n)|=|P_2(n-2)|+|P_3(n-2)|$.

• $P_3(n)$ has one member, $\underbrace{3+3+\ldots+3}_{n/3}$, if $n$ is a multiple of $3$; otherwise, $P_3(n)=\varnothing$.

You could try using these ideas as a starting point to develop recurrences that would at least allow you to calculate $|P_k(n)|$ (and hence $p(n,3)$ fairly efficiently for $n$ of reasonable size. Once you’ve done that, the data themselves may reveal further regularities that are worth pursuing.

-

We write $p(n,m)$ for the number of partitions of $n$ into parts less than or equal to $m$. The question asks about $p(n,3)$. There's a very nice discussion of this in Chapter 6 of Andrews and Eriksson, Integer Partitions. The bottom line is, $p(n,3)$ is the nearest integer to $(1/12)(n+3)^2$.

-
Thanks Gerry. I'm aware of this formula, so I will be able to check the solution I come up with. This question is for a first year linear algebra course, and the tools I have aren't sufficient to derive that formula. I am asked specifically to determine $p(n,3)$ for $n=2012,..,2017$. It is suggested we work out some values of $p(n,3)$, starting at 1, and see what happens, and then "maybe even get a recursive way of computing" $p(n,3)$. Though in the question they do not use the partition notation - partitions are not mentioned. – Jerzy_Gregor Nov 7 '12 at 1:18
If you look at the reference I gave, I think you will find that you do have the tools to derive the formula --- you just have to know about infinite series and partial fractions. Anyway, if you have been given a suggestion, why not follow it? Have you worked out $p(n,3)$ for small values of $n$? – Gerry Myerson Nov 7 '12 at 6:05

Suppose you wanna calculate the answer for a number n. You can place n '1s' with (n-1) gaps in between them, now you just have to fill these gaps with a '+' sign to combine the one into larger number. For e.g. 3 = 1_1_1 For 3 there are (3-1) gaps, I have two options for each gap either I put a plus in there to combine the '1s' to form a bugger number or I can leave the gap empty and add all the numbers formed after combining the '1s' linked with '+'. So that'd make you answer to be 2^(n-1)

-
Doing this, you allow larger numbers than just 1, 2 or 3. – Tom-Tom Jan 28 '14 at 22:35