# Chaitanya's Random Pages

## July 25, 2015

### Compositions of positive integers where adjacent parts have different parity

Filed under: mathematics — ckrao @ 5:39 am

Here is an interesting problem based on one I found in the 2008 AIME (Q11).

How many compositions of the positive integer n have adjacent parts with different parity?

For example, a valid composition of n=14 is

14 = 1 + 2 + 5 + 2 + 1 + 2 + 1,

since the 1,2,5,2,1,2,1 alternate between being odd and even.

The first terms of the sequence are (OEIS A062200)

1, 1, 3, 2, 6, 6, 11, 16, 22, 37, 49, 80, …

Interestingly the sequence decreases between n=3 and 4 since the only valid compositions of 4 are 4 = 1 + 2 + 1 and 4, while 3 = 1 + 1 + 1 = 2 + 1 = 1 + 2.

Here is the first approach I came up with to solve the problem. Let $a_n$ be the number of such compositions starting with an even number and let $b_n$ be the number of compositions starting with an odd number. We wish to find $t_n := a_n + b_n$. We identify four cases:

• If $n$ is odd and the composition starts with an even number $2c$, we remove that even number and have a composition of $n-2c$ starting with an odd number. Summing over choices of $c$,
$a_{2k+1} = b_{2k-1} + b_{2k-3} + \ldots + b_1. \quad (1)$
• If $n$ is odd and the composition starts with an odd number $2c+1$, we either have the single term composition $n$, or we remove that odd number and have a composition of $n-(2c+1)$ starting with an even number. Summing over choices of $c$,
$b_{2k+1} = 1 + a_{2k} + a_{2k-2} + \ldots + a_2. \quad (2)$
• If $n$ is even  and the composition starts with an even number $2c$, we either have the single term composition $n$, or we remove that even number and have a composition of $n-2c$ starting with an odd number. Summing over choices of $c$,
$a_{2k} = 1 + b_{2k-2} + b_{2k-4} + \ldots + b_2. \quad (3)$
• If $n$ is even and the composition starts with an odd number $2c+1$, we remove that odd number and have a composition of $n-(2c+1)$ starting with an even number. Summing over choices of $c$,
$b_{2k} = a_{2k-1} + a_{2k-3} + \ldots + a_1.\quad (4)$

Recursions (1)-(4) with the initial conditions $a_1 = 0, b_1 = 1, a_2 = 1, b_2 = 0$ allows us to generate the following table.

 $n$ 1 2 3 4 5 6 7 8 9 10 11 12 $a_n$ 0 1 1 1 3 2 6 6 11 16 22 37 $b_n$ 1 0 2 1 3 4 5 10 11 21 27 43 $t_n$ 1 1 3 2 6 6 11 16 22 37 49 80

After writing out some terms I noticed the pattern

$\displaystyle a_n = a_{n-2} + b_{n-2} \text{ and } b_n = a_{n-1} + b_{n-2}.\quad \quad (5)$

I later saw why this is so. Firstly, a composition of $n$ that starts with an even number can be obtained from any composition of $n-2$ by adding 2 to the first term if even or inserting 2 at the start if odd. Hence $a_n = t_{n-2} = a_{n-2} + b_{n-2}$. For the second relation, if the composition of $n$ starts with an odd number, it either is 1 plus an even-starting composition of $n-1$ or it can be obtained from an odd-starting composition of $n-2$ by adding 2 to the first term. Hence $b_n = a_{n-1} + b_{n-2}$.

From (5) and using $t_n = a_n + b_n$ we find that

\begin{aligned} t_n &= a_n + b_n\\ &= t_{n-2} + (a_{n-1} + b_{n-2})\\ &= t_{n-2} + t_{n-3} + t_{n-2} - a{n-2}\\ &= 2t_{n-2} + t_{n-3} - t_{n-4}.\quad \quad (6) \end{aligned}

Together with the initial terms $t_1 = 1, t_2 = 1, t_3 = 3, t_4 = 2$, (6) enables us to generate our desired terms without requiring $a_n$ or $b_n$.

The OEIS page also gives the following expression for $t_n$:

$\displaystyle t_n = \sum_{k=0}^{n+1} \binom{n-k+1}{3k-n+1}.\quad \quad (7)$

Here is how to show this result, with help from the solution at AoPS here. For ease of exposition convert the problem to one of binary strings: we require the number of length-n 0-1 strings so that maximal continguous blocks of 1s have even length and maximal contiguous blocks of 0s have odd length.

Suppose there are $b$ maximal blocks of 0s. All but the last such block must necessarily be followed by a pair of 1s. That is, the string has the form

$\displaystyle [....][....0][11....][....0][11....] \ldots [....0][....],$

where blocks enclosed by [] contain the same digit (0 or 1) and 0 or more pairs of digits are in place of the sets of four dots. We have shown $2b+1$ blocks above but the first and last may be empty.

Let $k = (n-b)/2$, which is the number of pairs of digits to use after $b$ 0s are used (noting that $n-b$ must be even). We have $b$ 0s used above along with $b-1$ pairs of 1s. Therefore $(n-(b + 2(b-1)))/2$ pairs of 0s or 1s need to inserted into the $2b+1$ blocks above. The blocks that they end up determine whether they are 0 or 1.

Now $x$ pairs can be inserted into $y$ blocks in $\binom{x+y-1}{x}$ ways, since we write out $x+y-1$ symbols in a row and choose $x$ of them to be pairs, with the remaining symbols representing separators between blocks. In our case,

$x = \frac{n-(b + 2(b-1))}{2}$, $y = 2b+1$ and $b = n-2k$, so

\begin{aligned} x &= \frac{n-3b+2}{2}\\ &= \frac{n-3n+6k+2}{2}\\ &= 3k-n+1,\end{aligned}

and $x+y-1 = 3k-n+1 + 2(n-2k) + 1 = n-k+1$.

Summing over choices of $k$ gives (7) as desired. Note that some of the terms will be 0 as $k$ ranges from 0 to n+1.

For example, when n=11 and 12, we have

$\displaystyle t_{11} = \binom{8}{2} + \binom{7}{5} = 28 + 21 = 49,$

$\displaystyle t_{12} = \binom{9}{1} + \binom{8}{4} + \binom{7}{7} = 9 + 70 + 1= 80,$

matching the values given in the table above.