0
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ The 'cool' font is called LaTeX and tutorials are found math.meta.stackexchange.com/questions/5020/…. $\endgroup$ – Landuros Feb 8 at 15:02
  • 2
    $\begingroup$ 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. $\endgroup$ – hardmath Feb 8 at 15:06
  • $\begingroup$ Thanks landuros $\endgroup$ – Godlixe Feb 8 at 15:07
  • $\begingroup$ And thanks hardmath $\endgroup$ – Godlixe Feb 8 at 15:07
  • $\begingroup$ 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$. $\endgroup$ – Donald Splutterwit Feb 8 at 15:23
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ These are the "tribonacci" numbers : oeis.org/A000073 (See in particular the second comment) $\endgroup$ – Jean Marie Feb 11 at 8:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.