Different Solutions to British Maths Olympiad (BMO) 1995 Round 1 Question 5, another dwarf combinatorics question 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?
 A: 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.
