[Math] In how many ways i can write 12

combinatoricsinteger-partitions

In how many ways i can write 12 as an ordered sum of integers where
the smallest of that integers is 2? for example 2+10 ; 10+2 ; 2+5+2+3 ; 5+2+2+3;
2+2+2+2+2+2;2+4+6; and many more

Best Answer

There are $89$ ways (and $89$ is the $11$th Fibonacci number).

You're looking for "restricted compositions" of $12$ (the restriction being that each part is at least $2$).

In Sage (doc):

sage: Compositions(12, min_part = 2).list()
[[12], [10, 2], [9, 3], [8, 4], [8, 2, 2], [7, 5], [7, 3, 2], [7, 2, 3], [6, 6], [6, 4, 2], [6, 3, 3], [6, 2, 4], [6, 2, 2, 2], [5, 7], [5, 5, 2], [5, 4, 3], [5, 3, 4], [5, 3, 2, 2], [5, 2, 5], [5, 2, 3, 2], [5, 2, 2, 3], [4, 8], [4, 6, 2], [4, 5, 3], [4, 4, 4], [4, 4, 2, 2], [4, 3, 5], [4, 3, 3, 2], [4, 3, 2, 3], [4, 2, 6], [4, 2, 4, 2], [4, 2, 3, 3], [4, 2, 2, 4], [4, 2, 2, 2, 2], [3, 9], [3, 7, 2], [3, 6, 3], [3, 5, 4], [3, 5, 2, 2], [3, 4, 5], [3, 4, 3, 2], [3, 4, 2, 3], [3, 3, 6], [3, 3, 4, 2], [3, 3, 3, 3], [3, 3, 2, 4], [3, 3, 2, 2, 2], [3, 2, 7], [3, 2, 5, 2], [3, 2, 4, 3], [3, 2, 3, 4], [3, 2, 3, 2, 2], [3, 2, 2, 5], [3, 2, 2, 3, 2], [3, 2, 2, 2, 3], [2, 10], [2, 8, 2], [2, 7, 3], [2, 6, 4], [2, 6, 2, 2], [2, 5, 5], [2, 5, 3, 2], [2, 5, 2, 3], [2, 4, 6], [2, 4, 4, 2], [2, 4, 3, 3], [2, 4, 2, 4], [2, 4, 2, 2, 2], [2, 3, 7], [2, 3, 5, 2], [2, 3, 4, 3], [2, 3, 3, 4], [2, 3, 3, 2, 2], [2, 3, 2, 5], [2, 3, 2, 3, 2], [2, 3, 2, 2, 3], [2, 2, 8], [2, 2, 6, 2], [2, 2, 5, 3], [2, 2, 4, 4], [2, 2, 4, 2, 2], [2, 2, 3, 5], [2, 2, 3, 3, 2], [2, 2, 3, 2, 3], [2, 2, 2, 6], [2, 2, 2, 4, 2], [2, 2, 2, 3, 3], [2, 2, 2, 2, 4], [2, 2, 2, 2, 2, 2]]
sage: Compositions(12, min_part = 2).cardinality()
89

The number for general $n$ in place of $12$ would be interesting to calculate. Using Sage again:

sage: print ','.join(str(Compositions(n, min_part = 2).cardinality()) for n in range(20))
1,0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584

Searching for that on OEIS gives A212804 as the sequence.

This of course is the Fibonacci sequence with an additional "1" at the beginning.

Now it would be interesting to prove that it is so for general $n$. This is easy now that we know what to prove. Let's call compositions with each part at least $2$ as "good" compositions. Let $C_n$ be the number of "good" compositions of $n$. Any such "good" composition either begins with $2$ or with a number greater than 2:

  • If it starts with $2$, then it can be got by prepending a $2$ to a "good" composition of $n-2$ (and there are $C_{n-2}$ of them)

  • If it starts with a number greater than $2$, then it can be got by taking a "good" composition of $n-1$ (there are $C_{n-1}$ of them) and incrementing the first element by one.

So $C_n = C_{n-2} + C_{n-1}$, which along with the initial conditions $C_0 = 1$ and $C_1 = 0$, proves what we wanted to prove.

Related Question