Different Solutions to British Maths Olympiad (BMO) 1995 Round 1 Question 5, another dwarf combinatorics question

combinatoricscontest-math

The question states:

The seven dwarfs walk to work each morning in single file. As they go, they sing their famous song, “High – low – high -low, it’s off to work we go . . . ” Each day they line up so that no three successive dwarfs are either increasing or decreasing in height. Thus, the line-up must go up-down-up-down- · · · or down-up-down-up- · · ·. If they all have different heights, for how many days they go to work like this if they insist on using a different order each day? What if Snow White always came along too?

My solution focuses on building up from smaller cases. What other elementary solutions exist?

Best Answer

Denote the number of admissible orderings of $n$ dwarfs by $a_n$. Let $n\geq2$. If $\gamma:\>[n]\to[n]$ is an admissible ordering then $$\bar\gamma(k):=n+1-\gamma(k)\qquad(1\leq k\leq n)$$ is an admissible ordering as well. The map $\gamma\mapsto\bar\gamma$ is in fact a fixed point free involution of the set of admissible orderings. Among $\gamma$, $\bar\gamma$ exactly one ends with a downward slope of the zigzag, and exactly one starts with an upward slope of the zigzag.

Assume there are $n+1$ dwarfs. The largest among them (the boss) can range himself at $n+1$ different places in the row. For a given choice there are $0\leq k\leq n$ free places ahead of the boss and $n-k$ free places behind the boss. We can choose the $k$ dwarfs marching in front of the boss in ${n\choose k}$ ways. If $k=0$ or $k=1$ we can arrange these $k$ dwarfs in one way, and if $k\geq2$ we can arrange them in ${1\over2}a_k$ ways such that their zigzag ends with a downward slope. Similarly, if $k=n-1$ or $k=n$ we can arrange the remaining $n-k$ dwarfs to the right of the boss in one way, and if $k\leq n-2$ we can arrange these dwarfs in ${1\over2}a_{n-k}$ ways such that their zigzag begins with an upward slope.

We therefore obtain the following recursion: $$a_0=a_1=1,\quad a_2=2,\quad a_3=4\ ,$$ $$a_{n+1}={1\over2}a_n+{n\over2}a_{n-1}+{1\over4}\sum_{k=2}^{n-2}{n\choose k}a_ka_{n-k}+{n\over2}a_{n-1}+{1\over2}a_n\quad(n\geq3)\ .$$ This recursion produces the following table: $$\bigl(a_n\bigr)_{n\geq0}=\bigl(1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042,\ldots\bigr)\ .$$ This is sequence A001250 at OEIS, where they refer to the greek word $\beta\omicron\upsilon\sigma\tau\rho\omicron\phi\eta\delta\omicron\nu$, meaning going back and forth.