0
$\begingroup$

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?

  • 0
    And now I’ve done so. Elementary generating functions aren’t hard $-$ I could probably sit down with you and teach you the basics in a few hours $-$ but you do need some background to follow that argument.2012-11-07

3 Answers 3

1

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.

0

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

  • 0
    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$?2012-11-07
0

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)

  • 0
    Doing this, you allow larger numbers than just 1, 2 or 3.2014-01-28