The generating function of two-stack sortable permutations by descents is real-rooted
Petter Br�nd\'en
B{\'o}na has conjectured that, for fixed $n \geq 0$ and $t \geq 1$, the generating function of $t$-stack sortable permutations of length $n$ by descents is real-rooted. The conjecture is known to be true for $t=1$ and $t=n-1$. Here we prove it for $t=2$.
twostack.tex
% LaTeX file for a 10 page document
\documentclass[11pt,reqno,a4paper]{amsart}
\pagenumbering{arabic}

%\usepackage{showkeys}

\addtolength{\textheight}{-4mm}
\topmargin6mm


\title[Two-stack sortable permutations by descents]{The generating function 
of two-stack sortable permutations by 
descents is real-rooted}


\author{Petter Br�nd\'en}
\address{Matematik,
  Chalmers tekniska h\"ogskola och G\"oteborgs universitet,\linebreak
  S-412~96  G\"oteborg, Sweden}
\email{branden@math.chalmers.se}
%\thanks{thanks}
%\keywords{keywords}
%\subjclass{Primary: subject; Secondary: subject}
\date{\today}


\usepackage[english]{babel}
\usepackage{amsmath}
\usepackage{amsthm,amssymb,latexsym}
\usepackage{t1enc}
%\usepackage{fancyheadings}
\usepackage{epic}
\usepackage{eepic}
%\usepackage{xypic}
\usepackage{mathrsfs}


\newtheorem{proposition}{Proposition}
\newtheorem{lemma}[proposition]{Lemma}
\newtheorem{corollary}[proposition]{Corollary}
\newtheorem{theorem}[proposition]{Theorem}
\newtheorem{conjecture}[proposition]{Conjecture}
\theoremstyle{definition}
\newtheorem{definition}[proposition]{Definition}
\newtheorem{example}[proposition]{Example}
\newtheorem{remark}[proposition]{Remark}

\newcommand{\N}{\mathbb{N}}
\newcommand{\om}{\omega}
\newcommand{\ii}{\mbox{\em\small~in~}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Pos}{\mathbb{P}}
\newcommand{\J}{\mathcal{L}}
\newcommand{\Four}{\mathcal{L}_{\phi}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\bru}{<_w}
\newcommand{\lbru}{\leq_w}
\newcommand{\inter}{\mathscr{I}}
\newcommand{\sym}{\mathcal{S}}
\newcommand{\In}{\mathcal{I}}
\newcommand{\CP}{\Delta (\mathfrak{C}_n)}
\newcommand{\e}{\varepsilon}
\newcommand{\zB}{\zeta_B}
\newcommand{\muB}{\mu_B}
\newcommand{\one}{\hat{1}}
\newcommand{\zero}{\hat{0}}
\newcommand{\Al}{\mathscr{A}}
\newcommand{\Pa}{\mathcal{P}}
\newcommand{\Ps}{\mathfrak{P}}
\newcommand{\lep}{<_P}
\newcommand{\V}{\mathcal{V}}
\newcommand{\W}{\mathcal{W}}

\def\ch#1,#2,{\binom#1#2}
\def\hy#1,#2,#3,#4,{{}_2F_1\left(#1,#2;#3;#4\right)}
\def\emm#1,{{\em #1}}
\def\ba#1,{\overline{#1}}
\newcommand\mps[1]{\marginpar{\small\sf#1}}

\def\gen#1,{\langle #1 \rangle}
\def\geno#1,{\langle #1 \rangle_{\infty}}

%\renewcommand{\theenumi}{\upshape (\roman{enumi})}


\def\newop#1{\expandafter\def\csname #1\endcsname{\mathop{\rm
#1}\nolimits}}

\newop{span}
\newop{min}
\newop{max}
\newop{deg}
\newop{des}
\newop{Con}
\newop{Ann}
\newop{dim}
\newop{Int}
\newop{Im}
\newop{ker}
\newop{mult}
\newop{rank}
\newop{sign}
\newop{sgn}
\newop{TrCl}
\newop{inf}

\usepackage{graphicx}



\begin{document}
\nocite{*}\bibliographystyle{plain}
%\setcounter{page}{13}
\maketitle
\thispagestyle{empty}
\begin{abstract}
B{\'o}na has conjectured that, for fixed $n \geq 0$ and 
$t \geq 1$, the generating function of $t$-stack sortable permutations of 
length $n$ by descents is real-rooted. The conjecture is known to be true for 
$t=1$ and $t=n-1$. Here we prove it for $t=2$.   
\end{abstract}
\section{Introduction}
Let $W_t(n,k)$ be the number of $t$-stack sortable permutations in the 
symmetric group, $\sym_n$, with $k$ descents. Recently, B{\'o}na 
\cite{bona2,bona1} 
showed that 
for fixed $n$ and $t$ the numbers $W_t(n,k)$ form a unimodal sequence.  
Let $W_{n,t}(x)= \sum_{k=0}^{n-1}W_t(n,k)x^k$. 
A sufficient condition on a nonnegative sequence to be unimodal is that the 
corresponding polynomial is real-rooted. 
When $t=n-1$ and $t=1$ we get the 
Eulerian and the Narayana polynomials respectively. These 
are known to be real-rooted and B\'{o}na conjectures that the same is true 
for general $t$. In what follows we will prove the conjecture for 
$t=2$. 

Let $W$ be the set of finite words on $\N$ without repetitions. 
If $w$ is any nonempty word we may write 
it as the concatenation $w=LnR$ where $n$ is the greatest letter of $w$ and 
$L$ and $R$ are the subwords to the left and right of $n$ respectively. 
The stack-sorting operation $s : W \rightarrow W$ may be defined recursively 
by 
$$
s(w) = \begin{cases}
w, \mbox{ if $w$ is the empty word,} \\
s(L)s(R)n, \mbox{ if } w=LnR \mbox{ is nonempty.}
\end{cases}
$$
The {\em stack sortable} permutations in  
$\sym_n$ are the permutations which are mapped by $s$ to the identity 
permutation. Similarly, a permutation is called {\em $t$-stack sortable} 
if $s^t(\pi)$ is the identity permutation. 
\section{Stack sortable permutations and Jacobi polynomials} 
The number of stack sortable permutations of length $n$ with $k$ descents 
are known \cite{simion} to be the famous Narayana numbers
\cite{stanley2,sulanke}
$$
W_1(n,k)=\frac 1 n \binom n k \binom n {k+1}.
$$
The Narayana polynomials $W_{n,1}(x)$ are known to have real zeros. A 
simple proof of this fact is obtained by expressing $W_{n,1}(x)$ in terms 
of Jacobi polynomials. Recall the definition of the 
{\em hypergeometric function} $_2F_1$: 
$$
\hy a,b,c,z, = \sum_{n=0}^\infty \frac{(a)_n(b)_nz^n}{(c)_n n!},
$$
where $(\alpha)_0=1$ and $(\alpha)_n=\alpha(\alpha+1)\cdots (\alpha+n-1)$ 
when $n \geq 1$. The Jacobi polynomial $P^{(\alpha,\beta)}_n(x)$ can 
be expressed in the following two ways \cite[Page 254]{rainville}:
\begin{equation}\label{ulv1}
P^{(\alpha,\beta)}_n(x)=\frac {(1+\alpha)_n}{n!} \hy -n,1+\alpha+\beta+n,1+\alpha,\frac{1-x}2,,
\end{equation}
\begin{equation}\label{ulv2}
P^{(\alpha,\beta)}_n(x)=\frac{(1+\alpha)_n}{n!}\left(\frac{x+1}2\right)^n \hy -n,-\beta-n, 
1+\alpha,\frac{x-1}{x+1},.
\end{equation}
Rewriting $W_1(n+1,k)$ we end up with  
$$
W_{n+1,1}(x) = \hy -n,-n-1,2,x,,
$$ 
which by \eqref{ulv2} gives 
\begin{equation*}
W_{n+1,1}(x) = \frac{1}{n+1}(1-x)^nP_n^{(1,1)}\left(\frac{1+x}{1-x}\right).
\end{equation*}       
Since the Jacobi polynomials 
are orthogonal when $\alpha,\beta>-1$ we know that $W_{n,1}(x)$ is real- 
and simple-rooted and 
that the zeros of $W_{n,1}(x)$ strictly interlace the zeros of $W_{n+1,1}(x)$, 
that is, $\{W_{n+1,1}(x)\}_{n=0}^{\infty}$ form a {\em Sturm sequence}. 

The numbers $W_2(n,k)$ are surprisingly hard to determine despite of 
their compact and  simple form. It was recently shown that 
$$
W_2(n,k)= \frac {(n+k)!(2n-k-1)!}{(k+1)!(n-k)!(2k+1)!(2n-2k-1)!}.
$$
See \cite{bousquet,gire,gouldenwest,jacquard} for proofs and more 
information on $2$-stack sortable permutations. 

A sequence of real numbers $\Gamma = \{\gamma_k\}_{k=0}^n$ is called 
an {\em $n$-sequence (of the first kind)} if for any real-rooted polynomial 
$f= a_0 + a_1x + \cdots + a_nx^n$ of degree at most $n$ the polynomial 
$\Gamma(f) := a_0\gamma_0 + a_1\gamma_1x + \cdots + a_n\gamma_nx^n$ is 
real-rooted. There is a simple algebraic characterisation of $n$-sequences 
\cite{mult}:
\begin{theorem}
Let $\Gamma=\{\gamma_k\}_{k=0}^n$ be a sequence of real numbers. Then 
$\Gamma$ is an $n$-sequence of the first kind if and only if 
$\Gamma[(x+1)^n]$ is real-rooted with all its zeros of the same sign. 
\end{theorem}
%\mps{holds for other $f \neq (x+1)^n$}
We need the following lemma: 
\begin{lemma}\label{factor}
Let $n$ be a positive integer and $r$ a non-negative real number. Then  
$\Gamma=\{\binom{-n-r}k\}_{k=0}^n$ is an $n$-sequence. 
\end{lemma}
\begin{proof}
Let $r > 0$. Then    
\begin{eqnarray*}
\Gamma[(x+1)^n] &=& \sum_{k=0}^n\binom {-n-r} k \binom n k x^k \\
                &=& \hy -n,n+r,1,x,   \\
                &=& P^{(0,r-1)}_n(1-2x),
\end{eqnarray*}
where the last equality follows from \eqref{ulv1}.
Since the Jacobi polynomials 
are known to have all their zeros in $[-1,1]$ when $\alpha , \beta> -1$ 
we have that $\Gamma[(x+1)^n]$ has all its zeros in $[0,1]$. The case 
$r=0$ follows by continuity when we let $r$ tend to zero from above.  
\end{proof}
From the case $r=0$ in Lemma \ref{factor} and the identity
$$
\sum_{k=0}^n\binom{2n-k-1}{n-1}\binom n k x^k= (-1)^n\sum_{k=0}^n\binom{-n}{k}
\binom n k (-x)^{n-k}, 
$$ 
it follows that $\binom{2n-k-1}{n-1}$ is an $n$-sequence.
\begin{theorem}
For all $n \geq 0$ the polynomial $W_{2,n}(x)$, which records $2$-stack 
sortable permutations by descents, is real-rooted.
\end{theorem}
%\mps{simple roots}
\begin{proof}
We may write $W_2(n,k)$ as 
$$
W_2(n,k) = \frac{\binom {2n-k-1}{n-1} \binom{n+k}{n-1} \binom{2n}{2k+1}}
                {n^2\binom{2n}{n}}.
$$
A well known result on real-rooted polynomials reads as follows: If 
$\sum_i a_i x^i$ is a polynomial having only real non-positive zeros then 
so is the polynomial $\sum_ia_{ki}x^i$, where $k$ is any positive integer. 
For a proof see \cite[Theorem 3.5.4]{brenti}. Applying this result to 
the polynomial $x(1+x)^{2n}$ we see that $\sum_k\binom{2n}{2k+1}x^k$ is 
real-rooted. Now, 
$$
\sum_{k=0}^{n-1}\binom{n+k}{n-1} \binom{2n}{2k+1}x^k =
\sum_{k=0}^{n-1}\binom {2n-k-1}{n-1}\binom{2n}{2k+1}x^{n-1-k},
$$
which by the discussion after Lemma \ref{factor} is real-rooted. 
Another application 
of Lemma \ref{factor} gives that $W_{n,2}(x)$ is real-rooted. 
\end{proof}
 

\bibliography{twostack}
 
\end{document}







twostack.bbl
\begin{thebibliography}{10}

\bibitem{bona2}
Mikl{\'o}s B{\'o}na.
\newblock Corrigendum: ``{S}ymmetry and unimodality in {$t$}-stack sortable
  permutations'' [{J}.\ {C}ombin.\ {T}heory {S}er.\ {A} {\bf 98} (2002), no. 1,
  201--209; 1897934].
\newblock {\em J. Combin. Theory Ser. A}, 99(1):191--194, 2002.

\bibitem{bona1}
Mikl{\'o}s B{\'o}na.
\newblock Symmetry and unimodality in {$t$}-stack sortable permutations.
\newblock {\em J. Combin. Theory Ser. A}, 98(1):201--209, 2002.

\bibitem{bousquet}
M.~Bousquet-M{\'e}lou.
\newblock Multi-statistic enumeration of two-stack sortable permutations.
\newblock {\em Electron. J. Combin.}, 5(1):Research Paper 21, 12 pp.
  (electronic), 1998.

\bibitem{brenti}
F.~Brenti.
\newblock Unimodal, log-concave and {P}\'olya frequency sequences in
  combinatorics.
\newblock {\em Mem. Amer. Math. Soc.}, 81(413):viii+106, 1989.

\bibitem{mult}
T.~Craven and G.~Csordas.
\newblock Multiplier sequences for fields.
\newblock {\em Illinois J. Math.}, 21(4):801--817, 1977.

\bibitem{gire}
S.~Dulucq, S.~Gire, and O.~Guibert.
\newblock A combinatorial proof of {J}. {W}est's conjecture.
\newblock {\em Discrete Math.}, 187(1-3):71--96, 1998.

\bibitem{gouldenwest}
I.~P. Goulden and J.~West.
\newblock Raney paths and a combinatorial relationship between rooted
  nonseparable planar maps and two-stack-sortable permutations.
\newblock {\em J. Combin. Theory Ser. A}, 75(2):220--242, 1996.

\bibitem{jacquard}
B.~Jacquard and G.~Schaeffer.
\newblock A bijective census of nonseparable planar maps.
\newblock {\em J. Combin. Theory Ser. A}, 83(1):1--20, 1998.

\bibitem{rainville}
E.~D. Rainville.
\newblock {\em Special functions}.
\newblock The Macmillan Co., New York, 1960.

\bibitem{simion}
R.~Simion.
\newblock Combinatorial statistics on noncrossing partitions.
\newblock {\em J. Combin. Theory Ser. A}, 66(2):270--301, 1994.

\bibitem{stanley2}
Richard~P. Stanley.
\newblock {\em Enumerative combinatorics. {V}ol. 2}, volume~62 of {\em
  Cambridge Studies in Advanced Mathematics}.
\newblock Cambridge University Press, Cambridge, 1999.

\bibitem{sulanke}
R.~A. Sulanke.
\newblock The {N}arayana distribution.
\newblock {\em J. Statist. Plann. Inference}, 101(1-2):311--326, 2002.
\newblock Special issue on lattice path combinatorics and applications (Vienna,
  1998).

\end{thebibliography}
