Problem:
A flock of 8 birds is flying in formation, led by a single leader bird, which has exactly 2 followers immediately behind. Each non-leader bird follows exactly one bird, and has 0, 1, or 2 followers immediately behind. Two possible formations are shown in the figure below. (When a bird has two followers, swapping its left and right subflocks can produce a different formation, as shown in the figure.)
What is the total number of possible formations?
Answer Choices:
A. 48
B. 52
C. 76
D. 132
E. 196
Solution:
Let T(n) be the number of formations of n birds in which the leader may have 0, 1, or 2 followers (and so may every other bird). Every bird together with all the birds behind it forms a smaller formation of this kind.
Recursion. In a formation of n birds, the leader has
- 0 followers: only possible when n=1;
- 1 follower: the other nβ1 birds form one formation, in T(nβ1) ways;
- 2 followers: the other nβ1 birds split into a left formation of i birds and a right formation of nβ1βi birds, with 1β€iβ€nβ2, in T(i)T(nβ1βi) ways.
So T(1)=1 and
T(n)=T(nβ1)+i=1βnβ2βT(i)T(nβ1βi)(nβ₯2).
Computing.
T(2)T(3)T(4)T(5)T(6)β=T(1)=1=T(2)+T(1)T(1)=1+1=2=T(3)+[T(1)T(2)+T(2)T(1)]=2+2=4=T(4)+[T(1)T(3)+T(2)T(2)+T(3)T(1)]=4+5=9=T(5)+[T(1)T(4)+T(2)T(3)+T(3)T(2)+T(4)T(1)]=9+12=21β
The answer. In our flock the leader has exactly 2 followers, so the other 7 birds split into a left formation of i birds and a right formation of 7βi birds:
i=1β6βT(i)T(7βi)=21+9+8+8+9+21=(C) 76.
Remark. The numbers 1,1,2,4,9,21,51,β¦ are the Motzkin numbers.
The problems and solutions on this page are the property of the MAA's American Mathematics Competitions