%\documentclass{article} %\usepackage[utf8]{inputenc} %\begin{document} %(Type your content here.) %\end{document} % EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amsmath,amssymb} \newcommand{\des}{{des}} %\newcommand{\Des}{{Des}} %\newcommand{\ides}{{ides}} %\newcommand{\wc}{{wc}} %\newcommand{\simp}{{simp}} %\newcommand{\Simp}{{Simp}} %\newcommand{\Av}{{Av}} \DeclareMathOperator{\Des}{Des} \DeclareMathOperator{\ides}{ides} \DeclareMathOperator{\wc}{wc} \DeclareMathOperator{\simp}{simp} \DeclareMathOperator{\Simp}{Simp} \DeclareMathOperator{\Av}{Av} % Please remove all commands that change parameters such as % margins or page sizes. % Packages amssymb and amsthm are already loaded. % We recommend these AMS packages: % We recommend the graphicx package for importing figures: \usepackage{graphicx} % Use this command to create hyperlinks (optional and recommended): \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % Theorem-like environments that are declared in the style file are: % theorem, lemma, corollary, proposition, fact, observation, claim, % definition, example, conjecture, open, problem, question, remark, note %%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Give the submission and acceptance dates in the format shown. % The editors will insert the publication date in the third argument. \dateline{Jan 1, 2018}{Jan 2, 2018}{TBD} % Give one or more subject codes separated by commas. % Codes are available from http://www.ams.org/mathscinet/freeTools.html \MSC{05A05, 05A15} % Uncomment exactly one of the following copyright statements. Alternatively, % you can write your own copyright statement subject to the approval of the journal. % See https://creativecommons.org/licenses/ for a full explanation of the % Creative Commons licenses. % % We strongly recommend CC BY-ND or CC BY. Both these licenses allow others % to freely distribute your work while giving credit to you. The difference between % them is that CC BY-ND only allows distribution unchanged and in whole, while % CC BY also allows remixing, tweaking and building upon your work. % % One author: %\Copyright{The author.} %\Copyright{The author. Released under the CC BY license (International 4.0).} %\Copyright{The author. Released under the CC BY-ND license (International 4.0).} % More than one author: %\Copyright{The authors.} %\Copyright{The authors. Released under the CC BY license (International 4.0).} \Copyright{ The authors. Released under the CC BY-ND license (International 4.0).} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % If needed, include a line break (\\) at an appropriate place in the title. \title{On two-sided gamma-positivity for simple permutations\\ } % Input author, affiliation, address and support information as follows; % The address should include the country, but does not have to include % the street address. Give at least one email address. %, , } %\email{ % \author{Ron M.\ Adin\\ \small Department of Mathematics\\[-0.8ex] \small Bar-Ilan University\\[-0.8ex] \small Ramat-Gan 52900, Israel\\ \small\tt radin@math.biu.ac.il\\ \and Eli Bagno \qquad Estrella Eisenberg \qquad Shulamit Reches \qquad Moriah Sigron\\ \small Department of Mathematics\\[-0.8ex] \small Jerusalem College of Technology\\[-0.8ex] \small 21 Havaad Haleumi St., Jerusalem, Israel\\ \small\tt \{bagnoe@g.jct.ac.il,\{estchoc,shulamit.reches\}@gmail.com,moria.sigron@mail.huji.ac.il} %\small\tt \{ssa,sta\}@uwn.edu.au} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract may be distributed without the rest of the % paper so it must be entirely self-contained. Try to include all words % and phrases that someone might search for when looking for your paper. \begin{abstract} Gessel conjectured that the two-sided Eulerian polynomial, recording the common distribution of the descent number of a permutation and that of its inverse, has non-negative integer coefficients when expanded in terms of the gamma basis. This conjecture has been proved recently by Lin. We conjecture that an analogous statement holds for simple permutations, and use the substitution decomposition tree of a permutation (by repeated inflation) to show that this would imply the Gessel-Lin result. We provide supporting evidence for this stronger conjecture. \end{abstract} \section{Introduction} \label{sec:intro} Eulerian numbers enumerate permutations according to their descent numbers. The {\em two-sided Eulerian numbers}, studied by Carlitz, Roselle, and Scoville \cite{CRS} constitute a natural generalization. These numbers count permutations according to their number of descents as well as the number of descents of the inverse permutation. % %Gessel conjectured that the corresponding generating function $A_n(s,t)$ has a nice symmetry property. In order to present this conjecture in a formal way we bring here some definitions. Explicitly, the {\em descent set} of a permutation $\pi \in S_n$ is defined as: \[ \Des(\pi) = \{i \in [n-1] \mid \pi(i)>\pi(i+1)\}. \] Denote $\des(\pi) = |\Des(\pi)|$ and $\ides(\pi) = \des(\pi^{-1})$, the {\em descent numbers} of $\pi$ and $\pi^{-1}$. %\begin{exa} For example, if $\pi= 2 4 6 1 3 5$ then $\Des(\pi)=\{3\}$, $\des(\pi)=1$, $\Des(\pi^{-1})=\{1,3,5\}$ and $\ides(\pi)=3$. %\end{exa} %It is easy to see that for each $\pi \in S_n$ one has $des(\pi)=n-1-des(\pi^r)$, where the {\em reversal} of $\pi = a_1 \ldots a_n$ is $\pi^r = a_n \ldots a_1$; and similarly for $ides(\pi)$. %\begin{defn} A polynomial $f(q)$ is {\em palindromic} if its coefficients are the same when read from left to right as from right to left. Explicitly, if $f(q)=a_rq^r+a_{r+1}q^{r+1} +\cdots +a_sq^s$ with $a_r, a_s \ne 0$ and $r \le s$, then we require $a_{r+i}=a_{s-i}$ $(\forall i)$; equivalently, $f(q) = q^{r+s} f(1/q)$. %\end{defn} Following Zeilberger \cite{Z}, we define the {\it darga} of $f(q)$ as above to be $r+s$; the zero polynomial is considered to be palindromic of each nonnegative darga. The set of palindromic polynomials of darga $n-1$ is a vector space of dimension $\lfloor (n+1)/2 \rfloor$, with {\em gamma basis} \[ \{q^j (1+q)^{n-1-2j} \mid 0 \le j \leq \lfloor (n-1)/2 \rfloor \}. \] The (one-sided) {\em Eulerian polynomial} \[ A_n(q) = \sum_{\pi \in S_n} q^{\des(\pi)} \] is palindromic of darga $n-1$, and thus there are real numbers $\gamma_{n,j}$ such that \[ A_n(q) = \sum_{0 \leq j \leq \lfloor (n-1)/2 \rfloor} \gamma_{n,j} q^j(1+q)^{n-1-2j}. \] See \cite[pp.\ 72, 78]{Pet Book} for details. % Foata and Sch\"utzenberger \cite{F.S} proved that the coefficients $\gamma_{n,j}$ are actually non-negative integers. The result of Foata and Sch\"utzenberger was reproved combinatorially, using an action of the group $\mathbb{Z}_2^n$ on $S_n$ which leads to an interpretation of each coefficient $\gamma_{n,j}$ as the number of orbits of a certain type. This method, called ``valley hopping", is described in \cite{F.St, Branden}. A nice exposition appears in \cite{P}. \medskip Now let $A_n(s,t)$ be the {\em two-sided Eulerian polynomial} \[ A_n(s,t) = \sum_{\pi \in S_n} s^{\des(\pi)} t^{\ides(\pi)}. \] %where $ides(\pi) = des(\pi^{-1})$. % It is well known (see, e.g., \cite[p.\ 167]{P}) that the bivariate polynomial $A_n(s,t)$ satisfies % \begin{equation}\label{eq.pal} A_n(s,t) = (st)^{n-1} A_n(1/s, 1/t) \end{equation} as well as \begin{equation}\label{eq.inv} A_n(s,t) = A_n(t,s). \end{equation} % In fact, (\ref{eq.pal}) follows from the bijection from $S_n$ onto itself taking a permutation to its reverse, while (\ref{eq.inv}) follows from the bijection taking each permutation to its inverse. A bivariate polynomial satisfying Equations (\ref{eq.pal}) and (\ref{eq.inv}) will be called (bivariate) {\em palindromic of darga} $n-1$. Note that if we arrange the coefficients of a bivariate palindromic polynomial in a matrix, then this matrix is symmetric with respect to both diagonals. \begin{example} The two-sided Eulerian polynomial for $S_4$ is: \[ A_{4}(s,t)=1+10st+10(st)^2+(st)^3+st^2+s^2t. \] Its matrix of coefficients is \[ \left( \begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 10 & 1 & 0 \\ 0 & 1 & 10 & 0 \\ 0 & 0 & 0 & 1 \end{array} \right), \] and is clearly symmetric with respect to both diagonals. \end{example} It can be proved (see \cite[p.\ 78]{Pet Book}) that the set of bivariate palindromic polynomials of darga $n-1$ is a vector space of dimension $\lfloor (n+1)/2 \rfloor \cdot \lfloor (n+2)/2 \rfloor$, with {\em bivariate gamma basis} \[ \{(st)^i(s+t)^j(1+st)^{n-1-j-2i} \mid i,j \ge 0,\, 2i+j \le n-1 \}. \] A bivariate palindromic polynomial is called {\em gamma-positive} if all the coefficients in its expression in terms of the bivariate gamma basis are nonnegative. Gessel (see \cite[Conjecture 10.2]{Branden}) conjectured that the two-sided Eulerian polynomial $A_n(s,t)$ is gamma-positive. This has recently been proved by Lin \cite{Lin}. Explicitly: \begin{theorem}\label{t:Gessel} {\rm (Gessel's conjecture, Lin's theorem)} For each $n \geq 1$ there exist nonnegative integers $\gamma_{n,i,j}$ $(i,j \ge 0,\, 2i+j \leq n-1)$ such that \[ A_n(s,t)=\sum\limits_{i,j}{\gamma_{n,i,j}(st)^i(s+t)^j(1+st)^{n-1-j-2i}}. \] \end{theorem} An explicit recurrence for the coefficients $\gamma_{n,i,j}$ was described by Visontai~\cite{V}. This recurrence does not directly imply the positivity of the coefficients, but Lin~\cite{Lin} managed to use it to eventually prove Gessel's conjecture. Unlike the univariate case, no combinatorial proof of Gessel's conjecture is known. \medskip Simple permutations (for their definition see Section~\ref{sec:simple permutations}) serve as building blocks of all permutations. We propose here a strengthening of Gessel's conjecture, for the class of simple permutations. \begin{conjecture} \label{conj:simple} For each positive $n$, the bivariate polynomial \[ \simp_{n}(s,t) = \sum_{\sigma \in \Simp_n} s^{\des(\sigma)} t^{\ides(\sigma)} \] is gamma-positive, where $\Simp_n$ is the set of simple permutations of length $n$. \end{conjecture} Using the substitution decomposition tree of a permutation (by repeated inflation), we show how this cojecture implies the Gessel-Lin result. A combinatorial proof of the conjecture will give a combinatorial proof of the Gessel-Lin result. We also provide supporting evidence for this stronger conjecture. %We represent each permutation as a tree, composed of its simple blocks and define actions on that tree from which we can produce a combinatorial proof of Gessel's conjecture provided the validity of the conjecture for simple permutations. We therefore reduce the claim of gamma positivity of arbitrary permutations to that of simple ones. \medskip The rest of the paper is organized as follows. Section \ref{sec:simple permutations} contains background material concerning simple permutations, inflation, and the substitution decomposition tree of a permutation. In Section \ref{sec:partial settlement} we introduce combinatorial involutions on the tree, and use them to give a combinatorial proof of Gessel's conjecture for a certain class of permutations, $H(5) \cap S_n$. In Section~\ref{sec:reduction} we show how, more generally, Lin's theorem (Gessel's conjecture) follows combinatorially from Conjecture \ref{conj:simple}. Finally, in Section \ref{sec:generating function}, we give a formula for $\simp_{n}(s,t)$ which may have independent value. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Simple permutations and inflation}\label{sec:simple permutations} We start by presenting some preliminaries concerning simple permutations, inflation and the substitution decomposition tree. Original papers will be mentioned occasionally, but terminology and notation will follow (with a few convenient exceptions) the recent survey \cite{Vatter}. \begin{definition} Let $\pi=a_1 \ldots a_n \in S_n$. A {\em block} (or {\em interval}) of $\pi$ is a nonempty contiguous sequence of entries $a_i a_{i+1} \ldots a_{i+k}$ whose values also form a contiguous sequence of integers. \end{definition} \begin{example} If $\pi = 2647513$ then $6475$ is a block but $64751$ is not. \end{example} Each permutation can be decomposed into singleton blocks, and also forms a single block by itself; these are the {\em trivial blocks} of the permutation. All other blocks are called {\em proper}. \begin{definition} A permutation %of length $n \ge 2$ is {\em simple} if it has no proper blocks. \end{definition} \begin{example}\label{ex:simple up to 5} The permutation $3517246$ is simple. \end{example} %for $n=1$ and $n=2$ are $1$, $12$ and $21$. The simple permutations of length $n \le 2$ are $1$, $12$ and $21$. There are no simple permutations of length $n=3$. Those of length $n=4$ are $2413$ and its inverse (which is also its reverse). For length $n=5$ they are $24153$, $41352$, their reverses and their inverses (altogether $6$ permutations). \begin{definition} A {\em block decomposition} of a permutation is a partition of it into disjoint blocks. \end{definition} For example, the permutation $\sigma=67183524$ can be decomposed as $67\ 1\ 8\ 3524$. In this example, the relative order between the blocks forms the permutation $3142$, i.e., if we take for each block one of its digits as a representative then the set of representatives is order-isomorphic to $3142$. Moreover, the block $67$ is order-isomorphic to $12$, and the block $3524$ is order-isomorphic to $2413$. These are instances of the concept of {\em inflation}, defined as follows. \begin{definition} Let $n_1, \ldots, n_k$ be positive integers with $n_1 + \ldots + n_k = n$. The {\em inflation} of a permutation $\pi \in S_k$ by permutations $\alpha_i \in S_{n_i}$ $(1 \leq i \leq k)$ is the permutation $\pi[\alpha_1, \ldots, \alpha_k] \in S_n$ obtained by replacing the $i$-th entry of $\pi$ by a block which is order-isomorphic to the permutation $\alpha_i$ on the numbers $\{s_i + 1, \ldots, s_i + n_i\}$ instead of $\{1, \ldots, n_i\}$, where $s_i = n_1 + \ldots + n_{i-1}$ $(1 \leq i \leq k)$. \end{definition} \begin{example} The inflation of $2413$ by $213,21,132$ and $1$ is \[ 2413[213,21,132,1]=546 \ 98 \ 132 \ 7. \] \end{example} A very important fact is that inflation is additive on both $\des$ and $\ides$. \begin{observation}\label{respect des} Let $\sigma=\pi[\alpha_1,\dots,\alpha_k]$. Then \[ \des(\sigma)=\des(\pi)+\sum_{i=1}^n{\des(\alpha_i)} \] and \[ \ides(\sigma)=\ides(\pi)+\sum_{i=1}^n{\ides(\alpha_i)}. \] \end{observation} Two special cases of inflation, deserving special attention, are the {\em direct sum} and {\em skew sum} operations, defined as follows. \begin{definition} Let $\pi \in S_m$ and $\sigma \in S_n$. The {\em direct sum} of $\pi$ and $\sigma$ is the permutation $\pi \oplus \sigma \in S_{m+n}$ defined by \[ (\pi \oplus \sigma)_i = \begin{cases} \pi_i, & \text{if } i \leq m; \\ \sigma_{i-m}+m, & \text{if } i>m, \end{cases} \] and their {\em skew sum} is the permutation $\pi \ominus \sigma \in S_{m+n}$ defined by \[ (\pi \ominus \sigma)_i = \begin{cases} \pi_{i}+n, & \text{if } i \leq m; \\ \sigma_{i-m}, & \text{if } i>m. \end{cases} \] \end{definition} \begin{example} If $\pi=132$ and $\sigma=4231$ then $\pi \oplus \sigma=1327564$ and $\pi \ominus \sigma=5764231$ \end{example} Note that $\pi \oplus \sigma = 12[\pi,\sigma]$ and $\pi \ominus \sigma = 21[\pi,\sigma]$. \begin{definition}\label{sum-indecomposable} A permutation is {\em sum-indecomposable} (respectively, {\em skew-indecomposable}) if it cannot be written as a direct (respectively, skew) sum. \end{definition} The following proposition shows that every permutation has a canonical representation as an inflation of a simple permutation. \begin{proposition}\label{t.substitution}%\cite{A.S} \cite[Theorem 1]{AAK}\cite[Proposition 3.10]{Vatter} Let $\sigma \in S_n$ $(n \geq 2)$. Then there exist a unique integer $k \ge 2$, a unique simple permutation $\pi \in S_k$, and a sequence of permutations $\alpha_1,\ldots,\alpha_k$ such that \[ \sigma = \pi[\alpha_1,\dots,\alpha_k]. \] If $\pi \notin \{12,21\}$ then $\alpha_1, \ldots,\alpha_k$ are also unique. If $\pi=12$ $(\pi=21)$ then $\alpha_1, \alpha_2$ are unique as long as we require, in addition, that $\alpha_2$ is sum-indecomposable (respectively, skew-indecomposable). \end{proposition} \begin{example} The permutation $\sigma=452398167$ can be written as an inflation of the simple permutation $2413$: \[ \sigma=2413[3412, 21, 1, 12]. \] \end{example} \begin{remark} \label{right chain condition in permutations} The additional requirements for $\pi = 12$ and $\pi = 21$ are needed for uniqueness of the expression. To see that, note that the permutation $123$ can be written as $12[12,1]=12 \ 3$ but also as $12[1,12]=1 \ 23$. The first expression is the one preferred above (with $\alpha_2$ sum-indecomposable). \end{remark} One can continue the process of decomposition by inflation for the constituent permutations $\alpha_i$, recursively, until all the resulting permutations have length $1$. %are simple. In the example above, $3412$ can be further decomposed as $3412=21[12,12]$, so that \[ \sigma= 2413[21[12,12],21,1,12] \] and, eventually, \[ \sigma= 2413[21[12[1,1],12[1,1]],21[1,1],1,12[1,1]]. \] %\begin{rem} \label{T of pi} % * 2016-05-19T20:57:41.963Z: % % ^. % * 2016-05-19T20:57:41.503Z: % % ^. This information can be encoded by a tree, as follows. \begin{definition}\label{tree of perm} Represent each permutation $\sigma$ by a corresponding {\em substitution decomposition tree} $T_{\sigma}$, recursively, as follows. \begin{itemize} \item If $\sigma = 1 \in S_1$, represent it by a tree with one node. \item Otherwise, write $\sigma=\pi[\alpha_1,\ldots,\alpha_k]$ as in Proposition~\ref{t.substitution}, and represent $\sigma$ by a tree with a root node, labeled $\pi$, having $k$ ordered children corresponding to $\alpha_1,\ldots,\alpha_k$. Replace each child $\alpha_i$ by the corresponding tree $T_{\alpha_i}$. \end{itemize} \end{definition} % In the latter case, if $\alpha_i$ is not simple, then by Proposition \ref{t.substitution} it can be represented as $\alpha_i=\pi'[\beta_1,\ldots,\beta_k]$ with $\pi'$ simple. We take $\pi'$ to be the root of the new sub-tree. % If $\alpha_i$ is simple of length $k$ then we can write $\alpha_i=\alpha_i[1,1,\dots, 1]$ and it has $k$ (unlabeled) leaves. % We proceed in a recursive manner. %\end{rem} \begin{figure} \begin{center} %\hspace*{-5.5cm} \includegraphics[scale=1]{eli2.pdf} \caption{The tree $T_\sigma$ for $\sigma=452398167$} \label{fig:one tree} \end{center} \end{figure} \begin{example} Figure \ref{fig:one tree} depicts the substitution decomposition tree $T_{\sigma}$ for $\sigma=452398167$. For clarity, the leaves are labeled by the corresponding values of the permutation $\sigma$, instead of simply $1$. \end{example} % Now, given a tree, we present a recursive algorithm to find the corresponding permutation. % Note that the digit placed in the j-th position in the label of each node refers to the j-th sub-tree of this node. % \begin{enumerate} % \item % Let $k=1$. % \item % Start with the root, with the sub-tree corresponding to $i=1$. % \item % If that sub-tree is a leaf, then label this leaf by $k$ and increase $k$ by $1$. % \item % Otherwise descend to the root of that sub-tree and go back to $(2)$ with respect to this sub-tree. % \item % Increase $i$ by $1$ and go back to $(3)$ for the next digit. % \end{enumerate} % Now the permutation can be obtained by reading the labeled leaves from the left to the right. % \begin{exa} % We refer to the last example. % Starting with the root node, labeled $2413$, consider first the digit $1$. % Its sub-tree is a leaf, so we label this leaf by $1$. % Then we proceed to the sub-tree of digit $2$. Note that $4$ of its descendants are leaves. % We descend to the leftmost sub-tree of $2413$ which is labeled $21$. The digit $1$ in the root of this sub-tree has a sub-tree labeled $12$ the leaves of which we label by $2$ and $3$ (from left to right) % Now we go back one level up and descend to the left son of the $21$ node. % This node has two leaves which will be labeled as $4$ and $5$ % from left to right. Now we go to digit $3$ of the root and proceed in this % way until all of the leaves are labeled. Finally we get the picture appearing in Figure \ref{fig:one tree}. % \end{exa} %Inflation is actually a localized version of Inflation can be extended to %the {\em wreath product} construction introduced in \cite{A.S}. sets of permutations (an operation called {\em wreath product} in \cite{A.S}). \begin{definition} Let $\mathcal{A}$ and $\mathcal{B}$ be sets of permutations. %The {\em wreath product} of $\mathcal{A}$ and $\mathcal{B}$ is Define \[ %\mathcal{A} \wr \mathcal{B} \mathcal{A}[\mathcal{B}] = \{\alpha[\beta_1,\ldots,\beta_k] \mid \alpha \in \mathcal{A},\, \beta_1,\ldots,\beta_k \in \mathcal{B} \}. \] \end{definition} \begin{example} Let $A=\{12\}$ and $B=\{21,132\}$. Then \[ %A \wr B A[B] = \{2143,21354,13254,132465\}. \] \end{example} \begin{definition} A set $C$ of permutations is %{\em wreath-closed} if $H=H \wr H$. {\em substitution-closed} if $C = C[C]$. %The {\em wreath closure} $\wc(H)$ The {\em substitution closure} $\langle C \rangle$ of a set $C$ of permutations is the smallest %wreath-closed substitution-closed set of permutations which contains $C$. \end{definition} %The wreath product The inflation operation is associative. Defining $C_1 = C$ and %$H_{n+1} = H \wr H_n$, we have % \[ % \wc(H) = \bigcup_{n=1}^{\infty}{H_n}. % \] $C_{n+1} = C[C_n]$, we clearly have \[ \langle C \rangle = \bigcup_{n=1}^{\infty} C_n. \] % \begin{exa} % Let $A=\{21\}$. Then it is easy to see that $A\wr A=\{4321\}$ and $(A\wr A)\wr A=\{87654321\}$ and continuing in this manner one obtains that $\wc(A)=\{[2^n, 2^{n}-1,\cdots, 1] \mid n \in \mathbb{N}\}$. % \end{exa} %Finally, we have the following definition: \begin{definition}\label{def:Simp} For a positive integer $n$, let $\Simp_n$ ($\Simp_{\leq n}$) be the set of all simple permutations of length $n$ (respectively, of length at most $n$). %Let $H(n)=\wc(\Simp_{\leq n})$, the wreath-closure of $\Simp_{\leq n}$. Let $H(n)=\langle \Simp_{\leq n} \rangle$, the substitution closure of $\Simp_{\leq n}$. \end{definition} %The following example has significance for the sequel. \begin{example} %$H(2)=\wc\{1,12,21\}$ $H(2) = \langle \Simp_{\le 2} \rangle = \langle \{1,12,21\} \rangle$ is the set of all permutations that can be obtained from the trivial permutation $1$ by direct sums and skew sums. These are exactly the {\em separable permutations}, counted by the {\em large Schr\"oder numbers;} see \cite{W}. % Separable permutations can also be described via pattern avoidance, namely \[ H(2)=\Av(3142,2413). \] For more details see \cite[following Proposition 3.2]{B.H.V.}. \end{example} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Gamma-positivity for $H(5)$} %{A partial settlement of Gessel's conjecture} \label{sec:partial settlement} In this section we present a combinatorial proof of Gessel's conjecture (Lin's theorem) for the subset $H(5) \cap S_n$ of $S_n$ (for any positive $n$). %Gessel's conjecture for the case $H(2)$ can be derived from the paper of Fu, Lin and Zeng \cite{F.L.Z.} proved the following (univariate) gamma-positivity result. \begin{proposition} For each $n$ there exist nonnegative integers $\gamma_{n,k}$ $(0 \leq k \leq \lfloor (n-1)/2 \rfloor)$ such that \[ \sum_{\pi \in H(2)\cap S_n}{t^{\des(\pi)} = \sum_{k=0}^{\lfloor (n-1)/2 \rfloor}} { \gamma_{n,k} t^k (1+t)^{n-1-2k}} \] \end{proposition} By Observation~\ref{respect des}, if $\pi \in H(2)$ then $\des(\pi)=\ides(\pi)$. %(This can be concluded from Observation \ref{respect des}). Hence, one can conclude the following restricted version of Gessel's conjecture for the set of separable permutations. \begin{theorem} \label{H(2)} For each $n$ there exist non-negative integers $\gamma_{n,k}$ $(0 \leq k \leq \lfloor (n-1)/2 \rfloor)$ such that: \[ \sum_{\pi \in H(2) \cap S_n}{s^{\des(\pi)}t^{\ides(\pi)}=\sum_{\pi \in H(2) \cap S_n}{(st)^{\des(\pi)}=\sum_{k=0}^{\lfloor (n-1)/2 \rfloor}}{ \gamma_{n,k} (st)^k (1+st)^{n-1-2k}}}. \] \end{theorem} % Every root which has a simple permutation of length $2$ as a label (i.e. $12$ or $21$) is a root of a binary sub-tree. We give special attention to the maximal binary sub-trees. For each maximal binary sub-tree, following \cite{B.H.V.}, we define the notion of a right chain as follows: In order to extend Theorem \ref{H(2)} further, let us introduce some more definitions. \begin{definition}\label{def:BRC} Let $T$ be a tree with all internal nodes labeled by simple permutations. A {\em binary right chain} (BRC) is a maximal nonempty chain composed of consecutive right descendants, all of which are from the set $\{12,21\}$. The {\em length} of a BRC is the number of nodes in it. %; note that a BRC may contain a single node. Denote by $r_{odd}(T)$ the number of BRC of odd length in $T$. \end{definition} \begin{example} The tree $T_{\sigma}$ in Figure \ref{fig:one tree} has $4$ BRC, and $r_{odd}(T_{\sigma})=3$. %$= 2$. \end{example} \begin{figure} \begin{center} %\hspace*{-5.5cm} \includegraphics[scale=0.8]{eli1.pdf} \caption{Left: the tree $T$. Right: The tree $\phi_1(T)$.} \label{fig:two trees} \end{center} \end{figure} \begin{definition}\label{def:G-tree} A tree $T$ is called a {\em G-tree} if %it is labeled by simple permutations and the following ``right chain condition" is satisfied: %The labeling on each BRC alternates between $12$ and $21$. it satisfies: \begin{enumerate} \item Each leaf is labeled by $1$. \item Each internal node is labeled by a simple permutation ($\ne 1$), and the number of its children is equal to the length of the permutation. \item The labels in each BRC alternate between 12 and 21. \end{enumerate} Denote by $\mathcal{GT}_n$ the set of all G-trees with $n$ leaves. %(Recall that each $S_n$ permutation can be represented as such a tree). \end{definition} %Note that the right chain condition corresponds precisely to the %way we constructed the inflation in Remark \ref{right chain condition in permutations}. % By the preceding argument, we can deduce the following theorem: \begin{lemma}\label{bijection perms to trees} % For each $k$, the function which sends each $\pi \in H(k)\cap S_n$ to the G-tree $T_{\pi}$ from Definition \ref{tree of perm} is an injection. The map $f_n : S_n \to \mathcal{GT}_n$ sending each permutation $\sigma$ to its substitution decomposition tree $T_{\sigma}$, as in Definition~\ref{tree of perm}, is a bijection. %from $S_n$ onto $\mathcal{GT}_n$. \end{lemma} \begin{proof} Follows immediately from Proposition~\ref{t.substitution}. The last condition in Definition~\ref{def:G-tree} reflects the extra restrictions for the cases $\pi \in \{12, 21\}$ in Proposition~\ref{t.substitution}. \end{proof} %We present now a combinatorial proof for Gessel's conjecture for $H(5)\cap S_n$ for each $n$. Thus now from on until the end of this section we deal only with permutations in $H(5) \cap S_n$. Let $T=T_{\pi}$ be a G-tree, and let $\{C_i \mid 1 \leq i \leq r_{odd}(T)\}$ be the set of all BRC of odd length in $T$. For each $i$, let $\phi_i(T)$ be the tree obtained from $T$ by switching $12$ and $21$ in each of the nodes of $C_i$. (A similar action was introduced in \cite{F.L.Z.} for univariate polynomials.) Clearly, each operator $\phi_i$ is an involution, and the various $\phi_i$ commute. By Observation~\ref{respect des}, each $\phi_i$ changes both $\des(\pi)$ and $\ides(\pi)$ by $\pm1$. \begin{example} Consider $\pi = 6713254$. The corresponding tree $T=T_{\pi}$ appears on the left side of Figure \ref{fig:two trees}, and has $r_{odd}(T)=2$. If %we number the odd chains from right to left, $C_1$ is the unique BRC of length $3$ in $T$, then $\phi_1(T)$ is the tree on the right side of the figure. The permutation corresponding to $\phi_1(T)$ is $1257634$. Note that $\phi_1$ decreased both $\des(\pi)$ and $\ides(\pi)$ by $1$. \end{example} Let $T = T_{\pi}$ be a G-tree, and let $l_1,\ldots,l_k$ be the labels of nodes in $T$ that belong to the set $\Simp_4 = \{2413,3142\}$. Define $\psi_j(T)$ $\textup{(}1 \leq j \leq k\textup{)}$ to be the tree obtained from $T$ by switching the label $l_j$ from $2413$ to $3142$, or vice versa. Again, it is easy to see that the $\psi_j$ are commuting involutions, and each $\psi_j$ commutes with each $\phi_i$. Switching from $2413$ to $3142$ increases $\des(\pi)$ by $1$ while decreasing $\ides(\pi)$ by $1$. %, and passing from $3142$ back to $2413$ increases $\ides(\pi)$ and decreases $\des(\pi)$ by $1$. \begin{remark} Each of the $6$ simple permutations $\pi \in \Simp_5$ has $\des(\pi) = \ides(\pi) = 2$, and we don't need to define involutions for them. \end{remark} \begin{definition} For any two G-trees $T_1$ and $T_2$, write $T_1 \sim T_2$ if $T_2$ can be obtained from $T_1$ by a sequence of applications of the involutions $\phi_i$ and $\psi_j$. \end{definition} Clearly $\sim$ is an equivalence relation, partitioning the set $\mathcal{GT}_n$ (equivalently, the group $S_n$) into equivalence classes. \begin{definition} For each equivalence class in $\mathcal{GT}_n$, let $T_0$ be the unique tree in this class in which each odd BRC begins with $12$ and each node representing a simple permutation of length $4$ is labeled $2413$. The corresponding permutation $\pi_0$ has the minimal number of descents in its class. The tree $T_0$ and the permutation $\pi_0$ are called the {\em minimal representatives} of their equivalence class. \end{definition} %Our next goal is to compute the bi-distribution of $\des$ and $\ides$ over each equivalence class. %In order to do that, we pick up the minimal representative $T_0$ and use the actions $\phi_i$ and $\psi_j$ to go over the entire class. % \begin{rem}\label{contribution of actions} % \quad % \begin{itemize} % \item % Each action of the form $\phi_i$ takes each odd BRC beginning with $12$ to an odd BRC beginning with $21$, and vice versa. Hence, if $T$ is a tree with a binary right chain $R$ of length $2c+1$, then $R$ and its counterpart in $\phi_i(T)$ together contribute a factor of $(st)^c (1+st)$ to the bi-distribution of $\des$ and $\ides$ over the whole class. % Each even BRC of length $2d$ contributes a factor of $(st)^d$. % %where $d$ is the number of nodes of the form $21$ in the chain. % \item % Each action of the form $\psi_j$ takes a node of the form $2413$ to a node of the form $3142$. % %, hereby increasing the number of descents by $1$ and decreasing the number of inverse descents by $1$. % The two nodes together contribute $st^2 + s^2t = st (s+t)$. % \item % For nodes labeled by simple permutations of length $5$, since each of the $6$ simple permutations of this length (see Example~\ref{ex:simple up to 5}) contributes $(st)^2$, there is no need for an action between them. % \end{itemize} % \end{rem} %We proceed with some notations which will be needed in the sequel. \begin{lemma}\label{over class} Let $A$ be an equivalence class of permutations in $H(5)\cap S_n$. There exist nonnegative integers $i$ and $j$ such that \[ \sum_{\sigma \in A} s^{\des(\sigma)} t^{\ides(\sigma)} = (st)^{i} (s+t)^{j} (1+st)^{n-1-2i-j}. \] \end{lemma} \begin{proof} Let $\pi_0$ be the minimal representative of $A$, and let $T_0 = T_{\pi_0}$. For $i \in \{2,4,5\}$, let $v_i$ be the number of nodes of $T_0$ having labels of length $i$. Since $T_0$ has exactly $n$ leaves, its total number of nodes (including leaves) is %\begin{equation}\label{v_2} \[ v = n + v_2 + v_4 + v_5. \] %\end{equation} % On the other hand, counting the children of each node gives %nodes of the tree in such a way that each vertex contributes the number of its sons, we have that %\begin{equation}\label{v} \[ v - 1 = \sum_{i\in \{2, 4, 5\}} i v_i. \] %\end{equation} %Using Equations (\ref{v_2}) and (\ref{v}), we conclude that It follows that \[ %v_2=2v_2+4v_4+5v_5+1-n-v_4-v_5=3v_4+4v_5+2v_2+1-n, n-1 = v_2 + 3v_4 + 4v_5. \] %and thus $v_2=n-1-3v_4-4v_5$. %For example, the tree in Figure \ref{fig:one tree} has $v_4=1,v_2=5,v=4v_4+2v_2+1=15$. Let $r = r_{odd}(T_0)$ be the number of odd BRC in $T_0$, and let $d_2$ be the number of nodes labeled $21$. By definition, each BRC alternates between $12$ and $21$ and each odd BRC in $T_0$ starts with $12$. %Thus $v_2=2d_2+r_0$, or equivalently It follows that %\begin{equation}\label{eq:r} \[ v_2 = 2d_2 + r, \] %\end{equation} so that \begin{equation}\label{eq:number_of_nodes} n-1 = r + 2d_2 + 3v_4 + 4v_5. \end{equation} Now recall that $\des(12)=\ides(21)=0$, $\des(21)=\ides(21)=1$, $\des(2413)=1$, $\ides(2413)=2$, $\des(3142)=2$, $\ides(3142)=1$, and for each simple permutation $\sigma$ of length $5$ we have $\des(\sigma)=\ides(\sigma)=2$. it follows from Observation~\ref{respect des} that %\begin{equation}\label{des of vertices} \[ \des(\pi_0)=d_2+v_4+2v_5 \] %\end{equation} and %\begin{equation}\label{ides of vertices} \[ \ides(\pi_0)=d_2+2v_4+2v_5, \] %\end{equation} so that the bivariate monomial corresponding to $\pi_0$ is \[ s^{\des(\pi_0)} t^{\ides(\pi_0)} = (st)^{d_2 + v_4 + 2v_5} t^{v_4}. \] Consider now the whole equivalence class $A$, whose elements are obtained from $\pi_0$ by applications of the commuting involutions $\phi_1, \ldots, \phi_r$ and $\psi_1, \ldots, \psi_k$, where $r = r_{odd}(T_0)$ is the number of BRC in $T_0$ and $k = v_4$. Each application of $\phi_i$ multiplies the monomial by $st$, and each application of $\psi_j$ multiplies it by $st^{-1}$. It follows that %Now, by Remark \ref{contribution of actions}, we have that %recall that the application of each $\phi_i$ adds $1$ to both $des(\pi_0)$ and $ides(\pi_0)$, for each $i$, $(1\leq i\leq r_0)$, and the application of $\psi_j$ adds $1$ to $des(\pi_0)$ and subtracts $1$ from $ides(\pi_0)$ for each $j$, ($1\leq j\leq v_4)$, so that we obtain \[ \begin{aligned} \sum_{\sigma \in A}%\sim \pi_0} s^{\des(\sigma)} t^{\ides(\sigma)} &= (st)^{d_2+v_4+2v_5} t^{v_4} (1+st)^{r} (1 + st^{-1})^{v_4} \\ &= (st)^{d_2+v_4+2v_5} (s+t)^{v_4} (1+st)^{r}. \end{aligned} \] Denoting $i = d_2+v_4+2v_5$ and $j = v_4$ will complete the proof, once we show that \[ 2(d_2+v_4+2v_5) + v_4 +r = n-1; \] but this follows immediately from equation~\eqref{eq:number_of_nodes} above. % We finally have: % \begin{equation}\label{second v_2} % r_0=n-1-3v_4-4v_5-2d_2. % \end{equation} %By Equations \ref{des of vertices} and \ref{ides of vertices}, we have for the minimal representative $\pi_0$ that $$s^{\des(\pi_0)}t^{\ides(\pi_0)}=(st)^{d_2+v_4+2v_5}t^{v_4}.$$ % If we denote $i=d_2+v_4+2v_5$ and $j=v_4$ then we finally have % $$\sum_{\sigma \sim \pi_0}{s^{\des(\sigma)}t^{\ides(\sigma)}}=(st)^{i}(s+t)^{j}(1+st)^{n-1-2i-j}$$ \end{proof} Lemma \ref{over class} immediately implies one of the main results of this paper: \begin{theorem}\label{main theorem} %Let $n \in \mathbb{N}$. There exist $\alpha_{n,i,j} \in \mathbb{N}_0$, $(1 \leq i \leq n)$, $(0 \leq j \leq n-1)$,$(0 \leq j+2i \leq n-1)$, such that: %\begin{equation*}\label{simple_pol1} %\sum\limits_{\sigma \in H(5)\cap S_n}{s^{des(\sigma)}t^{ides(\sigma)}}=\sum\limits_{i,j}{ \alpha_{n,i,j} (st)^i (s+t)^j(1+st)^{n-1-2i-j}}. %\end{equation*} For each $n \ge 1$, the polynomial \[ \sum_{\sigma \in H(5) \cap S_n} s^{des(\sigma)} t^{ides(\sigma)} \] is gamma-positive. \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Gamma-positivity for simple permutations} %{A reduction of Gessel's conjecture for simple permutations} \label{sec:reduction} For each positive integer $n$, the set $\Simp_n$ of simple permutations of length $n$ is invariant under taking inverses and reverses. It follows that the bivariate polynomial \[ \simp_{n}(s,t) = \sum_{\sigma \in \Simp_n} s^{\des(\sigma)} t^{\ides(\sigma)} \] is palindromic, and can be expanded in the gamma basis. Conjecture~\ref{conj:simple}, presented in the Introduction, states that this polynomial is, in fact, gamma-positive. The main result of this section is the following. \begin{theorem} Conjecture~\ref{conj:simple} implies Gessel's conjecture (Lin's theorem), Theorem~\ref{t:Gessel}. \end{theorem} \begin{proof} For each permutation $\sigma$ of length $n \ge 2$, consider its substitution decomposition tree $T_{\sigma}$. Each internal node of $T_{\pi}$ is labeled by some simple permutation $\pi$ of length $\ell = \ell(\pi) \ge 2$. Replace $\pi$ by $\ell$, to obtain a {\em simplified tree} $T'_{\sigma}$ (with internal nodes labeled by numbers). For permutations $\sigma_1, \sigma_2 \in S_n$ define $\sigma_1 \sim \sigma_2$ if $T'_{\sigma_1} = T'_{\sigma_2}$. Clearly $\sim$ is an equivalence relation on $S_n$, with each equivalence class corresponding to a unique simplified tree $T'$. Denote such a class by $A(T')$. Define a BRC of $T'$ (in analogy to Definition~\ref{def:BRC}) to be a maximal nonempty chain of consecutive right descendants, all labeled $2$. How can we recover a permutation $\sigma \in A(T')$ from the tree $T'$? Each internal node, labeled by a number $\ell$, can be relabeled by any simple permutation of length $\ell$, with the single restriction that the labels in each BRC must alternate between $12$ and $21$, starting with either of them. % In this general case, however, the nodes are labeled by simple permutations of arbitrary length. Then we define an equivalence relation on $S_n$ by declaring that two trees belong to the same class if one can be reached from the other by applying a series of actions of the following two types: % \begin{enumerate} % \item % Replace a label of one node (which is a simple permutation of length $k \geq 4$) by a simple permutation of the same order. % \item % Alternate the labels of an odd right chain, as described in the paragraph after Lemma \ref{bijection perms to trees}. % \end{enumerate} It thus follows, by Observation~\ref{respect des}, that for each simplified tree $T'$, the polynomial \[ \sum_{\sigma \in A(T')} s^{\des(\sigma)} t^{\ides(\sigma)} \] is a product of factors, as follows: \begin{itemize} \item Each internal node with label $\ell \geq 4$ contributes a factor $\simp_\ell(s,t)$. \item Each BRC of even length $2k$ contributes a factor $2(st)^k$. \item Each BRC of odd length $2k+1$ contributes a factor $(st)^k (1+st)$. \end{itemize} By Conjecture~\ref{conj:simple}, all those factors are gamma-positive, and so is their product. Summing over all equivalence classes in $S_n$ completes the proof. % In summary, for each $i$, let $l_i$ be the length of the simple permutation labeling the node $v_i$. Assume that $T_{\sigma}$ has $m$ nodes. Then each node $v_i$ contributes $l_i-1$ to the darga of $S_{[\sigma]}$. As a result we obtain that the darga of $S_{[\sigma]}$ is $\sum\limits_{i=1}^m{(l_i-1)}=n-1$. \end{proof} It is clear from the arguments above that a {\em combinatorial} proof of Conjecture~\ref{conj:simple} will immediately yield a combinatorial proof of Theorem~\ref{t:Gessel}. In fact, the preceding section contains such a combinatorial proof assuming there are only labels $\ell \le 5$, using $\simp_4(s,t) = st (s+t)$ and $\simp_5(s,t) = 6(st)^2$. We were unable to extend the combinatorial arguments to length $6$, although the corresponding polynomial is indeed gamma-positive: % % Recall that $\Simp_n$ is the set of all simple permutations in $S_n$. % Since $\Simp_n$ is closed under the actions of reverse and inverse, we have by symmetry arguments (see \cite[p.\ 78]{P}) the following: % \begin{prop} % For each positive $n$ there exist integers $\gamma_{n,i,j}$ $(i,j \geq 0,\, j+2i \leq n-1)$ such that: % %\begin{equation*}\label{simple_pol2} % \[ % \simp_n(s,t) = \sum_{\pi \in \Simp_n}{s^{\des(\pi)}t^{\ides(\pi)}}=\sum\limits_{i,j}{ \gamma_{n,i,j} (st)^i (s+t)^j(1+st)^{n-1-2i-j}}. % \] % %\end{equation*} % \end{prop} % % In the preceding sections we defined actions on the set of simple permutations for $n=2$ (the reverse action), for $n=4$, (the reverse action again) and also (the identity action) for $n=5$. % Consequently, we obtain $\simp_2(s,t)=(1+st)$, $\simp_4(s,t)=st(s+t)$ and $\simp_5(s,t)=6(st)^2$. % % A natural continuation of this work might start with a definition of similar actions on the set of simple permutations for each $n$. % Note that the success of the reverse action in the case $n=4$ is based on the fact that the only simple permutations of $S_4$ have $s^2t$ and $st^2$ as $(\des,\ides)$ monomials which sum up to the gamma-positive polynomial: % $st(s+t)$. % % For $n=5$ there are exactly $6$ simple permutations (see example~\ref{ex:simple up to 5}). % All of them have $s^2t^2$ as $(\des,\ides)$ monomial, and are therefore gamma-positive. % % However, this technique fails to work in the case of $S_6$. Take for example the simple permutation $246135$ which contributes $st^3$ while its reverse contributes $s^4t^2$. Note that even had we allowed also the inverse action, we wouldn't have gained a proper contribution to the Gessel form. % On the other hand, one can easily check that % summing up all the simple permutations of order $6$ will give us the following gamma-positive polynomial: % \[ \simp_6(s,t) = st(s+t)^2(1+st)+5(st)^2(1+st)+14(st)^2(s+t). \] In fact, Conjecture~\ref{conj:simple} has been verified by computer for all $n \le 12$. %computer experiments show that $\simp_n(s,t)$ is gamma-positive for each $n \leq 12$. %The following conjecture seems plausible: % \begin{con}%\label{conj_simple} % For each positive integer $n$, the bivariate polynomial $\simp_n(s,t)$ is gamma-positive; % i.e., there exist nonnegative integers $\alpha_{n,i,j}$ $(0 \leq j+2i \leq n-1)$ such that: % %\begin{equation*}\label{simple_pol3} % \[ % \simp_n(s,t) % = \sum_{\pi \in \Simp_n}{s^{\des(\pi)}t^{\ides(\pi)}} % = \sum_{i,j}{ \alpha_{n,i,j} (st)^i (s+t)^j (1+st)^{n-1-2i-j}}. % \] % %\end{equation*} % \end{con} % \begin{con} % %\label{conj:simple} % For each positive $n$, the bivariate polynomial % \[ % \simp_{n}(s,t) = \sum_{\sigma \in \Simp_n} s^{\des(\sigma)} t^{\ides(\sigma)} % \] % is gamma-positive, where $\Simp_n$ is the set of simple permutations of length $n$. % \end{con} % \begin{rem} % Note that from the discussion above we can not deduce the opposite implication, i.e. the validity of Gessel's conjecture for the entire group $S_n$ does not imply the validity of the conjecture for the simple permutations. % Explicitly: % \[ % \begin{aligned} % A_{n+1}(s,t) % &= \sum_{i,j} \gamma_{n+1,i,j} (st)^i (s+t)^j (1+st)^{n-1-2i-j} \\ % &= \sum_{\pi \in \Simp_{n+1}} \alpha_{n+1,i,j} (st)^i (s+t)^j (1+st)^{n-1-2i-j} \\ % &\quad + \sum_{\pi \notin \Simp_{n+1}} \beta_{n+1,i,j} (st)^i (s+t)^j (1+st)^{n-1-2i-j}. % \end{aligned} % \] % Even if we accept Gessel's conjecture for all the simple permutations of length less or equal to $n$, (which implies the positiveness of the $\beta_{n+1,i,j}$, since each non-simple permutation of $S_{n+1}$ is an inflation of simple permutations of order less than or equal to $n$) and we accept it for the whole group $S_k$ for each $k \in \mathbb{N}$ (which implies in turn the positiveness of the $\gamma_{n+1,i,j}$), we still can not conclude the correctness of the conjecture for the simple permutations of length $n+1$ which means the positivity of the $\alpha_{n+1,i,j}s'$. % \end{rem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{The bi-Eulerian polynomial for simple permutations}\label{sec:generating function} In \cite{AAK}, the ordinary generating function for the {\em number} of simple permutations was shown to be very close to the functional inverse of the corresponding generating function for all permutations. In this section we refine this result by considering also the parameters $\des$ and $\ides$, thus obtaining a formula for $\simp_n(s,t)$. \medskip Recall from Definition \ref{sum-indecomposable} the notions of sum-indecomposable and skew-indecomposable permutations. \begin{definition} For each positive integer $n$, denote by $I_n^+$ (respectively, $I_n^-$) the set of all sum-indecomposable (respectively, skew-indecomposable) permutations in $S_n$. \end{definition} \begin{definition} Let \begin{align*} F(x,s,t) := \sum_{n=1}^{\infty} \left( \sum_{\pi \in S_n} s^{\des(\pi)} t^{\ides(\pi)} \right) x^n, \\ I^+(x,s,t) := \sum_{n=1}^{\infty} \left( \sum_{\pi \in I^+_n} s^{\des(\pi)} t^{\ides(\pi)} \right) x^n, \\ I^-(x,s,t) := \sum_{n=1}^{\infty} \left( \sum_{\pi \in I^-_n} s^{\des(\pi)} t^{\ides(\pi)} \right) x^n, \\ S(x,s,t) := \sum_{n=4}^{\infty} \left( \sum_{\pi \in \Simp_n} s^{\des(\pi)} t^{\ides(\pi)} \right) x^n. \end{align*} \end{definition} Note that the summation in the definition of $S(x,s,t)$ is only over $n \ge 4$. We want to find relations between these generating functions. From now on, we consider $F(x,s,t)$ etc.\ as formal power series in $x$, with coefficients in the field of rational functions $\mathbb{Q}(s,t)$. We therefore use the short notation $F(x)$, or even $F$. For example, the composition $S \circ F$ means that $F$ is substituted as the $x$ variable of $S(x,s,t)$. By Proposition~\ref{t.substitution} and Observation~\ref{respect des}, \begin{align*} F &= x + I^+ F + st I^- F + \sum_{n=4}^{\infty} \simp_n F^n \\ &= x + I^+ F + st I^- F + S \circ F \end{align*} and similarly %\begin{align*} \[ I^+ = x + st I^- F + S \circ F \] and \[ I^- = x + I^+ F + S \circ F. \] %\end{align*} Rearranging, we have \begin{align*} F I^+ + stF I^- + (S \circ F + x) &= F \\ -I^+ + stF I^- + (S \circ F + x) &= 0 \\ F I^+ - I^- + (S \circ F + x) &= 0 \end{align*} This is a system of linear equations in $I^+$, $I^-$ and $S \circ F + x$. Its unique solution is \begin{equation}\label{e.solutions} \begin{aligned} I^+ &= \frac{F}{1 + F} \\ I^- &= \frac{F}{1 + stF} \\ S \circ F + x &= \frac{F(1 - stF^2)}{(1 + F)(1 + stF)} \end{aligned} \end{equation} Note that the reversal map $\pi \mapsto \pi'$, defined by $\pi'(i)=n-1-\pi(i)$ $(1 \le i \le n)$, is a bijection from $S_n$ onto itself (and also from $I_n^+$ onto $I_n^-$), satisfying $\des(\pi') = n-1-\des(\pi)$ and $\ides(\pi') = n-1-\ides(\pi)$. Therefore: \[ \begin{aligned} F(x,s,t) &= \frac{1}{st} F(xst, 1/s, 1/t) \\ I^-(x,s,t) &= \frac{1}{st} I^+(xst, 1/s, 1/t). \end{aligned} \] This agrees with the first two equations in \eqref{e.solutions}. Denoting $u=F(x)$, the third equation in \eqref{e.solutions} gives an explicit expression for $S(u,s,t)$: \[ S(u,s,t) = -F^{\langle -1 \rangle}(u) + \frac{u(1-stu^2)}{(1+u)(1+stu)}\,, \] where $x = F^{\langle -1 \rangle}(u)$ is the functional inverse of $u = F(x)$. Further manipulations with partial fractions give the following. \begin{proposition} \begin{equation}\label{eq.Sust} S(u,s,t) = -F^{\langle -1 \rangle}(u) + \frac{u}{1 + stu} + \frac{u}{1 + u} -u. \end{equation} \end{proposition} % Let % \[ % \simp_{n}(s,t)=\sum_{\sigma \in \Simp_n}{s^{\des(\sigma)}t^{\ides(\sigma)}}. % \] Using the expansions \[ S(u,s,t) = \sum_{n \ge 4} \simp_n(s,t) u^n \] and \[ F^{\langle -1 \rangle}(u) = \sum_{n \ge 1} f_n^{\langle -1 \rangle}(s,t) u^n, \] %formula~\eqref{eq.Sust} can be written in the following equivalent form. we finally obtain a formula for $\simp_n(s,t)$. \begin{corollary} %\begin{equation} \[ \simp_n(s,t) = -f_n^{\langle -1 \rangle}(s,t) + (-1)^{n-1} + (-st)^{n-1} \qquad (n \ge 4). \] %\end{equation} \end{corollary} %\begin{rem} %Let %\[ %f(x,t) = \sum_{n \geq 0} A_n(x) \frac{t^n}{n!} %= \frac{1-t}{e^{(1-t)x} - t} %\] %be the exponential generating function for the Eulerian polynomials $A_n(x)$. %Then %\[ %f(x,t) = \frac{(1-t)e^{(t-1)x}}{1-te^{(t-1)x}} %=\sum_{j \geq 0}t^j(1-t)e^{(j+1)(t-1)x}. %\] % %Hence, the ordinary %generating function for the Eulerian polynomials $A_n(x)$ is given %by %\[ %g(x,t)=\sum_{n\geq0}A_n(x)t^n %=\sum\limits_{j\geq0}\frac{t^j(1-t)}{(1-(j+1)(t-1)x)}. %\] %\end{rem} %%%%%%%%%%%%%%%%%%%%%%%%% \section*{Acknowledgments} The authors thank Mathilde Bouvel and an anonymous referee for useful comments. RMA thanks the Institute for Advanced Studies, Jerusalem, for its hospitality during part of the work on this paper. Work of RMA was partially supported bu an MIT-Israel MISTI grant. \begin{thebibliography}{99} \bibitem{AA} M.\ H.\ Albert and M.\ D.\ Atkinson, {\em Simple permutations and pattern restricted permutations}, Discrete Math.\ {\bf 300} (2005) 1--15. \bibitem{AAK} M.\ H.\ Albert, M.\ D.\ Atkinson and M.\ Klazar, {\em The enumeration of simple permutations}, J.\ Integer Sequences {\bf 6} (2003), Article 03.4.4. \bibitem{A.S} M.\ D.\ Atkinson and T.\ Stitt, {\em Restricted permutations and the wreath product}, Discrete Math.\ {\bf 259} (2002) 19--36. \bibitem{Branden} P.\ Br\"and\'en, {\em Actions on permutations and unimodality of descent polynomials}, European J.\ Combin.\ {\bf 29}, (2008) 514--531. \bibitem{B.H.V.} R.\ Brignall, S.\ Huczynska and V.\ Vatter, {\em Simple permutations and algebraic generating functions}, J.\ Combinat.\ Theory, Series A {\bf 115}, (2008), 423--441, \bibitem{CRS} L.\ Carlitz, D.\ P.\ Roselle and R.\ A.\ Scoville, {\em Permutations and sequences with repetitions by number of increases}, J.\ Combinat.\ Theory {\bf 1} (1966), 350--374. \bibitem{F.S} D.\ Foata and M.-P.\ Sch\"utzenberger, {\em Th\`eorie g\`eom\`etriques des polyn\^{o}mes Eul\`eriens}, Lecture notes in Math., Vol.\ 138, Springer-Verlag, Berlin, (1970). \bibitem{F.St} D.\ Foata and V.\ Strehl, {\em Rearrangements of the symmetric group and enumerative properties of the tangent and secant numbers}, Math.\ Z.\ {\bf 137} (1974), 257--264. \bibitem{F.L.Z.} S.\ Fu, Z.\ Lin and J.\ Zeng, {\em Two new unimodal descent polynomials}, arXiv:1507.05184v1 [math.CO]. \bibitem{Lin} Z.\ Lin, {\em Proof of Gessel's $\gamma$-positivity conjecture}, Electronic J.\ Combinat.\ {\bf 23} (2016), \#P3.15. \bibitem{P} T.\ K.\ Petersen, {\em Two sided Eulerian Numbers via balls in boxes}, Math.\ Mag.\ {\bf 86} (2013) 159--176. \bibitem{Pet Book} T.\ K.\ Petersen, {\em Eulerian numbers}, Birkhauser, Basel, (2015). \bibitem{S.O} L.\ Shapiro, W.-J.\ Woan and S.\ Getu, {\em Runs, slides, and moments}, SIAM J.\ Algebraic Discrete Methods {\bf 4} (1983), 459--466. \bibitem{Vatter} V.\ Vatter, {\em Permutation classes}, in: Handbook of Combinatorial Enumeration (M.\ Bona, ed.), CRC Press (2015), pp.\ 753--833. \bibitem{V} M.\ Visontai, {\em Some remarks on the joint distribution of descents and inverse descents}, Electronic J.\ Combinat.\ {\bf 20} (2013), \#P52. \bibitem{W} J.\ West, {\em Generating trees and the Catalan and Schr\"oder numbers}, Discrete Math.\ {\bf 146} (1995), 247--262. \bibitem{Z} D.\ Zeilberger, {\em A one-line high school proof of the unimodality of the Gaussian polynomials $\binom{n}{k}_q$ for $k<20$}, in: D.\ Stanton (Ed.), $q$-Series and Partitions, Minneapolis, MN, (1988), 67-72. \end{thebibliography} \end{document}