Number of permutations of $\{1, 2, 3, \dots, n\}$ such that every number is less than or equal to the average of its $2$ neighbours (if any).

combinatoricscontest-mathpermutations

Question:

Find the number of permutations of $\{1, 2, 3, \dots, n\}$ such that every number is less than or equal to the average of its $2$ neighbours (if any).

My attempt:

I immediately noticed that $n$ must be at the $2$ ends. This encourages us to use recursion since every time $n$ increases, it is just added to either of the $2$ ends.

Let the number of such permutations be $x_n$. Suppose that a possible sequence is $\{a_1, a_2, a_3, \dots, a_n\}$ and we want to insert $n+1$. As I've said above, either $a_1$ is $n$ or $a_n$ is $n$. Here's where I got stuck. Suppose that $a_1$ is $n$. Then, we do not know whether letting $a_0=n+1$ (i.e. inserting $n+1$ in front) works, because we have to ensure that $a_1=n$ is less than or equal to the average of $a_0$ and $a_2$, and we cannot ensure this, so I got stuck.

I have no other methods except to brute-force everything. Any help will be appreciated! Thanks in advance.

Best Answer

A not-so-satisfying approach to rigorously prove that the answer is $8$ for large enough $n$ is to simply catalogue the list of solutions, and prove inductively that these are the only ones. The induction step proceeds using your observations that the number $n$ always appears at the start or the end, so to get a suitable permutation of $1,\ldots,N+1$, you need to append the number $N+1$ to either the start or end of a suitable permutation of $1,\ldots,N$.

For $n = N$, the $8$ solutions admit the following patterns.

  • $T_1$: $\{1, 2 \ldots, N-1, N\}$
  • $T_2$: $\{N-1, 1, 2, \ldots, N-2, N\}$
  • $T_3$: $\{N-1, N-3, \ldots, 1,\ldots,N-2,N\}$
  • $T_4$: $\{N-1, N-2, \ldots, 2, 1, N\}$
  • $T_5$: Reverse of type 4
  • $T_6$: Reverse of type 3
  • $T_7$: Reverse of type 2
  • $T_8$: Reverse of type 1

An example for $N = 10$ is illustrated in my initial comment to your question. Now let $s$ be the act of adding $N+1$ to the start of a sequence, and $e$ the act of adding $N+1$ to the end of a sequence. Then

You can now attach the number $N+1$ in precisely $8$ possible ways:

  • $s(T_1) = T_5$
  • $e(T_1) = T_1$
  • $s(T_3) = T_6$
  • $s(T_4) = T_7$
  • $e(T_5) = T_2$
  • $e(T_6) = T_3$
  • $s(T_8) = T_8$
  • $e(T_8) = T_4$

Still hoping someone else comes up with a cleverer solution.

Related Question