Roller Coaster permutations

Importance: High ✭✭✭
Subject: Combinatorics
Recomm. for undergrads: no
Posted by: Tanbir Ahmed
on: October 14th, 2013

Let $S_n$ denote the set of all permutations of $[n]=\set{1,2,\ldots,n}$. Let $i(\pi)$ and $d(\pi)$ denote respectively the number of increasing and the number of decreasing sequences of contiguous numbers in $\pi$. Let $X(\pi)$ denote the set of subsequences of $\pi$ with length at least three. Let $t(\pi)$ denote $\sum_{\tau\in X(\pi)}(i(\tau)+d(\tau))$.

A permutation $\pi\in S_n$ is called a \emph{Roller Coaster permutation} if $t(\pi)=\max_{\tau\in S_n}t(\tau)$. Let $RC(n)$ be the set of all Roller Coaster permutations in $S_n$.

\begin{conjecture} For $n\geq 3$, \begin{itemize} \item If $n=2k$, then $|RC(n)|=4$. \item If $n=2k+1$, then $|RC(n)|=2^j$ with $j\leq k+1$. \end{itemize} \end{conjecture}

\begin{conjecture}[Odd Sum conjecture] Given $\pi\in RC(n)$, \begin{itemize} \item If $n=2k+1$, then $\pi_j+\pi_{n-j+1}$ is odd for $1\leq j\leq k$. \item If $n=2k$, then $\pi_j + \pi_{n-j+1} = 2k+1$ for all $1\leq j\leq k$. \end{itemize} \end{conjecture}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{}


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

*[AS] Tanbir Ahmed, Hunter Snevily, Some properties of Roller Coaster permutations. To appear in \emph{Bull. Institute of Combinatorics and its Applications}, 2013.

* indicates original appearance(s) of problem.