# 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?

• It's a little difficult to avoid your solution if we don't know what it is. :-) – Theo Bendit Sep 27 '18 at 4:28
• @TheoBendit I think the OP is asking whether there's a solution method that doesn't depend on building up the solution from smaller cases. – saulspatz Sep 27 '18 at 4:37
• You can just list the $5040$ permutations and sort out the unacceptable ones. – Ross Millikan Sep 27 '18 at 5:05

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.