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.

 

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: