Is my answer correct? Partitioning numbers

Question

How many ways are there to write the number 7 with the summands: 1, 2, and 3? For example, there are 7 ways to write the number 4:

{1 + 1 + 1 + 1} x 1

{2 + 1 + 1} x 3

{3 + 1} x 2

{2 + 2} x 1

I got the answer 44 by doing so:

{1 + 1 + 1 + 1 + 1 + 1 + 1} x 1

{2 + 1 + 1 + 1 + 1 + 1} x 6

{3 + 1 + 1 + 1 + 1} x 5

{2 + 2 + 1 + 1 + 1} x 12

{2 + 2 + 1 + 1} x 4

{3 + 2 + 2 + 1} x 12

{3 + 3 + 1} x 3

{3 + 2 + 2} x 3

The problem is, Im likely to miss a kind of summand, for example I forgot there is {2 + 2 + 1 + 1 + 1}, any tips on how to list them all? And how to get the cool number fonts people use here? Thanks!

The 'cool' font is called LaTeX and tutorials are found https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference. — Landuros, Feb 08 '19 at 15:02
Note that the word partition (used in title but not body of your Question) means the summands are considered without regard to order, i.e. rearrangement of summands is not counted as a different solution. The word composition is used to describe summations where the order of terms is important. — hardmath, Feb 08 '19 at 15:06
Ordered partitions enumerate to $2^n$. {2 + 2 + 1 + 1 + 1} x 12 should be $\times 10$... see if you can get $64$ with all the partitions of $6$. — Donald Splutterwit, Feb 08 '19 at 15:23

score 2 · Answer 1 · answered Feb 08 '19 at 16:32

In your counting the order of the summands is playing a rôle. Denote the number of representations of $n$ by summands $1$, $2$, $3$ by $a_n$. Any such representation has a last summand from $\{1,2,3\}$. Therefore we have the following recursion: $$a_n=a_{n-1}+a_{n-2}+a_{n-3}\qquad(n\geq3)\ .\tag{1}$$ The initial values are $a_0=a_1=1$, $a_2=2$, and we then obtain $a_3=4$, $a_4=7$. The general solution of $(1)$ is obtained through solution of its characteristic equation $\lambda^3-\lambda^2-\lambda-1=0$.

These are the "tribonacci" numbers : https://oeis.org/A000073 (See in particular the second comment) — Jean Marie, Feb 11 '19 at 08:42

Is my answer correct? Partitioning numbers

1 Answers1