One Basket or Group Photo

Dorothy of Madras College, St Andrews and Maren & Corinna of Camden School for Girls used the same notation denoting the people by the numbers 1, 2, 3,...? in ascending order of height. As each person at the back must be taller than the person directly in front of them and, along the rows, the heights must increase from left to right the 1 must be in front on the left and the tallest must be at the back on the right. Dorothy gave the results for 2, 4, 6, and 8 people in the following table.

Number of people	Number of arrangements	Diagrams
2	1	2 1
4	2	2 4 1 3 3 4 1 2
6	5	2 4 6 1 3 5 3 4 6 1 2 5 2 5 6 1 3 4 3 5 6 1 2 4 4 5 6 1 2 3
8	14	2 4 6 8 1 3 5 7 3 4 6 8 1 2 5 7 2 5 6 8 1 3 4 7 3 5 6 8 1 2 4 7 4 5 6 8 1 2 3 7 2 4 7 8 1 3 5 6 3 4 7 8 1 2 5 6 2 5 7 8 1 3 4 6 3 5 7 8 1 2 4 6 4 5 7 8 1 2 3 6 2 6 7 8 1 3 4 5 3 6 7 8 1 2 4 5 4 6 7 8 1 2 3 5 5 6 7 8 1 2 3 4

Many people think that because the sequence 1, 2, 5, 14 ? goes up in powers of 3 (with differences 1, 3 and 9) the next difference will be 3 cubed to give the next number 14 + 27 = 41. Maths is full of patterns but, when you think you spot a pattern you have to prove it always works. If you count the arrangements for 10 people the answer is 42 and not 41. Can you find them all?

The solution for 10 people was sent in by Andrei from Tudor Vianu National College, Bucharest, Romania.

For 10 people I shall describe the arrangements briefly without writing all the numbers. I see that 1 and 10 are fixed.

- I start with 1 2 3 4 in the first line, and there are 5 possibilities for the last position: 5, 6, 7, 8 and 9.

- If 4 goes on the second line, than in the first there will be 1 2 3 5, and there are 4 possibilities for the last place: 6, 7, 8 and 9.

- If 5 goes besides 4 on the second line, than in the first there will be 1 2 3 6 and there are 3 possibilities for the last place: 7, 8 and 9.

- If 6 goes also on the second, there will be 1 2 3 7 8 or 1 2 3 7 9 in the first. So, for the sequence 1 2 3 in the first line, there are (5 + 4 + 3 + 2) possibilities.

I change 3 on the second line.

- If on the first line there is the sequence 1 2 4 5, there are 4 possibilities for the last place: 6, 7, 8 and 9.

- If 4 goes on the second line, than on the first there will be 1 2 5 6 followed by 7, 8 or 9 '?? 3 possibilities

- If 5 goes too on the second line, than 1 2 6 7 will be followed by 8 or 9 '?? 2 possibilities.

So, for the group 3 x x x 10 1 2 x x x , there are (4 + 3 + 2) possibilities. Studying all the possibilities further, I arrived at the conclusion that for 10 people, I find the following number of possibilities:

(5 + 4 + 3 + 2) + (4 + 3 + 2) + (3 + 2) +(4 + 3 + 2) + (3 + 2) = 14 +9 +5 + 9 + 5 = 42

Summarising, up to now I found the following table:

No. of people	2	4	6	8	10
No of possibilities	1	2	5	14	42

For 12 people, I see that there are 132 possibilities, which could be counted as:

(6 + 5 + 4 + 3 + 2) + (5 + 4 + 3 + 2) + (4 + 3 + 2) + ( 3 + 2)

+ (5 + 4 + 3 + 2) + (4 + 3 + 2) + ( 3 + 2)

+ (4 + 3 + 2) + ( 3 + 2)

+ (5 + 4 + 3 + 2) + (4 + 3 + 2) + ( 3 + 2)

+ (4 + 3 + 2) + ( 3 + 2) = 48 + 28 +14 + 28 + 14 = 132

At this point, I had the chance to look back on the NRICH site, and to discover the link to the problem Counting Binary Ops. I recognized the numbers I found (1, 2, 5, 14, 42, 132) as being the first terms of the sequence of Catalan numbers. Looking more for Catalan numbers, e.g. at http://mathworld.wolfram.com/CatalanNumber.html I found both the recurrence relation and the explicit formula.

If $C_n$ is the $n$-th Catalan number ($n$ being for our problem the number of places in one line, i.e. half the number of people), $$C_n ={1\over n+1}{2n\choose n}$$ and $${C_{n+1}\over C_n} = {2(2n+1)\over n+2}$$ or, if $C_0 = 1$ (there is exactly one way of arranging zero people: don't put them in any way), then: $$\begin{eqnarray} C_1&=&C_0C_0= 1 \\ C_2&=&C_1C_0 + C_0C_1 = 2 \\ C_3&=&C_2C_0 + C_1C_1 + C_0C_2 = 5 \\ C_4&=&C_3C_0 + C_2C_1 + C_1C_2 + C_0C_3 = 14 \\ C_5&=&C_4C_0 + C_3C_1 + C_2C_2 + C_1C_3 + C_0C_4 = 42 ... \\ C_n &=& C_{n-1}C_0 + C_{n-2}C_1 + ...C_1C_{n-2}+ C_0C_{n-1} \end{eqnarray}$$