\documentclass[19pt]{beamer}
%\usepackage{cctbase,ccmap}
\usepackage{graphicx}
%\usepackage{maplestd2e}
\usepackage{epstopdf}
\usepackage{float}
\usepackage{bbm}
\usepackage{multirow,multicol,subfigure}
\usepackage{makecell}
\usepackage{caption}
\usepackage{amsmath,cite,colordvi,xcolor}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{tikz}
\usepackage{float}
\usepackage{subfigure}

%\usepackage{times}
%\usepackage{mathptmx}
\usepackage{CJK} %使用ctex套装编辑时请选择
%\usepackage[UTF8]{ctex} %使用texlive 套装编辑时请选择 PDFLaTeX 编译，并请编译两次以保证正确显示目录
\mode<presentation>
{
%dresden
%Malmoe
%Goettingen
%Montpellier
  \usetheme{Madrid}
  %\usecolortheme{seahorse}
  \def\hilite<#1>{%
\temporal<#1>{\color{blue!35}}{\color{magenta}}%
{\color{blue!75}}}
\def\hidark<#1>{%
\temporal<#1>{\color{black!35}}{\color{magenta}}%
{\color{black}}}

% \usecolortheme{beetle} \usecolortheme{dove} \usecolortheme{fly} \usecolortheme{seagull}
% \usecolortheme{dolphin} \usecolortheme{lily} \usecolortheme{orchid} \usecolortheme{rose} \usecolortheme{seahorse}
  % \usetheme{Darmstadt} \usetheme{JuanLesPins} \usetheme{Madrid} \usetheme{Montpellier} \usetheme{Pittsburgh} \usetheme{Rochester} \usetheme{Singapore}

  \newtheorem{thm}{Theorem}[section]
\newtheorem{defi}[thm]{Definition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{ex}{Exersise}[section]
\newtheorem{exam}[thm]{Example}

\allowdisplaybreaks

\setbeamercovered{transparent}
}
\setbeamertemplate{caption}[numbered]
\setbeamertemplate{frametitle}[smoothtree theme]
\setbeamertemplate{blocks}[rounded][shadow=true]
%\setitemize[1]{itemsep=8pt}
%\setenumerate[1]{itemsep=8pt}


\setlength{\baselineskip}{20pt}
\renewcommand{\baselinestretch}{1.5}

\renewcommand{\thefootnote}{\fnsymbol{footnote}}
%\setlength{\itemsep}{10pt}
%\setlength{\parsep}{5pt}
%\setlength{\itemsep}{2pt plus3pt}

\def\pf{\noindent {\it Proof.} }
%\renewcommand{\familydefault}{<\rmdefault>}
%\renewcommand{\baselinestretch}{1}
\usefonttheme{serif}
%\def\mathfamilydefault{rmdefault}
%\rmfamily

\begin{document}
\begin{CJK*}{GBK}{kai} %使用ctex 套装编辑时请选择

\title[Context-free Grammars ]
{Context-free Grammars for \\ Combinatorial Enumeration}
\author[Bill Chen]{Bill Chen}
\institute[China]{
{\normalsize Center for Applied Mathematics\\[5pt]
Tianjin University\\[5pt]
Email: chenyc@tju.edu.cn }}

\date[June~27,~2021]{June~27,~2021\\[10pt]
In Celebration of the Retirement of Professor Yeong-Nan Yeh
}
%\titlegraphic{\includegraphics[height=2cm]{w.1}}



\frame{\titlepage}






{\footnotesize \begin{frame}
\frametitle{Outline}
\tableofcontents[hideallsubsections]
\end{frame}}




\section{What is a Context-Free Grammar?}

\begin{frame}

\begin{center}
{\Large \color{blue} \bf I. What is a Context-Free Grammar?}
\end{center}
\end{frame}

\begin{frame}\frametitle{What is a context-free grammar?}

The grammars we will be talking about are
exactly those as in computer science, that is,
a set of substitution rules over an alphabet.

For the purpose of combinatorial enumeration,
we treat the alphabet as a set of commuting
variables.  The key idea is that the notion of
a context-free grammar is closely connected to the
notion of a derivative for which the
Leibniz formula holds. The production rules
are supposed to be applied to Laurent polynomials
over a set of variables.
\end{frame}

\begin{frame}
Let us give some simple examples to illustrate the
idea. Let $V=\{  a,x\}$ be a set of variable, and let
\[ G= \{ a \rightarrow ax , \quad x \rightarrow  x  \}. \]
be a context-free grammar, and let $D$ be the formal
derivative with respect to the grammar $G$.

A formal derivative can be formulated as a
differential operator
\[ D =
  a x { \partial \over \partial a} +   x    {\partial \over \partial x}.\]

The Leibniz formula:
\[ D^n (fg) = \sum_{k=0}^n
{n \choose k} D^{k} (f) D^{n-k} (g). \]
\end{frame}


\begin{frame}
It should be noted that
the above expression of a formal derivative
in terms of a differential operator
can be employed in the implementation in Maple
for the computation of the action of $D$ on
a Laurent polynomial $f(a, x)$.

A context-free grammar has two facets. One is
combinatorial, and the other is computational.
\end{frame}

\begin{frame}\frametitle{What is a context-free grammar?}
{\small For the above grammar $G =
  \{ a \rightarrow ax , \quad x \rightarrow  x   \}
 $, in combinatorial
terms  one can easily argue
that
\[ D^n(a) =  a \sum_{k=1}^n S(n,k) x^k, \]
where $S(n,k)$ are the Stirling numbers of the second kind.
 \begin{align*}
D(a) &= ax, \\
 D^2 (a) &= D(ax) = D(a) x + a D(x) = ax+ a x^2,\\
 D^3(a) &= D(ax) + D(a) x^2 +  a D(x^2), \\
  D(x^2) &= 2x D(x) = 2x^2.
\end{align*}
Thus,
\[    D^3(a) = a x + a x^2  + a 2x^2   +a x^3   = a x +3a x^2  +a x^3 . \]
 }
\end{frame}

\begin{frame}\frametitle{Remarks}
{\small \begin{itemize}
\item[] {\bf Remark 1.} One feature of a context-free grammar
is that it makes use of many variables, like $x$ and
$y$ in this case, but we use only one derivative $D$ involving many variables and we   consider
the generating function only in one variable.
It turns out that  many variables may work better than only one variable. In some sense, these
variables may be viewed as parameters.

\item[]{\bf Remark 2.} The variables of a grammar
can be associated as tags or marks
 with a combinatorial structure.  As a result, a grammar can be employed to study statistics of combinatorial objects
such as permutations, partitions and trees.
\end{itemize}}

\end{frame}

\begin{frame}
Since $D$ is a derivative, by the
Leibniz formula and the relation
\[ D^{m+n} = D^m D^n,\]
 we obtain the convolution formula for the
Stirling numbers of the second kind, due to Verde-Star (1988), see Chen (1993):
For $m,n\geq 1$,
\[ S(m+n,k)  = \sum_{i+j\geq k}
{m \choose j} i^{m-j} S(n,i) S(j, k-i).\]



\footnotesize {
{\color{blue}
\begin{thebibliography}{1}
\bibitem{Verde-Star}
L. Verde-Star, Interpolation and combinatorial functions, Stud. Appl. Math.,
 79 (1988), 65-92.
\bibitem{Chen-1993}
W.Y.C. Chen, Context-free grammars, differential operators and
formal power series, Theoret. Comput. Sci. 117 (1993), 113-129.
\end{thebibliography}}}




\end{frame}


\begin{frame} \frametitle{Spivey's Bell
number formula}

This relation implies the following
identity on Bell numbers,
which has been called Spivey's Bell
number formula (Spivey, 2008).
\[ B_{n+m} = \sum_{j=0}^m \sum_{k=0}^n
   k^{m-j} S(n,k) {m \choose j} B_j .\]

I came across to the work of Verde-Star, largely
because I met him at MIT during his visit to
Gian-Carlo Rota, while I was a student.


\vskip 3mm
\footnotesize {
{\color{blue}
\begin{thebibliography}{1}
\bibitem{Spivey}
M. Spivey, A generalized recurrence for Bell numbers,
    J. Integer Seq., 11 (2008), Article 08.2.5.
\end{thebibliography}}}



\end{frame}



\begin{frame}\frametitle{Connection to the symbolic method}
The key to the symbolic method is to treat a sequence
$a_0, a_1, a_2, \ldots$ like $a^0, a^1, a^2, \ldots$. Rota made it rigorous in light of the idea of
linear functionals.

 Grammars can be used to put the
classic argument 
(or the umbral calculus for the Bell polynomials)
 on a firm foundation, see Johnson:


\vskip 3mm
\footnotesize {
{\color{blue}
\begin{thebibliography}{1}
\bibitem{Johnson}
W.P. Johnson, The curious history of Fa\`a di Bruno's formula, Amer. Math. Monthly 109 (2002) 217-234.
\end{thebibliography}}}

\end{frame}

\begin{frame}\frametitle{Connection to the symbolic method}
Let $G$ be the grammar
\[  G=\{f\rightarrow f, a_i \rightarrow a_{i+1} \, | \, i =0, 1, 2, \ldots \} .\]
Let $D$ denote the derivative with respect to the
grammar $G$. Bear in mind that the $a_i$ are considered
as variables.  Clearly, we have
\[ D(f^{-1}) = -f^{-1}.\]

\end{frame}

\begin{frame}
Assume that
\[ b_n = \sum_{k=0}^n {n \choose k} a_k,\]
for $n\geq 0$. Then the above relation can be
recast as
\[ b_n = f^{-1} D^n(fa_{0}).\]
Consequently,
\[ a_n = D^n(a_0) = D^n(f^{-1} fa_0),
\]
which equals
\[ \sum_{k=0}^n (-1)^{n-k} {n\choose k} f^{-1} D^k(fa_0) =
\sum_{k=0}^n (-1)^{n-k} {n \choose k} a_k. \]

\end{frame}

\section{The Dumont Grammar for the Eulerian Numbers}


\begin{frame}

\begin{center}
{\Large \color{blue} \bf II. The Dumont Grammar for

the Eulerian Numbers}
\end{center}
\end{frame}

\begin{frame}\frametitle{The Eulerian numbers}
 \begin{defi}
 For $1\leq k \leq n$, the Eulerian numbers $A(n,k)$ are defined to be
the number of permutations of $[n]=\{1, 2, \ldots, n\}$ with $k$ descents,
where we assume that the last position is always a descent.
 For $n=0$, we define
$A(0,0)=1$.
 \end{defi}
 The Eulerian numbers are often denoted
by $\left\langle {n \atop k} \right\rangle $.  For $n\geq 0$, the Eulerian polynomials
$A_n(x)$ are defined by $A_0(x)=1$ and for $n\geq 1$,
\begin{equation*}
A_n(x) = \sum_{\sigma\in S_n} x ^{\rm{des\,} (\sigma) } = \sum_{k=1}^n A(n,k)x^k,
\end{equation*}
where $\rm{des\,}(\sigma)$ denotes the number
of descents of a permutation $\sigma$.

\end{frame}



\begin{frame}\frametitle{Dumont's grammar}

\noindent {\large\bf Dumont's Grammar.}
Dumont discovered the following grammar for the Eulerian polynomials $A_n(x)$:
\begin{equation*}
G=\{x\rightarrow xy, \quad y\rightarrow xy\}.
\end{equation*}


Let $D$ denote the derivative with respect to the
above grammar $G$. If we do not mind
the rigor in notation, for $n\geq 0$,
we use $A_n(x,y)$ to the denote the bivariate polynomial
$D^n(y)$, namely,
\begin{equation*}\label{A-n-D}
A_n(x,y) = D^n(y).
\end{equation*}
\end{frame}


\begin{frame}\frametitle{Example}
The first few values of $A_n(x,y)$ are given below
\begin{eqnarray*}
A_0(x,y) & = & y, \\
A_1(x,y) & = & xy, \\
A_2(x,y) & = & xy^2+x^2y, \\
A_3(x,y) & = & xy^3+4x^2y^2+x^3y, \\
A_4(x,y) & = & xy^4 + 11 x^2y^3 + 11 x^3 y^2 + x^4y,\\
A_5(x,y) & = & xy^5+ 26x^2y^4 +66x^3y^3 +26 x^4y^2 + x^5y, \\
A_6(x,y) & = & xy^6+57x^2y^5+302x^3y^4+ 302 x^4y^3 + 57 x^5y^2 + x^6y.
\end{eqnarray*}
\end{frame}

\begin{frame}\frametitle{The Dumont grammar for the Eulerian numbers}

 \begin{thm}[Dumont]
 For $n\geq 1$,
\begin{equation*} \label{A-n-x-y}
A_n(x,y) = \sum_{\sigma \in S_n} x^{\rm{des\,}(\sigma) }
                                y^{\rm{asc\,}(\sigma) },
\end{equation*}
where $\rm{asc\,}(\sigma)$ stands for the number
of ascents of $\sigma$ and we always assume that the first
position is an ascent. In other words, $i$ is an ascent
of $\sigma=\sigma_1\sigma_2\cdots \sigma_n$ if
$i=1$ or $\sigma_{i-1} < \sigma_i$.
\end{thm}
Since $A_0(x,y)=y$, the above theorem implies that for $n\geq 0$,
\begin{equation*}
 A_n(x) = A_n(x,y)|_{y=1}.
\end{equation*}
\end{frame}



\begin{frame}

It is not difficult to see that $A_n(x,y)$ can also be
expressed in terms of permutations in $S_n$.
For a permutation $\pi$ in $S_n$,
we give a labeling of $\pi$ as follows.
 For $0 \leq i \leq n$,
if $\pi_i<\pi_{i+1}$, we label $\pi_i$ by $x$;
if $\pi_i>\pi_{i+1}$, we label $\pi_i$ by $y$.
The weight of $\pi$ is defined as the product of the labels, that is,
\[
w(\pi)=x^{\mathrm{asc}(\pi) }y^{\mathrm{des}(\pi) },\]
where $\mathrm{asc}(\pi)$ denotes the number of ascents in $\pi$
and $\mathrm{des}(\pi)$ denotes the number of descents in $\pi$.  For $n\geq 1$,
it can be shown that the polynomial  $A_{n}(x,y)$
permits the following equivalent expression:
\begin{equation*}
A_{n}(x,y)=\sum_{\pi \in S_{n}}x^{\mathrm{asc}(\pi) }y^{\mathrm{des}(\pi) }.
\end{equation*}
\end{frame}

\begin{frame}\frametitle{Example of a grammatical labeling}

To illustrate the
relation between the  action of
the formal derivative $D$
 and the insertion of the element $n+1$ into a permutation on $[n]$,
 we give the following example. Let $n=6$ and $\pi=325641$.  The grammatical labeling of
   $\pi$ reads
\[\begin{array}{ccccccl}
&3&2&5&6&4&1\\[-5pt]
x&y&x&x&y&y&y,
\end{array}\]
where the element $0$ is made invisible.
If we insert $7$ after $5$, the resulting permutation and its grammatical labeling are given below,
\[\begin{array}{cccccccl}
 &3&2&5&7&6&4&1\\[-5pt]
x&y&x&x&y&y&y&y.
\end{array}\]

\end{frame}

\begin{frame}\frametitle{Example of a grammatical labeling}

Notice that the insertion of $7$ after $5$ corresponds to applying the rule $x\rightarrow xy$ to the label $x$ associated with $5$. We have a similar situation when the new element is inserted after an element labeled by $y$.
Hence  the action of the formal derivative $D$ on the set of weights of   permutations in $S_{n}$ gives the set of weights of permutations in $S_{n+1}$. This yields a
grammatical expression for $A_{n}(x,y)$.

\end{frame}

\begin{frame}\frametitle{D. Dumont}

 Dumont made ingenious discoveries of
 grammars in connection with
 classical problems on permutations and trees.
 These grammars take astonishingly simple forms.
 As far as enumeration is concerned, a
 grammar furnishes sufficient information.
 In other words, Dumont found remarkable
 generation
 rules for several combinatorial objects.

\end{frame}



\begin{frame}\frametitle{D. Dumont}

 I was thrilled by his results. Out of great admiration, I was
 tempted to invite him to visit China.
  He kindly accepted the invitation in 2014, but it was
 sad that due to the illness, he could not make it.
 It was a great regret that I could not have the honor
 of meeting him. The following paper was dedicated to
 his memory.

\vskip 3mm
\footnotesize {
{\color{blue}
\begin{thebibliography}{1}
\bibitem{Chen-Fu=2017}
 W.Y.C. Chen and A.M. Fu,
Context-free grammars for permutations and increasing trees,
Adv. in Appl. Math. 82 (2017) 58-82.
\end{thebibliography}}}



 \end{frame}

 \begin{frame}\frametitle{D. Dumont}

D. Foata was in contact with Dumont regarding
his plan to visit China, and   Professor Foata was so kind as
to inform me that Professor Dumont could no longer travel or   possibly
 send
 out a message. An account of Dumont's work on grammars
 was given by Foata:



\vskip 3mm
\footnotesize {
{\color{blue}
\begin{thebibliography}{1}
\bibitem{Chen-Fu=2017}
D. Foata, Dominique Dumont (1947–2016), S\'em. Lothar. Combin. 76 ([2016-2017]) Art. B76z.
\end{thebibliography}}}

\end{frame}

\subsection{A grammatical calculus for the
Eulerian polynomials}

\begin{frame}\frametitle{A grammatical calculus for the
Eulerian polynomials}
For the grammar $G$, we have
\begin{equation*} \label{D-x-1}
D(y^{-1} ) = -x y^{-1}.
\end{equation*}

The following observation in Chen and Fu (2017)
  is instrumental
for deriving relations of the Eulerian polynomials.


For $n\geq 0$,
\[ \tag{*}
D^n(xy^{-1} ) = x  y^{-1} (y-x)^n.
\]

For $n=1$, we have
\[  \tag{**}
 D(x^{-1}y)=x^{-1}y (x-y).
 \]
Since $D(x-y)=0$, we get (*).

\end{frame}

\begin{frame}\frametitle{A grammatical calculus for the
Eulerian polynomials}

The following
generating function of $A_n(x)$ is well-known.

\begin{thm}
\begin{equation*}
\label{Gen-A-n-x}
\sum_{n\geq 0} A_n(x) {t^n \over n!} = {1-x\over 1-xe^{(1-x)t}}.
\end{equation*}
\end{thm}

Let us demonstrate that
the above relation can be deduced
by employing the grammatical calculus.

\end{frame}

\begin{frame}\frametitle{Grammatical calculus for the
Eulerian polynomials}
For a Laurent polynomial $f$ in $x$ and $y$, define
\begin{equation*} \label{Gen-d}
{\rm Gen}(f, t) = \sum_{n\geq 0} D^n(f) {t^n \over n!}.
\end{equation*}
If $g$ is also a Laurent polynomial in $x$ and $y$,
then we have the multiplicative property
(or the homomorphism)
\begin{equation*} \label{Gen-fg}
{\rm Gen}(fg, t) = {\rm Gen}(f, t)\, {\rm Gen}(g, t) .
\tag{*}
\end{equation*}
Noting that
 $A_n(x)=D^n(y)|_{y=1}$ for $n\geq 0$, we are prompted to compute the generating function ${\rm Gen}(y, t)$.
It follows from (*) that
\begin{equation*}
{\rm Gen}(y, t) = {1 \over {\rm Gen}(y^{-1},t)}.
\end{equation*}
\end{frame}


\begin{frame}\frametitle{A grammatical calculus for the
Eulerian polynomials}
\begin{thm}[Chen-Fu, 2017] We have
\begin{equation*} \label{Gen-y-1}
{\rm Gen}(y^{-1},t) = {1 - xy^{-1} e^{(y-x)t} \over y-x}.
\end{equation*}
\end{thm}

{\small {\noindent \it Proof.} Since $D(y^{-1})= -xy^{-1}$, we have
\begin{equation*}
{\rm Gen}(y^{-1},t) = \sum_{n\geq 0}
D^n(y^{-1}){t^n \over n!}
= y^{-1} - \sum_{n\geq 1} D^{n-1} (xy^{-1}) {t^n \over n!}.
\end{equation*}
Recalling that $D^{n-1}(xy^{-1})=xy^{-1}(y-x)^{n-1}$ for $n\geq 1$, we get
\begin{eqnarray*}
{\rm Gen} (y^{-1}) & = & y^{-1} -
\sum_{n\geq 1}  xy^{-1}(y-x)^{n-1}{t^n \over n!} \\[5pt]
& = & y^{-1} -
   {xy^{-1} \over y-x} \left( e^{(y-x)t} -1 \right) \\[9pt]
& = & {1 - xy^{-1} e^{(y-x)t} \over y-x}.
\end{eqnarray*}
 } \qed
\end{frame}

\begin{frame}\frametitle{A grammatical calculus for the
Eulerian polynomials}
Therefore,
\begin{equation*}\label{Gen-y}
{\rm Gen}(y ,t) = { y-x \over 1 - xy^{-1} e^{(y-x)t}}.
\end{equation*}
Setting $y=1$, we are led to the
generating function of $A_n(x)$.

It should be noted that the bivariate version of the Eulerian polynomials
was also investigated by Carlitz and ***.


\end{frame}


\begin{frame}\frametitle{Exterior peak of a permutation}
 Given a permutation $\pi=\pi_1\pi_2\cdots\pi_n$ on $[n]$,
an index is called an {\it exterior peak} if $\pi_1>\pi_2$
for $i= 1$ or $\pi_{i-1}<\pi_i>\pi_{i+1}$ for $i< i< n$.
Let $T(n,k)$ be the number of permutations on $[n]$ with $k$ exterior peaks and let
$$T_n(x)=\sum_{k\geq 0}T(n,k)x^k .$$

\begin{thm} [Gessel] We have
$$\sum_{n=0}^{\infty}\frac{T_n(x)t^n}{n!}
=\frac{\sqrt{1-x}}{\sqrt{1-x}\cosh(t\sqrt{1-x})
-\sinh(t\sqrt{1-x})}.$$
\end{thm}

\end{frame}



\begin{frame}\frametitle{Proper double descents  of a permutation}
The number of proper double descents of a permutation
has been extensively studied. An index $i$ of
$\pi=\pi_1\pi_2\cdots\pi_n$ on $[n]$ is called a \textit{proper double descent} if
$3\leq i \leq n$ and $\pi_{i-2}>\pi_{i-1}>\pi$. Denote by $U(n,k)$ the number of
permutations on $[n]$ with $k$ proper double descents and let
$$U_n(y) =\sum_{k\geq 0}U(n,k)y^k .$$

\begin{thm}[Elizalde and Noy, Barry, Basset] We have
$$\sum_{n=0}^{\infty}U(n,0)\frac{t^n}{n!}=\frac{\sqrt{3}}{2}\frac{e^{t/2}}{\cos(\sqrt{3}t/2)+\pi/6} .$$
\end{thm}
\end{frame}

\begin{frame}\frametitle{Joint distribution}
To consider the joint distribution of the number of exterior peaks and the number
of proper double descents over permutations,   define $P_n(i,j)$ to be the number of permutations on $[n]$
with $i$ exterior peaks and $j$ proper double descents.
Let
$$P_n(x,y)=\sum_{i,j}P_n(i,j)x^iy^j$$
where $0\leq j\leq n-1$ and $2i+j\leq n$.
\end{frame}


\begin{frame}\frametitle{Joint distribution}
Fu (2018) found a context free grammar and a grammatical labeling of permutations to generate the polynomials
$P_n(x,y)$. Define the polynomials
$P_n(x,y,z,w)$ in four variables as
$$P_n(x,y,z,w)=\sum_{i,j}P_n(i,j)x^iy^jz^{i+1}w^{n-2i-j},$$
where $i$ and $j$ are in the same range as before.
Let $G$ be the grammar
\[ G=\{ x\rightarrow xy, \quad y \rightarrow xz ,\quad
    z \rightarrow zw, \quad w \rightarrow xz \}, \]
and let $D$ be the formal derivative with respect to $G$.

\end{frame}

\begin{frame}
 Fu (2018) proved that for $n \geq 0$,
\[ D^n(z)= P_n(x,y,z,w), \]
 and obtained the
 generating function for the joint distribution, which implies
the results of Gessel,
Elizalde-Noy, Barry and Basset.

\begin{thm}[Fu-2018]
\begin{align*}
&\sum_{n=0}^{\infty}P_n(x,y)\frac{t^n}{n!}=\\
&\frac{2\sqrt{(1+y)^2-4x}e^{t/2 \cdot (1-y+\sqrt{(1+y)^2-4x})}}
{1+y+\sqrt{(1+y)^2-4x}-(1+y-\sqrt{(1+y)^2-4x})e^{t\sqrt{(1+y)^2-4x}}} .
\end{align*}
\end{thm}

\vskip 3mm
\footnotesize {
{\color{blue}
\begin{thebibliography}{1}

\bibitem{Fu-2018}
 A.M. Fu, A context-free grammar for peaks and double descents of permutations, Adv. in Appl. Math. 100 (2018), 179-196.

\end{thebibliography}}}

\end{frame}



\section{The $\gamma$-Expansion of the Eulerian Polynomials}



\begin{frame}

\begin{center}
{\large \color{blue} \bf III. The $\gamma$-Expansion of

the Eulerian Polynomials}
\end{center}
\end{frame}

\begin{frame}\frametitle{The $\gamma$-expansion of the Eulerian Polynomials}

The following theorem is concerned with the celebrated gamma positivity of the Eulerian polynomials.

\begin{thm}[Foata and Sch\"utzenberger]
For $n\geq 1$,  $A_n(x)$ can be written as
\begin{equation*} \label{A-n-gamma}
   A_n(x) = \sum_{k=1}^{[(n+1)/2]}
       \gamma_{\,n,\,k\,}  x^k(1+x)^{n-2k+1}
\end{equation*}
with nonnegative coefficients $\gamma_{\,n,k}$.
\end{thm}

The above expression is
called the $\gamma$-expansion of $A_n(x)$.

\end{frame}

\begin{frame}\frametitle{The $\gamma$-expansion of the Eulerian Polynomials}
Remarkably, Foata and Sch\"utzenberger found
a combinatorial interpretation of the coefficients
$\gamma_{n,k}$.

\begin{thm}[Foata and Sch\"utzenberger] For $n\geq 1$ and $1 \leq k \leq [(n+1)/2]$,
 $\gamma_{n,k}$ equals
the number of permutations of $[n]$ with $k$ descents, but no double descents.
\end{thm}

By a change of the grammar $G$, the positivity
of the $\gamma$-expansion becomes transparent. {  This
beautiful observation is due to Ma, Ma and Yeh.}

\end{frame}

\begin{frame}\frametitle{The $\gamma$-expansion of the Eulerian Polynomials}
Let's see how it works.
Since
\begin{eqnarray*}
D(xy)& = & (x+y)xy, \\
D(x+y) & = & 2xy.
\end{eqnarray*}
If we treat $xy$ as a variable $u$ and $x+y$
as a variable $v$, then the of $D$ corresponds to
a new grammar
\begin{equation*}
H=\{ u \rightarrow uv, \quad v \rightarrow 2u.\}
\end{equation*}


For example, $A_1(x,y)=u$, $ A_2(x,y)=D(u) = uv=2xy(x+y),$
and
$ A_3(x,y)=D^2(u)=D(uv)=uv^2+2u^2=xy(x+y)^2+2x^2y^2.$



\end{frame}

\begin{frame}\frametitle{The $\gamma$-expansion of the Eulerian Polynomials}

We shall demonstrate that the grammar $H$ is vital to
provide a combinatorial explanation of the numbers $\gamma_{n,k}$,
which turns out to be in one-to-one correspondence with the
original interpretation of Foata and Sch\"utzenberger.

\end{frame}

\begin{frame}\frametitle{The $\gamma$-expansion of the Eulerian Polynomials}

\begin{thm}[Chen-Fu, 2021] For $n\geq 1$ and $1\leq k \leq [(n+1)/2]$,
the number $\gamma_{\,n,\,k}$
equals the number of 0-1-2 increasing plane trees
on $\{1, 2, \ldots, n\}$ with $k$ leaves.
\end{thm}


The above interpretation is equivalent to a formula
given by Han-Ma (2020) in terms of 0-1-2 increasing trees,
 which in turn is equivalent to a
known characterization in terms of increasing binary trees
not containing any single left children.

\end{frame}

\begin{frame}
 While the above
interpretation is merely a restatement of a known fact, it originates
 from the governing grammar and as will been seen
it offers a test ground for the study of
the trivariate second-order Eulerian
polynomials.



{\bf Remark.} For the above grammar $G=\{x\rightarrow xy, \; y\rightarrow xy\}$, the grammatical
labeling of a 0-1-2 increasing tree is given as
follows. For a 0-1-2 increasing tree $T$
 on $[n]$,
a leaf is labeled by $x$, a degree one vertex
is labeled by $y$ and a degree two vertex is labeled
by $1$. A 0-1-2 increasing tree $T'$ on $[n+1]$
can always be obtained from a 0-1-2 increasing
tree $T$ on $[n]$ by attaching the vertex
$n+1$ to $T$ as
a child of a leaf or a degree one vertex.
\end{frame}

\begin{frame}

Furthermore,
the grammar $H$ can be utilized to derive the
generating function of the  polynomials $\gamma_n(x)$, defined by
\begin{equation*}\label{gamma-p}
\gamma_{n}(x)=\sum_{k=1}^{[(n+1)/2]} \gamma_{n,k}x^k.
\end{equation*}

In view of the grammar $H$, the computation of
the polynomials $\gamma_n(x)$ is not much different
from that of the Andr\'e polynomials $E_n(x)$.


{ The $\gamma$ expansion of a polynomial whose
coefficients are symmetric can be better understood
in the framework of
 symmetric functions in  $x$ and $y$.
For the case of two variables $x$ and $y$, the
elementary symmetric functions are $x+y$ and $xy$.}
\end{frame}

\begin{frame}\frametitle{Andr\'e polynomials}
Andr\'e polynomials.

\end{frame}

\section{The Second Order Eulerian Polynomials}


\begin{frame}

\begin{center}
{\Large \color{blue} \bf IV. The Second Order Eulerian Polynomials}
\end{center}
\end{frame}

\begin{frame}\frametitle{Stirling permutations}


\noindent
{\large\bf  Stirling Permutations.} Stirling
permutations were introduced by Gessel and Stanley.
For $n\geq 1$, let
$[n]_2$ denote the multiset $\{1,1, 2, 2, \ldots, n, n\}$.  A permutation $\pi=\pi_1\pi_2 \cdots
\pi_{2n}$ of $[n]_2$ is
said to be a Stirling permutation if for any $1\leq j \leq n$ the elements
between the two $j$'s in $\pi$, if any, are greater than $j$.
  A descent and an ascent of $\pi$ can be defined
analogously to the case of ordinary permutations.
For a Stirling permutations $\sigma$, we
adopt the convention that $\sigma$ is patched with
a zero both at the beginning and at the end, that is,
$\sigma_0=\sigma_{2n+1} = 0$.
\end{frame}

\begin{frame}\frametitle{Some statistics of Stirling permutations}
Let $Q_n$ be the
set of Stirling permutations on $[n]_2$. For
$\sigma \in Q_n$, the sets of ascents, descents
and plateaux are defined by
\begin{eqnarray*}
   {\rm Asc}(\sigma) & = & \{ i \,|\, \sigma_{i-1}
              < \sigma_{i}, \; 1\leq i \leq 2n\},
               \\[6pt]
     {\rm Des}(\sigma) & = & \{ i \,|\, \sigma_{i }
              >  \sigma_{i+1}, \; 1\leq i \leq 2n\},
               \\[6pt]
      {\rm Plat}(\sigma) & = & \{ i \,|\, \sigma_{i }
              = \sigma_{i+1 }, \; 1\leq i \leq 2n \}.                \end{eqnarray*}
We use ${\rm asc}(\sigma)$, ${\rm des}(\sigma)$
and ${\rm plat}(\sigma)$ to denote the cardinalities
of ${\rm Asc}(\sigma)$, ${\rm Des}(\sigma)$
and ${\rm Plat}(\sigma)$, respectively.
\end{frame}

\begin{frame}\frametitle{The equidistribution property}
The following equidistribution property is due to Bona.

\begin{thm}[Bona] For $n\geq 1$,
the statistics ${\rm asc}(\sigma)$, ${\rm des}(\sigma)$
and ${\rm plat}(\sigma)$ have the same distribution
over $Q_n$.
\end{thm}

The simplest example is the case $n=1$,
where the Stirling permutation $11$ has one ascent, one descent, and one plateau.



\end{frame}

\begin{frame}\frametitle{The Second-order Eulerian polynomials}

The number of Stirling permutations of $[n]_2$
with $k$ descents is called the second order
Stirling number, denoted by $C(n,k)$, or
$\left\langle \! \left\langle {n \atop k} \right\rangle
 \!\right\rangle$.


Gessel and Stanley defined the second order
Eulerian polynomials $C_n(x)$ by $C_0(x)=1$
and for $n\geq 1$,
\begin{equation*}
C_n(x)= \sum_{k=1}^{n} C(n,k)x^k.
\end{equation*}


\end{frame}

\begin{frame}
Janson  defined the
trivariate generating function
\begin{equation*}
C_n(x,y,z)=\sum_{\sigma \in Q_n}
x^{{\rm des} (\sigma)}
y^{{\rm asc} (\sigma)}
z^{{\rm plat} (\sigma)}.
\end{equation*}

Janson  proved the symmetry property of the
joint distribution of the statistics
${\rm asc}(\sigma)$, ${\rm des}(\sigma)$
and ${\rm plat}(\sigma)$ by using an urn model.
\begin{thm}[Janson]
For $n\geq 1$, $C_n(x,y,z)$ is
symmetric in $x,y,z$.
\end{thm}

As pointed out by S.-M. Ma, the polynomials
$C_n(x,y,z)$ were introduced by Dumont. The
symmetry property was also due to Dumont.



\end{frame}

\begin{frame}\frametitle{A Paper of Dumont in French}

In a
paper in French published in JCTA, in 1980,
Dumont introduced the notion of a repetition of
a Stirling permutation, which is called a plateau by Bona. While we do not read French, the
machine translation seems to be a good avenue to get around.
Although machine translation can play a decisive role at times,
it may also have the effects of
 serious confusions or even terrible misunderstandings.
There were some outrageous stories. But in this case, it was great fun.


\vskip 3mm
\footnotesize {
{\color{blue}
\begin{thebibliography}{1}
\bibitem{Dumont-1980}
 D. Dumont, Une gen\'eralisation trivari\'ee sym\'etrique des nombres eul\'eriens,
J. Combin. Theory, Ser. A, 28 (1980), 307-320.
\end{thebibliography}}}

\end{frame}



\subsection{The $e$-Positivity of $C_n(x,y,z)$}

\begin{frame}{The $e$-Positivity of $C_n(x,y,z)$}
For $n\geq 1$, since $C_n(x,y,z)$ is symmetric, we can write
\begin{equation*}
C_n(x,y,z) =\sum_{i+2j+3k=2n} \gamma_{i,j,k} (x+y+z)^i
(xy+xz+yz)^j (xyz)^k .
\end{equation*}

Let $u=x+y+z$, $v=xy+xz+yz$ and $w=xyz$.
Then we have
\begin{eqnarray*}
 D(u) & = & 3w , \\[3pt]
 D(v) & = & 2uw, \\[3pt]
 D(w) & = & vw.
\end{eqnarray*}
It follows that the coefficients $\gamma_{i,j,k}$ are nonnegative.

\end{frame}

\begin{frame}\frametitle{The $e$-Positivity of $C_n(x,y,z)$}

Using 0-1-2-3 increasing plane trees on $\{1, 2, \ldots, n\}$, Chen-Fu (2021) obtained an interpretation
of the coefficients $\gamma_{i,j,k}$.
 \begin{thm}[Chen-Fu, 2021] For $n \geq 1$ and $i+2j+3k=2n+1$,
   $\gamma_{\,i,\,j,\, k}$   equals the
 number of 0-1-2-3 increasing plane trees on $[n]$
 with $k$ leaves, $j$ degree one vertices and $i$
 degree two vertices.
 \end{thm}



\footnotesize {
{\color{blue}
\begin{thebibliography}{1}
\bibitem{Chen-Fu-2021}
W.Y.C. Chen and A.M. Fu,
A Context-free grammar for the e-positivity of the trivariate second-order Eulerian polynomials, arXiv:2106.08831.
\end{thebibliography}}}


\end{frame}




\section{Alternatingly Increasing and Spiral Polynomials}

\begin{frame}

\begin{center}
{\Large \color{blue} \bf V. Alternatingly Increasing and

Spiral Polynomials}
\end{center}
\end{frame}

\begin{frame}
\frametitle{Alternatingly increasing and spiral polynomials}
A polynomial \[ f(x)=\sum_{i=0}^n  a_ix^i\]
 is called { alternatingly increasing} if
\[ a_0\leq a_n\leq a_1\leq a_{n-1}\leq\cdots \leq a_{\lfloor{{(n+1)}/{2}}\rfloor}.\]

{\color{blue} This is exactly what Bruce Sagan called top interlacing or bottom interlacing. }

\end{frame}

\begin{frame}
\frametitle{Alternatingly increasing and spiral polynomials}

It is said to be spiral if
\[ a_0\leq a_n\leq a_1\leq a_{n-1}\leq\cdots \leq a_{\lfloor{{(n+1)}/{2}}\rfloor}  \]
or
$$a_n\leqslant a_0\leq a_{n-1}\leq a_1\leq \cdots\leq a_{\lfloor{n/2}\rfloor}.$$
If $f(x)$ is spiral and $\deg f=n$, then $x^nf(1/x)$ is alternatingly increasing, and vice versa.


{\small \begin{thebibliography}{1}
\bibitem{Beck2019}
M. Beck, K. Jochemko and E. McCullough, $ h^\ast$-polynomials of zonotopes, Trans. Amer. Math. Soc., {371} (2019), 2021--2042.

\end{thebibliography}}
\end{frame}

\begin{frame}
\frametitle{Alternatingly increasing and spiral polynomials}

Let $f(x)$ be a polynomial of degree $n$.
There is a unique decomposition, called the
{\color{blue} symmetric decomposition} of the form
 \[ f(x)= A(x)+xB(x),\]
 with the requirement that $A(x)$ and $B(x)$
 are symmetric with respect to degrees $n$ and $n-1$,
 respectively. More precisely, we have
\begin{equation}\label{ax-bx-prop01}
A(x)=\frac{f(x)-x^{n+1}f(1/x)}{1-x},
\quad B(x)=\frac{x^nf(1/x)-f(x)}{1-x}.
\end{equation}

\footnotesize {
{\color{blue}
\begin{thebibliography}{1}
\bibitem{Beck2010}
M. Beck and A. Stapledon, On the log-concavity of Hilbert series of Veronese subrings and Ehrhart series, Math. Z., \textbf{264} (2010), 195--207.
\end{thebibliography}}}
\end{frame}

\begin{frame}

\noindent
{\it Proof.}
By the symmetry conditions on $a(x)$ and $b(x)$, we
see that
\begin{eqnarray*}
  x^nA(1/x) & = & A(x), \\[3pt]
  x^{n-1} B(1/x) & = & B(x).
  \end{eqnarray*}
  Since $f(x)=A(x) + xB(x)$, we deduce that
\[ x^{n+1} f(1/x)  = x^{n+1} A(1/x) + x^{n} B(1/x) = xA(x) + x  B(x), \]
   and so
  \[ f(x) - x^{n+1} f(1/x) = (1-x) A(x). \]
  Meanwhile, we obtain that
  \[x^nf(1/x)-f(x) = (1-x) B(x). \]
\end{frame}


\begin{frame}\frametitle{Simplest Examples}

\[ a + bx =  (a + ax) + x (b-a).\]
\[ a+bx+cx^2 = (a+ (a+b-c)x+ a x^2 ) + x( c-a +(c- a)x),\]
and
\[ a+bx+cx^2 +d x^3 = A(x) + x B(x),
    \]
    where
\begin{eqnarray*}
 A(x) & = & a+ (b+a-d)x + (a+b-d)x^2  + ax^3 , \\[3pt]
 B(x) & = & (d-a)  + (c-a-b+d)x   +  (d-a)x^2.
\end{eqnarray*}

\end{frame}

\begin{frame}\frametitle{A procedure to compute $A(x)$ and $B(x)$.}

Intuitively, the coefficients of $A(x)$ and $B(x)$ are
determined alternatively in the following order:
first, the constant term of $A(x)$, then the highest term
of $A(x)$, followed by the highest term of $B(x)$, then
the constant term of $B(x)$, then the coefficient of
$x$ in $A(x)$, and so forth.

\end{frame}

\begin{frame}
For a polynomial $f(x)$ with alternatively
increasing coefficients, it can be written
as
\[ f(x) = A(x) + xB(x),\]
where both $A(x)$ and $B(x)$ are symmetric
and unimodal. This is where the notion of bi-gamma
positivity comes into play. Let $m=\lceil\frac{n}{2}\rceil$. Then  we
have
\begin{eqnarray*}
A(x) & = & \sum_{i=0}^m(a_i-a_{n-i+1})(x^i+x^{i+1}+\cdots+x^{n-i}) ,  \\[3pt]
B(x) & = & \sum_{i=0}^m (a_{n-i}-a_{i})(x^i+x^{i+1}+\cdots+x^{n-i-1})    .
\end{eqnarray*}

\end{frame}

\begin{frame}



The above formulas can be verified directly, or can be
derived from the above expressions in (\ref{ax-bx-prop01})
 for $A(x)$ and $B(x)$.

For example, let $f(x)=a_0+a_1x+a_2x^2+a_3x^3$. Assume that
\[ a_0\leq a_3\leq a_1 \leq a_{2}.\]
Then
\[A(x)=a_0(1+x+x^2+x^3)+(a_1-a_3)(x+x^2)\]
 and
 \[B(x)=(a_3-a_0)(1+x+x^2)+(a_2-a_1)x\]



\end{frame}



\begin{frame}

\begin{thm}
Let $f(x)$ be a polynomial of degree $n$ and let
\begin{equation}
f(x)=A(x)+xB(x)
\end{equation}
be the symmetric decomposition of $f(x)$. Then
$f(x)$ is alternatively increasing if and only if
$A(x)$ and $B(x)$ have nonnegative coefficients.
\end{thm}

We note that the above assertion can also be
verified along with the procedure to determine
the coefficients of $A(x)$ and $B(x)$.

 \end{frame}

 \begin{frame}
For example, for the $q$-derangement number $D_5(q)$, we have
\[ D_4(q)=q + 2q^2 + 2 q^3 +2 q^4  + q^5 +q^6. \]

\[ *** \]


\noindent
{\color{blue}
{\sl {\large Question.} What is the
symmetric decomposition of $D_n(q)$?
Study the combinatorial and analytical properties
of the decomposition.  --- Note} }
\end{frame}

\begin{frame}\frametitle{Back to the spiral property}

This property was first observed by
X.D. Zhang in his proof of a conjecture
of Chen-Rota on the $q$-derangement numbers.
\[ D_n(q) = [n]! \sum_{k=0}^n (-1)^k q^{n\choose 2}
       {1\over [k]!},\]
       where $[n]! = [1][2]\cdots [n]$ and $[n]=1+q+\cdots +q^{n-1}$.

While $D_n(q)$ is not symmetric, {  Chen-Rota}
observed that the maximum coefficient of
$D_n(q)$ appears in the middle. X.D. Zhang
noticed the the spiral property, a term I suggested.

\end{frame}



\begin{frame}\frametitle{The spiral property}


He was my postdoc at that time. I was very impressed
with his keen observation. While the others might be
more impressed by his title as a postdoc, because
the title of a postdoc was regarded by some
 as the highest level of
diplomas. Back to that time,
there were only a handful postdocs in a province in the
south, where one could instantly become
 renowned for carrying
such a title. Indeed,
one was not called Dr. so and so, but Postdoc so and so.
There was even a special term (Bo-Hou) in Chinese.

\end{frame}
\begin{frame}

 {\small \begin{align*}
D_1(q)&=0, \quad D_2(q)=q, \quad
D_3(q) =q+q^2,\\
D_4(q)& =q+2q^2+2q^3+2q^4+q^5+q^6,\\
{\color{blue} D_5(q)} &{\color{blue} \; =q+3q^2+5q^3+7q^4+8q^5+8q^6+6q^7+4q^8+2q^9, }\\
D_6(q)&=q+4q^2+9q^3+16q^4+24q^5+32q^6+37q^7+38q^8+35q^9\\
&\qquad+28q^{10}+20q^{11}
+12q^{12}+6q^{13}+2q^{14}+q^{15},\\
D_7(q)&=q+5q^2+14q^3+30q^4+54q^5+86q^6+123q^7+160q^8+191q^9\\
&\qquad+210q^{10}+214q^{11}
+202q^{12}+176q^{13}+141q^{14}+104q^{15}\\
&\qquad+69q^{16}+41q^{17}+21q^{18}+9q^{19}+3q^{20}.
\end{align*} }
Look at $D_5(q)$, which is evidently spiral. How could one possibly fail to take a notice of this obvious fact at the beginning? Or it was a destiny
not to see it. What a pity!
\end{frame}

\begin{frame}\frametitle{Remarks}
\begin{itemize}

\item  Although the $q$-derangement polynomials are not symmetric,
in an asymptotic sense, it is almost symmetric. {Chen and Wang} showed that
the limit distribution of the $q$-derangement polynomials is
normal.

\vskip 3mm
\footnotesize {
{\color{blue}
\begin{thebibliography}{1}
\bibitem{Chen-Wang-2010}
W.Y.C. Chen and D.G.L. Wang,
The limiting distribution of the q-derangement numbers,
European J. Combin. 31 (2010) 2006-2013.
\end{thebibliography}}}



\item {Chen-Xia} noticed that the
spiral property follows from a ratio
property like the log-concavity, called the ratio monotone
property.
\end{itemize}

\end{frame}

\begin{frame}\frametitle{The ratio
monotonicity }

 We say that a sequence $a(1), a(2), \ldots, a(n)$  of
 positive numbers is  ratio
monotone if
\begin{align}\label{D-1}
\frac{a(1)}{ a(n) }\leq \frac{a(2)}{ a(n-1) } \leq \cdots \leq
\frac{a(\lfloor n/2\rfloor)}{a(\lceil n/2 \rceil+1)}\leq 1
\end{align}
and
\begin{align}\label{D-2}
\frac{a(n)}{a(2)} \leq \frac{a(m-1)}{a(3)} \leq \cdots
 \leq  \frac{a(\lfloor n/2 \rfloor+2)}
 {a(\lceil n/2 \rceil)}  \leq 1,
\end{align}
where  $\lfloor x \rfloor$ and $\lceil x \rceil$
are the floor function and the ceiling function.



In the case that all the inequalities are strict,
 we say that the sequence is
strictly ratio monotone.

\end{frame}


\begin{frame}
\frametitle{The ratio monotonicity and the spiral property}
\begin{itemize}

\item
{Chen and Xia}
 showed that for $n\geq 6$,
 the $q$-derangement numbers $D_n(q)$
are strictly ratio monotone, except for the last term when $n$ is
even.

 \item
 It has also been shown that
the Boros-Moll polynomials are ratio monotone.
\end{itemize}


\vskip 3mm
\footnotesize {
{\color{blue}
\begin{thebibliography}{1}

\bibitem{Chen-Xia-2011}
W.Y.C. Chen and E.X.W. Xia,
The ratio monotonicity of the $q$-derangement numbers,
Discrete Math. 311(6) (2011) 393-397

\bibitem{Chen-Xia-2009}
W.Y.C. Chen and E.X.W. Xia,
The ratio monotonicity of the Boros-Moll polynomials,
Math. Comp. 78 (2009) 2269-2282.
\end{thebibliography}}}





\end{frame}






\begin{frame}\frametitle{Example}

For example,
for the case of $D_6(q)$ without
the last term, we see that
\begin{align} &
{1 \over 2} < {4 \over 6} < {9 \over 12} <  {16 \over 20}
 <  {24\over 28 } < {32\over 35} < {37\over 38} <1, \label{I-1}\\[6pt]
&  {2\over 4} < {6\over  9}  < {12\over 16} < {20\over 24} <
{28\over 32}
  <  {35\over 37}< 1
. \label{I-2}
\end{align}
It can be checked that  $D_6(q)$ has the following spiral property
\[  1 <  2  < 4 <  6   < 9 <  12
 < 16 <  20   <24 <  28   < 32
  <   35
 < 37 <  38 ,\]
 where the last term is not taken into consideration.


\end{frame}



\begin{frame}
\frametitle{Bi-$\gamma$-positive and alternatingly increasing}
\begin{thm}[Ma-Ma-Yeh-Yeh, 2021]
Suppose $p(x,y)$ can be expanded as
\begin{equation*}\label{defpartial}
p(x,y)=\sum_{i=0}^ny^i\sum_{j=0}^{\lfloor{(n-i)/2}\rfloor}\mu_{n,i,j}x^j(1+x)^{n-i-2j}.
\end{equation*}
If $p(x,y)$ is partial $\gamma$-positive, $p(x,1)$ is bi-$\gamma$-positive and {$0\leq y\leq 1$ is a given real number}, then
$p(x,y)$ is alternatingly increasing.
\end{thm}


\end{frame}


\section{ Grammars and the Ramanujan-Shor polynomials}

\begin{frame}

\begin{center}
{\Large \color{blue} \bf VI. Grammars and

the Ramanujan-Shor polynomials}
\end{center}
\end{frame}

\begin{frame}
\frametitle{The Ramanujan-Shor polynomials}

For integers $1\leq k\leq r+1$, Ramanujan  defined the polynomials $\psi_k(r,x)$ by the following relation:
\begin{equation*}\label{equation:psi}
  \sum_{k=0}^\infty \frac{(x+k)^{r+k}e^{-u(x+k)}u^{k}}{k!}
  =\sum_{k=1}^{r+1}\frac{\psi_k(r,x)}{(1-u)^{r+k}},
\end{equation*}
and derived the recurrence relation:
\begin{equation}\label{equation:relation_original}
 \psi_k(r+1,x) =  (x-1)\psi_k(r,x-1)+\psi_{k-1}(r+1,x)-\psi_{k-1}(r+1,x-1),
\end{equation}
where  $\psi_1(0,x)=1$, $\psi_0(r,x)=0$ and
$ \psi_k(r,x)=0$ for $k>r+1$.
\end{frame}




\begin{frame}
Berndt, Evans and Wilson obtained
another  recurrence relation for $1\leq k\leq r+1$,
\begin{equation*} \label{Berndt}
\psi_k(r,n)=(n-r-k+1)\psi_k(r-1,n)+(r+k-2)\psi_{k-1}(r-1,n).
\end{equation*}
By setting $u=0$ in \eqref{equation:psi}, Ramanujan deduced the identity for $r\geq 1$,
\begin{equation*}\label{equation:psi_sum}
\sum_{k=1}^{r+1}\psi_k(r,x)=x^r.
\end{equation*}

Zeng  observed that the polynomials
 $\psi_k(r,x)$  coincide with the polynomails
 introduced by Shor as a refinement of Cayley's
 formula for the numbers of rooted trees on $n$ vertices.

 The polynomials
 $Q_{n,k}(x)$ are called the Ramanujan-Shor polynomials.
\end{frame}



\begin{frame}
Let
\begin{equation*}
Q_{n,k}(x)=\psi_{k+1}(n-1,x+n).
\end{equation*}
Then Ramanujan's identity can be recast as
\begin{equation*}
\sum_{k=0}^{n-1}Q_{n,k}(x)=(x+n)^{n-1}.
\end{equation*}
It is not hard to give a combinatorial explanation
of the recurrence relation (***) derived by
Berndt ****.
Shor posed the problem of finding a combinatorial
interpretation of the recurrence relation (***).
While a combinatorial proof has been found by
Chen-Guo and a simpler construction has been
provided by Guo, none of them seems to be satisfactory.

\end{frame}

\begin{frame}

Chen-Yang (2018) found a grammar for the
Ramanujan-Shor polynomials based on the grammar
of Dumont, and then gave a grammatical
derivation of the recurrence relation (RR).

However, it is still in demand to find a relatively
simple bijection for the recurrence relation (RR).
\end{frame}




\begin{frame}\frametitle{Connection found by Wang and Zhou}



  Recently, Wang and Zhou showed that the orbifold Euler characteristic of the moduli space of stable curves of genus zero with $n$ marked points turns out
 to be  the Ramanujan-Shor polynomial  $Q_{n-1,k+1}(x)$ evaluated at
 $x=-1$. They
 discovered the connection
by checking with the OEIS. As Stanley mentioned this morning,
and he did find something that is already there. For the case of Wang and Zhou,
it was beyond their expectation to see their finding. Zhou even got interested in combinatorics in a larger sense, including some work of Rota.


\end{frame}




\begin{frame} \frametitle{A grammar for  Ramanujan-Shor polynomials}
Utilizing Shor's recursive procedure to construct rooted trees, Dumont and Ramamonjisoa  found a context-free grammar to enumerate rooted trees with a given number of improper edges. They defined a
grammar $G$ by the following substitution rules:
\[
G=\{ A\rightarrow A^3S,\quad  S\rightarrow AS^2\}.
\]
\end{frame}


\begin{frame}\frametitle{Dumont-Ramamonjisoa's grammar}
Let $D$ denote the formal derivative with respect to $G$.
%Let $Q_{n}(x,y)$ denote the generating function of $Q_{n,k}(x)$, that is,
%\[
%    Q_n(x,y)=\sum_{k=0}^{n-1}Q_{n,k}(x)y^k.
%\]
%Dumont and Ramamonjisoa described the special values of $Q_n(x,y)$ for $x=0,1,-1$ by the Dumont grammar.
%For example, they
Dumont and Ramamonjisoa showed that, for $n\geq1$,
\begin{equation*}
   D^{n-1}(AS)=A^nS^{n}\sum_{k=0}^{n-1}b(n,k)A^{k},%Q_n(0,A).%,\\[6pt]
\end{equation*}
where $b(n,k)$ denotes the number of rooted trees on $[n]$ with $k$ improper edges. Note that $b(n,k) =Q_{n,k}(0)$.

\end{frame}

\begin{frame} \frametitle{A grammar for  Ramanujan-Shor polynomials}


Based on the Dumont-Ramamonjisoa grammar, Chen-Yang-Hao (2021) obtain a grammar $H$ to generate the Ramanujan-Shor polynomials $Q_{n,k}(x)$.
Let
\[
H\colon a\rightarrow axy,x\rightarrow xyw,y\rightarrow y^3w,w\rightarrow yw^2,
\]
and let $D$  denote the formal derivative with respect to $H$.
For $n\geq1$, we obtain the following relation
%\[
%  D^{n}(a)=axy^nw^{n-1}Q_n(xw^{-1},y),
%\]
%that is,
\[
  D^{n}(a)=axy^nw^{n-1}\sum_{k=0}^{n-1}Q_{n,k}(xw^{-1})y^k.
\]
\end{frame}


\begin{frame} \frametitle{A grammar for  Ramanujan-Shor polynomials}

With the aid of the grammar $H$, we are led to
a simple derivation of the Berndt-Evans-Wilson-Shor recursion.

\begin{equation*} \label{Berndt}
\psi_k(r,n)=(n-r-k+1)\psi_k(r-1,n)+(r+k-2)\psi_{k-1}(r-1,n).
\end{equation*}
It turns out that the grammar $H$ can also be used to derive the
 Abel identities.

\end{frame}

\begin{frame}\frametitle{Abel's identities}
  As will be seen, the Abel identities can be
 deduced from the Leibniz formula with respect to the grammar $H$.

 Riordan defined the sum
 \[
A_n(x_1,x_2;p,q)=\sum_{k=0}^n\binom{n}{k}(x_1+k)^{k+p}(x_2+n-k)^{n-k+q},
\]
where $n\geq 1$ and the parameters $p,q$ are integers.
He found closed formulas of $A_n(x_1,x_2;p,q)$ for some
$p$ and $q$. These identities were called the
Abel identities or the Abel-type identities since  the case   $(p,q)=(-1,0)$  corresponds to  the classical Abel identity.

\end{frame}


\begin{frame}\frametitle{Abel's identities}
We give a grammar $H'$ based on the grammar $H$ and show that
the summations $A_n(x_1, x_2; p,q)$ can be evaluated by
using the grammar $H'$.
Using this approach, closed forms can be deduced  for  $A_n(x_1,x_2;-1,0)$, $A_n(x_1,x_2;-1,-1)$ and $A_n(x_1,x_2;-2,0)$ and $A_n(x_1,x_2;-2,-2)$. The case of
  $A_n(x_1,x_2;-2,-2)$ seems to be new.

\end{frame}

\begin{frame}\frametitle{The Lacasse identity}

There is a grammatical explanation of the
identity
  \begin{equation*}
  n^{n+1}=
  \sum_{k=1}^n\sum_{k=0}^{n-j}\binom{n}{j}\binom{n-j}{k}j^jk^k(n-j-k)^{n-j-k}.
  \end{equation*}
It was conjectured by Lacasse  in the study of the
PAC-Bayesian machine learning theory. Since then, several proofs have been found by *******.

 \end{frame}







\section{Recent Developments}

\begin{frame}

\begin{center}
{\Large \color{blue} \bf VII. Recent Developments}
\end{center}
\end{frame}

\begin{frame}\frametitle{Recent developments}
Here only list some recent developments without
giving the details. I plan to write a more
detailed version of this presentation.
\begin{itemize}
\item[(1)] The interpretations of the Eulerian polynomials, the second-order Eulerian polyomials and Andr\'e polynomials in terms of Young tableaux have been given by { Han-Ma (2020)}.



\item[(2)] The flag ascent-plateau polynomial of Stirling permutations is not gamma-positive, and the semi-gamma-positivity of it are proved. ( { Ma-Ma-Yeh, 2020})




\end{itemize}

\end{frame}


\begin{frame}\frametitle{Recent developments}

\begin{itemize}
\item[(3)] The types A and B alternating Eulerian polynomials have gamma-vectors alternate in sign. (Lin-Ma-Wang-Wang, 2021, Ma-Fang-Mansour-Yeh, 2021)



\item[(4)] The enumerative polynomials of Stirling multipermutations by the statistics of plateaux, descents and ascents are partial gamma-positive. (Lin-Ma-Zhang, 2021)





\end{itemize}

\end{frame}


\begin{frame}\frametitle{Recent developments}

\begin{itemize}


\item[(5)] Two connections between fixed point and cycle (p,q)-Eulerian polynomials and multivariate polynomials of colored permutations are established. (Ma-Ma-Yeh-Yeh, 2021)





\item[(6)] Chen-Hao-Yang (2021)  used grammars to construct
stable multivariate polynomials in answer to
questions proposed by Haglund and Visontai.

\end{itemize}

\end{frame}

\begin{frame}
\frametitle{}
\begin{center}
{\bf \huge  \textcolor{blue}{Thank you!}}\\[10pt]

\end{center}
\end{frame}


\end{CJK*}
\end{document}
