2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ It's a little difficult to avoid your solution if we don't know what it is. :-) $\endgroup$ – Theo Bendit Sep 27 '18 at 4:28
  • 1
    $\begingroup$ @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. $\endgroup$ – saulspatz Sep 27 '18 at 4:37
  • $\begingroup$ You can just list the $5040$ permutations and sort out the unacceptable ones. $\endgroup$ – Ross Millikan Sep 27 '18 at 5:05
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.