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.

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?

share|improve this question
2  
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

3 Answers 3

up vote 0 down vote accepted

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.

share|improve this answer

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

share|improve this answer
    
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)

share|improve this answer
    
Doing this, you allow larger numbers than just 1, 2 or 3. –  Tom-Tom Jan 28 at 22:35

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.