Compositions with no 1

Probability Level 3

A composition of $n$ is an expression of $n$ as a sum of not necessarily distinct positive integers, where the order matters. Note that $n = n$ counts as a composition of $n$ .

Let $C_n$ be the number of compositions of $n$ with no part equal to 1.

For instance, $C_6 = 5$ because $6 = 6 =4+2=3+3=2+4=2+2+2.$

Find $C_{15}$ .

The answer is 377.

1 solution

Arjen Vreugdenhil
Mar 26, 2016

Claim : $C_n = F_{n-1}$ , i.e. the $(n-1)$ th Fibonacci number. In other words, $C_1 = 0;\ C_2 = 1;\ C_{n+2} = C_{n} + C_{n+1}\ \text{for}\ n \geq 1.$

Proof :

First of all, to generate all compositions of $n$ not containing 1, we start with each of the integer $2 \leq k \leq n$ , and append all possible compositions of $n - k$ not containing 1. That results in $C_n = \sum_{k = 2}^n C_{n-k} = \sum_{i=0}^{n-2} C_i$ different compositions.

Now we will prove the Fibonacci property by induction. Clearly, $C_0 = 1$ , $C_1 = 0$ , and $C_2 = 1$ , so that the recursion formula is valid for $n = 0$ . Now let $n \geq 1$ and assume the recursion formula is true for $i < n$ . Then $C_{n} + C_{n+1} = 1 + \sum_{i=0}^{n-2} (C_i + C_{i+1}) = 1 + \sum_{i=0}^{n-2} C_{i+2} = \sum_{i=0}^n C_i = C_{n+2}.$ Here, the term "1" had to be added because $C_{n+1} = C_0 + \sum_{i=0}^{n-2} C_{i+1}$ , and could be removed later because we absorbed it as $C_0 + C_1$ in the last sum.

Final calculation:

I like the "direct" formula, $C_n = F_{n-1} = \frac{(\tfrac12+\tfrac12\sqrt5)^{n-1} - (\tfrac12-\tfrac12\sqrt5)^{n-1}}{\sqrt 5},$ which in this case gives $C_{15} = \boxed{377}.$

Interesting. Your recurrence is not as well-known, but the way that you prove that the $C_n$ satisfy that one is quite natural.

There is a slightly more complicated way to show directly (combinatorially) that $C_n = C_{n-1} + C_{n-2}.$ Hint: Divide them into two groups depending on whether the last term is a 2.

Patrick Corn - 5 years, 2 months ago

B t w your problem was inspiration for this one.

Arjen Vreugdenhil - 5 years, 2 months ago

What you call an "unordered composition" is usually called a partition . I posted a similar problem recently.

Patrick Corn - 5 years, 2 months ago

Ah, yes, I see that solution now.

Let $n = a_1 + \cdots + a_k$ be a composition of $n$ with no 1. There are two possibilities.

$a_k = 2$ . In that case, $n - 2 = a_1 + \cdots + a_{k-1}$ is a composition of $n-2$ with no 1. Clearly this establishes a one-to-one correspondence between compositions of $n$ ending in 2, and compositions of $n-2$ .
$a_k > 2$ . Then $n-1 = a_1 + \cdots + a_{k-1} + (a_k-1)$ is a composition of $n-2$ with no 1. Again, we have a one-to-one correspondence, between compositions of $n$ not ending in 2, and compositions of $n-1$ .

Thus we have established a bijection $\mathbb{C}_n \leftrightarrow \mathbb{C}_{n-1} \cup \mathbb{C}_{n-2}$ , proving that $C_n = C_{n+1} + C_{n+2}$ .

Arjen Vreugdenhil - 5 years, 2 months ago

Compositions with no 1

The answer is 377.

1 solution

0 pending reports