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

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?

Answer 1

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.

Answer 2

My two solutions are recursive also, but the first is simple and the second is cool.

In the $n$-dwarf case, number the dwarfs $0,1,\dots,n$, and write a list $a$, in which the $k$th element is the number of permutations $p$ of dwarfs satisfying $p_0<p_1>p_2<\dots$ such that $p_n=k$, then $d(n)$ (the dwarf number) is $a$'s sum.

Denote this as a function of $n$ and $k$, then since each permutation of $n-1$ elements can have $1$ added to all elements with values $\ge k$, then all those with the last element $\lt k$ are satisfied for odd $n$ and all $\ge k$ for even $n$, so it is generated by running sums in alternate directions. We have the recurrence relation$$a(n,k)=\begin{cases}1&n=k=0\\\begin{cases}a(n,k-1)+a(n-1,k)&n\equiv1\ (\text{mod}\ 2)\\a(n,k+1)+a(n-1,k-1)&\text{else}\end{cases}&0\le k\le n\\0&\text{else}\end{cases}$$providing the triangle$$\begin{matrix} &&&&&1&&&&&\\&&&&1&&1&&&&\\&&&2&&2&&1&&&\\&&2&&4&&5&&5&&\\&16&&16&&14&&10&&5&\\16&&32&&46&&56&&61&&61\\ \end{matrix}$$(sequence A008282 in the OEIS)

The sum of a row (the largest value in the next row) is a term of A000111, and must be doubled to account for the problem only requiring it to be alternating, and not caring for whether it begins increasing or decreasing.

The cooler version (which is not so feasible for a student to implement in test conditions, but is interesting nonetheless) is based on the idea that the set of which you're enumerating permutations need only be comprised of entirely distinct elements, and that independent uniform random variables in the range $[0,1)$ are distinct with probability $1$, and $n$ of them, when converted to their indexes, will become each permutation with equal probability.

One may define the sequence of functions $p_i(x_i)$ to be the probability that $x_i$ satisfies the rule $x_0<x_1>x_2<\dots x_i$, then we have $p_0(x)=1$ and $p_n(x)=\begin{cases}\int_0^x\left(p_{n-1}(x)\ dx\right)&n\equiv1\ (\text{mod}\ 2)\\\int_x^1\left(p_{n-1}(x)\ dx\right)&\text{else}\end{cases}$, and $d(n)=n!*\int_0^1\left(p_n(x)\right)*2$.

Equivalently, to compute $d_n$ begin with the $0$-indexed tuple (polynomial expansion) $(1,)$. For each $k$ from $0$ to $n$,

• if $k\equiv n\ (\text{mod}\ 2)$, integrate (shift all terms a place rightward and divide by their new index),

• otherwise, also integrate, but afterwards take the sum (evaluate it at $x=0$), use this as the $0$th element ($x^0$ coefficient), and multiply all other elements by $-1$.

Once this is done for all $k$, take the sum once more. This provides you with the probability that a set of $n$ random variables abides by it, so must be multiplied by $n!$ to count the permutations, and by $2$ to account for the inverted-inequality cases for $d(n)$.