Roller Coaster permutations

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $S_n$ be the permutations of $[n]=\{1,\ldots,n\}$, written as sequences. An increasing (respectively decreasing) run is a maximal contiguous increasing (respectively decreasing) subsequence of length at least two; consecutive runs may share their turning-point entry. Write $i(\tau)$ and $d(\tau)$ for their numbers. If $\tau$ has length $m\geq2$, then \[i(\tau)+d(\tau)=1+\sum_{j=2}^{m-1}\mathbf1\left\{(\tau_j-\tau_{j-1})(\tau_{j+1}-\tau_j)<0\right\}.\] Let $X(\pi)$ consist of all subsequences selected by strictly increasing index sets of size at least three, and set \[t(\pi)=\sum_{\tau\in X(\pi)}(i(\tau)+d(\tau)),\qquad\operatorname{RC}(n)=\{\pi\in S_n:t(\pi)=\max_{\sigma\in S_n}t(\sigma)\}.\] The run convention is the one illustrated in the cited original research definition. [S3]

Statement recorded in the supplied source.

For every $n\geq3$, are the following two conjectures true? First, if $n=2k$ then $|\operatorname{RC}(n)|=4$, while if $n=2k+1$ then $|\operatorname{RC}(n)|=2^j$ for some integer $0\leq j\leq k+1$. Second, for every $\pi\in\operatorname{RC}(n)$ and every $1\leq a\leq k$, is $\pi_a+\pi_{n-a+1}$ odd when $n=2k+1$, and equal to $2k+1$ when $n=2k$? [S2]

Short English statement

For permutations maximizing the total monotone-run count over all subsequences, determine whether their number is four in even length and a bounded power of two in odd length, and whether opposite-position entries satisfy the stated sum laws.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3052 (OPG-58213). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Ahmed, Tanbir; Snevily, Hunter S., Roller Coaster permutations, Open Problem Garden, node 58213. Complete problem, discussion and bibliography (including mathematical image alt text). https://www.openproblemgarden.org/op/roller_coaster_permutations.
• S3 William L. Adamczak, A Note on the Structure of Roller Coaster Permutations, arXiv:1605.02415 (2016). Definition1.1 and Example1.2, page2; reference[1] identifies Ahmed--Snevily, BulletinICA68(2013),55--60. https://arxiv.org/pdf/1605.02415.