Q:

Arrangement in a row puzzle

In how many ways can the integers 0,0,1,2,3,4,5 be arranged in a row so that no integer is adjacent to 2 strictly larger integers ?

A:

Consider first the corresponding problem with just one $0$. Suppose that $a_1a_2\dots a_6$ is an acceptable arrangement. If $a_1>a_2$, then we must have $a_2>a_3$, which in turn implies that $a_3>a_4$, and so on; in fact, the arrangement must be $543210$. 
If $a_1<a_2$, however, matters are a bit different: $a_3$ can be larger or smaller than $a_2$ without hurting the acceptability of the string. However, the analysis in the first paragraph shows that if at some point we have $a_k>a_{k+1}$, the string must decrease from there to the end. Thus, any string with exactly one peak is acceptable. How many single-peaked strings are there? The peak must be the $5$, and it can be in any of the six positions; suppose that $a_k=5$. Once we decide which $k-1$ of the integers $0,1,2,3$, and $4$ are to go to the left of $a_k$, there’s only one possible arrangement: those $k-1$ integers must be arranged in increasing order, and the $6-k$ remaining integers must be arranged in decreasing order to the right of $a_k$. For $k=1,\dots,6$ there are $\binom5{k-1}$ ways to choose the integers to the left of the $5$, so there are altogether
$$\sum_{k=1}^6\binom5{k-1}=\sum_{k=0}^5\binom5k=2^5=32$$
acceptable arrangements.

An easier way to arrive at the same result is simply to notice that once you’ve placed the $5$, you can run through the other five numbers and for each one decide whether to place it to the left or to the right of the peak at $5$: as already noted, once those decisions are made, exactly one arrangement is possible. That’s a two-way choice made $5$ times, so there are $2^5=32$ possible outcomes.

Now let’s add the second $0$ to the set. First we’ll count the acceptable strings in which the two zeroes are adjacent. In that case they behave just like the single $0$ in the simpler problem, and and we get $32$ arrangements. Now suppose that the zeroes are not adjacent. Whatever is between them is bigger than $0$, and there is nothing smaller than $0$, so if one of them were not at one end of the string, it would be adjacent to two strictly larger numbers. Thus, the zeroes must be at the ends of the string: we have $0a_1a_2a_3a_4a_50$, where $a_1a_2a_3a_4a_5$ is some permutation of $1,2,3,4$, and $5$. Clearly that permutation has to be single-peaked, and every single-peaked permutation is acceptable. Now just use the ideas of the second or third paragraph to compute the number of single-peaked permutations of $1,2,3,4$, and $5$.

