\documentclass[professionalfont, % ignorenonframetext,
11pt]{beamer}
%%% \usepackage{beamerarticle}

\usepackage{newtxtext,newtxmath}
\usepackage{times}
\usepackage{color}
\mode<presentation>
{
\setbeamertemplate {footline}[frame number]
%%设置footline显示页码,但是由于Madrid也定义了一个footline,后出现的会覆盖前面的定义。另一方面说明，slide的每一部分都是可以自己定义的。
  \usetheme{Madrid}
\setbeamercovered{transparent}
\setbeamersize{text margin left=2em,text margin right=2em}
%%设置PPT左右边框的大小
\date{September 5, 2023}
%%自行设置日期，如果想自动生成日期，用\date{\today}
}


\renewcommand{\baselinestretch}{1.5}
\parskip=6pt

\usepackage{tikz}
%\usetikzlibrary{positioning}
\usetikzlibrary{trees}
\usetikzlibrary{calc}
\usetikzlibrary{intersections}

\tikzstyle{every node}=[circle,inner sep=1pt,fill=white!60]
\tikzstyle{tn}=[shape=circle, draw, color=black!70]
\tikzset{
  rect1/.style = {
    shape = rectangle,% 指定样式
    minimum height=2cm,% 最小高度
    minimum width=4.5cm,% 最小宽度
    align = center,% 文字居中
  }
  }

\begin{document}




\begin{frame}

\begin{center} {  \LARGE\bf {\textcolor{blue}
 {The Idea of a Grammatical Calculus}}  }

\vskip 3mm
{\small
Bill Chen

Tianjin University, China

\vskip 3mm
International Conference on Enumerative Combinatorics and Applications \\
(ICECA 2023)}
\end{center}
%\vskip -1mm

{\small

Chair: \quad \quad \, Toufik Mansour  \\
Co-chairs: \;\, M. Dukes, I. Kotsireas, Y. Roichman, A.Sh. Shabani,\\
\qquad \qquad  \quad\, A. Vainshtein, G. Yildirim.
 }
\end{frame}


\begin{frame}
Hello, Everyone! Good morning, good afternoon and good evening!
Thanks for coming! To the organizers of the conference, especially
to the
tireless Professor Toufik Mansour,  I would like to say
\begin{center}
\includegraphics[scale=0.20]{PPT-Mansour/Pandington-Bear.png}
\end{center}
I am honored and humbled to happen to be on the list of speakers and to be
monitored by such a distinguished audience.
\end{frame}


\begin{frame}

Where should I begin? I asked myself.
The King in the  Wonderland said,
begin at the beginning. But I am afraid that I might
end up with the beginning as well. Anyway, let us get started with
the idea of a programming language or a formal language, which might sound  irrelevant and
even bonkers.
But please bear with me for a second.

As one can imagine,  the fundamental issue  of a
programming language is to regulate every sentence
so that there is no ambiguity whatsoever. You simply
cannot say one thing and mean another, and the machine
does not have to read the tone between the lines, like
in a diplomatic statement.
Then the salvation came from the revolutionary concept,
namely, the idea of a context-free grammar.
\end{frame}

\begin{frame}
To make a long story short,
a context-free grammar consists of a set of
production rules. Each rule plays his own part regardless
of the context, just like you do your duty and you do not
really  care what other people think about you,
contrary to the real life scenarios.

While the grammars we are concerned with
are not exactly the same
as in practical use, due to completely different purposes,
their constructions fall into the
same framework, at least in theory.
\end{frame}


\begin{frame}{Connection to the Umbral Calculus}

Is it far fetched to relate to context-free grammars?
You may ask. I can't answer in one word.
Let
us consider the derivative property:
\[ D(fg) = D(f)g + fD(g). \]
Does this ring a bell to you?

{\textcolor{blue}{Observation:}}
If you stare at it for some time, you
may wonder if
a derivative operator $D$ is context-free
  in the sense that
when $D$ is taking an action on $f$,
it is none of the business of $g$, and
vice versa.


\end{frame}



\begin{frame}

As an after event wisdom, it is not insane to claim that
the ideology of context-free grammars can be traced back to the
concept of differential operators. Even if it were true,
it would  be a pointless and worthless truth.
But there is something to it,
when it comes to certain situations regarding combinatorial enumeration,
for
some combinatorial structures  are  intrinsically context-free.

Such context-free properties may look inconspicuous and some
may have been taken for granted,  but they may have the potential to
accomplish formidable missions like secret agents.
This is truly the embarkation point of our journey.


\end{frame}

\begin{frame}

Instead of projecting decorated theorems and
dwelling on the rigorous derivations, I have a feeling
that it's probably more authentic,
rather, to be less formal,  and just to have a chat
  about some basic ideas and  intuitions that
are not touched upon in the technical publications.

    Let us be a little more serious. Consider the
    grammar $ f \rightarrow f$. What is
   $D(f^{-1})=?$
Answer:
\[ \textcolor{blue}{\fbox{$D(f^{-1}) = -f^{-1}$.}} \]

Since $ff^{-1}=1$, The derivative property demands that
\[ D(f) f^{-1} + f D(f^{-1}) =0,\]
which yields $D(f^{-1}) = -f^{-1}$.
On the other hand, in view of the chain rule, we get the
same result.



\end{frame}

\begin{frame}
    Look at this lovely minus sign here! It tells that
    the formal derivative $D$  behaves like
    a sign-reversing operator.
    And then?

   This   property reminds us of
   inverse relations.
   Let's turn to the classical example of the umbral calculus.
Rota's magical interpretation of the old-fashioned symbolic
method by using linear functionals demystifies the
illusion of lifting a subscript of $a_n$ to a superscript of $a^n$, that is,
\[ a_n = L(x^n). \]
A benchmarking example is the
following inverse pair:
\[ a_n = \sum_{k=0}^n
\binom{n}{k} b_k \quad \Leftrightarrow
\quad b_n = \sum_{k=0}^n  (-1)^{n-k}
\binom{n}{k} b_k.\]
\end{frame}

\begin{frame}
    Does the above grammar have anything to do with the
    umbral calculus? \\
    -- Yes, it does! Let's see how it works.

Treat $b_0, b_1, b_2, \ldots$ as a sequence of symbols, or
variables, or indeterminates bearing no meaning. Define the grammar as
\[ G=\{ f\rightarrow f, \; b_i \rightarrow b_{i+1} \;| \;
i=0, 1,2, \ldots\}. \]
Let $D$ denote the formal derivative with respect to $G$.
Suppose that the relation on the left holds.
By the Leibniz formula, we get
\[ a_n=\sum_{k=0}^n {n \choose k}   b_k  = f^{-1} D^n(fb_0). \]

\end{frame}

\begin{frame}

Thus,
\[ b_n=D^n(b_0) =
D^{n}(f^{-1} fb_0),\]
which yields
\[
\sum_{k=0} ^ n \binom{n}{k}  D^{n-k}(f^{-1}) D^k(fb_0)  =
\sum_{k=0} (-1)^{n-k}  \binom{n}{k}
      a_k, \]
as required.

The above reasoning
may be related to
something elusively remarked
by Professor Doron Zeilberger in his review
article on the umbral calculus.
I must confess that I am ignorant and likely going
to be even more so of the early
history on the subject. Nevertheless, we gotta move on.
\end{frame}

\begin{frame}{The Eulerian Polynomials}


As the next example, let's consider the grammar
\begin{equation}
 G=\{ x \rightarrow xy, \quad y \rightarrow xy\}.
\end{equation}

This is a grammar
 related to  the Eulerian polynomials
involving the number of descents of a permutation.
It was formally presented by Dumont. In fact, this grammar
led us to the notion  of a grammatical labeling [C.-Fu,   2017].

{\color{blue} Remark.} The two variables $x$ and $y$ are needed in order
to perform the grammatical calculus.


\end{frame}

\begin{frame}

First, we encounter the two choices of   notation. On one hand,
a grammar is represented by a set of
substitution rules. On the other hand, it can be encoded by a
differential operator:
\begin{equation}
D= xy \left( \frac{\partial}{\partial x} + \frac{\partial}{ \partial y} \right), \end{equation}
which
is a {\it creation operator}, rather than an {\it annihilation operator}.


Dumont argued that grammar notation has certain
advantages. On the other hand, he did not elaborate on
the advantage of the operator
notation in doing experiments with computer algebra.
\end{frame}

\begin{frame}


The above operator $D$ can be perceived as a derivative defined by
\[ D(x)=xy, \quad D(y)=xy.\]
Thus we have
\[
D^2(x) =D(xy)=    D(x) y + xD(y) = xy^2+x^2y,
\]
\[ D(xy^2) = D(x) y^2 + x D(y^2) = xy^3+ 2xy D(y) = xy^3 + 2x^2y^2,\]
\[ D(x^2y) = D(x^2)y + x^2 D(y) = 2xyD(x) + x^3y = 2x^2y^2 + x^3y.\]
Hence we get
\[ D^3(x) = xy^3 + 4x^2y^2 +x^3y. \]
\end{frame}

\begin{frame}




For $n\geq 1$, the bivariate Eulerian polynomials are defined by
\[ A_n(x,y) = \sum_{\sigma\in S_n} x^{{\rm des}(\sigma)} y^{{\rm asc} (\sigma)}, \]
where $\sigma$ ranges over all permutations of $[n]=\{1, 2, \ldots, n\}$,
and $  {\rm des}(\sigma)$ and $  {\rm asc} (\sigma)$  are defined
with the understanding
that $\sigma$ is patched a zero both
at the beginning and at the end.

\begin{block}{Theorem (Dumont)}
For $n\geq 1$, we have
\[ A_n(x,y) = D^n(x).\]
 \end{block}

As will be seen, the above relation
has a proof without words.
\end{frame}

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

    Let $w$ be a   formal power series, or a Laurent
    series on the variables of a grammar $G$, and let
    $D$ be the formal derivative relative to $G$. Define the
    generating function
    \[ {\rm Gen}(w, t) =\sum_{n=0}^\infty D^n(w) \frac{t^n}{n!}. \]

\begin{block}{Generating function of $A_n(x,y)$}
Set $A_0(x,y)=x$. Then we have
\[  {\rm Gen}(x, t) = \sum_{n=0}^\infty A_n(x,y) \frac{t^n}{n!}
  =  \frac{x-y}{1-x^{-1}y \, e^{(x-y)t}}. \]
\end{block}
\end{frame}

\begin{frame}

Since $D(x)=xy$ and $D(y)=xy$, we have
\[ D(x^{-1}) = -x^{-2} D(x) = -x^{-1} y,\]
\[ D(\underline{x^{-1}y}) = -x^{-1} y^2 + y =
\textcolor{blue} {(x-y)}\,\underline{x^{-1}y}.\]
The factor $x-y$ is something special to $D$.
According to the grammar $G$, both $x$ and $y$ are
substituted by $xy$. But $x$ and $y$ are supposed to be
different variables.
What is really going on here?

Answer: $\underline{x-y}$ is a constant with respect to $D$.



\end{frame}

\begin{frame}
 At first glance, one would not look upon $x-y$ as a constant
as one is used to  what is meant to be a constant.
However, this individual $D$ has his own judgement,
because what matters for $D$ is merely whether
\[  D(x-y) =0 .\]

This constant
property makes it possible to
deduce a simple expression of $D^n(x^{-1})$ for all $n\geq 1$,
\[ \textcolor{blue}{ \fbox{$D^n(\underline{x^{-1}y})
= (x-y)^n \,\underline{x^{-1}y}.$} } \]
Consequently, we are led to the generating function of $x^{-1}$.
\end{frame}


\begin{frame}

Since
\[ {\rm Gen}(x,t) \, {\rm Gen}(x^{-1},t) =1,\]
we instantly arrive at the
generating function of the bivariate Eulerian polynomials.

Are you convinced that this is all the computation we need?
Could it have been simpler?  It might seem a little odd that
this innocent looking  constant $x-y$ does play a crucial part
  beyond expectation!
\end{frame}

\begin{frame}{A grammatical labeling for the Eulerian polynomials}

As promised, we now give a grammatical labeling of permutations
reflecting the number of descents.
Given $\sigma=\sigma_1\sigma_2 \cdots \sigma_n \in S_n$, assume that $\sigma_0=\sigma_{n+1}=0$. For $0\leq i \leq n$,
we label the position
between $\sigma_i$ and $\sigma_{i+1}$ by $x$ if  $i$ is a descent,
and by $y$ if $i$ is an ascent, for example,
\[ 0 \, y\, 3\, y \,  5 \,x \,  2\, y \, 4\, x\, 1\, y \, 6 \, x\, 0 .\]
This labeling scheme is essentially
the same the descent word on $\{U, D\}$
or the $ab$-index  of  the symmetric group
in noncommutative variables $a$ and $b$, see
[R. Stanley, Longest alternating subsequences of permutations] and
[R. Stanley, A survey of alternating permutations].

\end{frame}
\begin{frame}
\begin{figure}[!ht]
\begin{center}
\begin{tikzpicture}[scale=0.6]
\node [tn,label=180:{}](zero){}[grow=down]
	%[sibling distance=16mm,level distance=10mm]
    %child[grow=231] {node [tn,label=180:{$2$}](one){}}
     child[grow=306] {node [tn,label=0:{}](one){}};
     \coordinate[label=above right:{$x$}] (a) at ($(one)!.5!(zero)$);
\end{tikzpicture}
\hskip 3mm\raisebox{4mm}{$\Rightarrow$}\hskip 5mm
\begin{tikzpicture}[scale=0.6]
\node [tn,label=90:$*$](zero){}[grow=down]
	%[sibling distance=16mm,level distance=10mm]
    child[grow=236] {node [tn,label=0:{}](one){}}
     child[grow=304] {node [label=0:{}](){}
     child[grow=304] {node [tn](two){}}};
     \draw(zero)--(two);
     \coordinate[label=left:{$y$}] (a) at ($(one)!.6!(zero)$);
      \coordinate[label=right:{$x$}] (a) at ($(zero)!.43!(two)$);
\end{tikzpicture}
\hskip 1cm\raisebox{20pt}{$(x\rightarrow xy)$}\\[5pt]
\vskip 5mm
\begin{tikzpicture}[scale=0.6]
\node [tn,label=180:{}](zero){}[grow=down]
	%[sibling distance=16mm,level distance=10mm]
    %child[grow=231] {node [tn,label=180:{$2$}](one){}}
     child[grow=236] {node [tn,label=0:{}](one){}};
          \coordinate[label=above left:{$y$}] (a) at ($(one)!.5!(zero)$);
\end{tikzpicture}
\hskip 3mm\hskip 3mm\raisebox{4mm}{$\Rightarrow$}\hskip 5mm  %%%6mm
\begin{tikzpicture}[scale=0.6]
\node [tn,label=90:$*$](zero){}[grow=down]
	%[sibling distance=16mm,level distance=10mm]
    child[grow=236] {node [label=180:{}](one){}
    child[grow=236] {node [tn](two){}}}
     child[grow=304] {node [tn,label=0:{}](three){}};
     \draw(zero)--(two);
     \coordinate[label=right:{$x$}] (a) at ($(zero)!.4!(three)$);
     \coordinate[label=left:{$y$}] (a) at ($(zero)!.43!(two)$);
\end{tikzpicture}
\hskip 1cm \raisebox{20pt}{$(y\rightarrow xy)$}
\end{center}
\end{figure}



    This  a proof without words!
    The picture exhibits what happens
    when $n+1$, signified by $*$,
    is inserted to a permutation
    of $[n]$. The update is apparently a local
    or a context-free operation.

\end{frame}






\begin{frame}{The left peak polynomials}

What is a peak? Here is a line that is perhaps not entirely unfit:

\begin{center}
\includegraphics[scale=0.22]{Peak.png}
\end{center}
\vskip -3mm

But what for permutations? Well, first of all, special attention
has to be paid to the first
position and the last position. Thereby we are faced with
three types of peaks:
left peaks, interior peaks and exterior peaks. By symmetry, right peaks
can be treated equally as left peaks.
\end{frame}







\begin{frame}

There have been various and sporadic notations for the three
or four kinds. We found it hard
to set our mind to which   to follow. We felt relieved, at least to ourselves,
that we came up with a possible solution, and we hope that
they are acceptable to you as well unless there are
preferred alternatives.
Here is our proposal: $L$ for left peaks, $M$ for interior peaks, and
$W$ for exterior peaks. Recall that as far as a left peak is
concerned, a zero is patched to the beginning of a permutation,
and other types of peaks are defined in the same fashion.
The following illustration reveals why:

\begin{figure}[!ht]
\begin{center}
\begin{tabular}{ccc}
\begin{tikzpicture}[scale=0.7]
\node[shape=circle, fill,inner sep=1.2pt,color=black!70] at (0,1.5) {};
\draw[color=red] (0,1.5) circle (0.3);
\draw[line width=1pt] (0,1.5)--(0,0)--(1,0);
\end{tikzpicture}
\hspace{0.7cm}
&
\begin{tikzpicture}[scale=0.7]
\node[shape=circle, fill,inner sep=1.2pt,color=black!70] at (0,1.5) {};
\node[shape=circle, fill,inner sep=1.2pt,color=black!70] at (1,1.5) {};
\draw[color=red] (0,1.5) circle (0.3);
\draw[color=red] (1,1.5) circle (0.3);
\draw[line width=1pt] (-0.5,0)--(0,1.5)--(0.5,0)--(1,1.5)--(1.5,0);
\end{tikzpicture}
\hspace{0.7cm}
&
\begin{tikzpicture}[scale=0.7]
\node[shape=circle, fill,inner sep=1.2pt,color=black!70] at (0,1.5) {};
\node[shape=circle, fill,inner sep=1.2pt,color=black!70] at (1,1.5) {};
\node[shape=circle, fill,inner sep=1.2pt,color=black!70] at (2,1.5) {};
\draw[color=red] (0,1.5) circle (0.3);
\draw[color=red] (1,1.5) circle (0.3);
\draw[color=red] (2,1.5) circle (0.3);
\draw[line width=1pt] (0,1.5)--(0.5,0)--(1,1.5)--(1.5,0)--(2,1.5);
\end{tikzpicture}
%% \\[5pt]
%% Left peaks\hspace{0.7cm} & Interior peaks\hspace{0.7cm} & Exterior peaks \\[5pt]
%% L\hspace{0.7cm} & M\hspace{0.7cm} & W
\end{tabular}
\end{center}
\end{figure}


\end{frame}

\begin{frame}

Incidentally,  $M$ is reminiscent of
``middle'', and $W$  of ``wide'',
in contrast with   ``interior'' and
``exterior''.

The bivariate left peak polynomials are defined by
\begin{eqnarray} \label{LMW-xy}
L_n(x,y) & = & \sum_{k=0}^{\lfloor n /2 \rfloor} L(n,k) x^{2k+1}
        y^{n-2k},
\end{eqnarray}
where $ L(n,k)$ denotes the number of permutations of $[n]$ with $k$ left peaks.
For $n=0$, we define $L_0(x,y)= x$.

 The  interior peak polynomials $M_n(x,y)$ are defined
 in the same manner.
\end{frame}



\begin{frame}
The grammar for the left peak polynomials $L_n(x)$ was discovered
by Ma
via a recurrence relation and  independently by C.-Fu
in terms of  a grammatical labeling.
Ma   further noticed that this grammar can also be employed to generate
the interior peak polynomials.
Here is the grammar
\begin{equation} \label{Gxy}
    G=\{ x \rightarrow xy, \;\, y\rightarrow x^2\}.
\end{equation}
Let $D$ be the formal derivative with respect to the grammar $G$.

\begin{block}{The grammatical interpretation}
For  $n \geq 0$, we have
$$
D^n(x)=L_n(x,y).
$$
\end{block}
\end{frame}


\begin{frame}{A grammatical calculus for the Gessel formula}

In the single variable version,
 David-Barton
 established a system of partial differential equations
involving $L(x,t)$ and $M(x,t)$,
 and found a solution  requiring
 one more step of integration.
 An explicit expression of $L(x,t)$
was given by Gessel.
Alternative proofs of the formulas for $L(x,t)$ and $M(x,t)$
have been given by Zhuang.

    \begin{block}{The bivariate form of the Gessel formula}
    \begin{equation*}\label{Genx}
   \sum_{n=0}^\infty L_n(x,y)\frac{t^n}{n!} =\frac{x\sqrt{y^2-x^2}}
    {\sqrt{y^2-x^2}\cosh(t\sqrt{y^2-x^2})-y\sinh(t\sqrt{y^2-x^2})}.
\end{equation*}
    \end{block}

\end{frame}

\begin{frame}
Appealing to the grammar, we find that $y^2-x^2$ is a constant,
since
\[ D(x^2) = D(y^2)=2x^2y. \]
Now we aim to computer $D^n(x^{-1})$ for $n\geq 1$.
Starting with
\[
D(x^{-1}) = -x^{-1}y, \quad
D^2(x^{-1}) = x^{-1}(y^2-x^2),
\]
 the following rhythm emerges. For $n\geq 0$,
\begin{eqnarray*}
D^{2n}(x^{-1})& =& x^{-1}  (y^2-x^2)^n,  \\[6pt]
 D^{2n+1}(x^{-1}) &= &-x^{-1}y(y^2-x^2)^n.
\end{eqnarray*}
\end{frame}

\begin{frame}


Taking the parity into account,  we deduce that
\begin{eqnarray*}
\sum_{n=0}^\infty D^{2n}(x^{-1}) {t^{2n} \over (2n)!} & =& x^{-1}
\cosh\left(t\sqrt{y^2-x^2}\right),
\\[6pt]
 \sum_{n=0}^\infty D^{2n+1}(x^{-1})
{t^{2n+1} \over  (2n+1)!} & = & -\frac{x^{-1}y}{\sqrt{y^2-x^2}}
\sinh\left(t\sqrt{y^2-x^2}\right).
\end{eqnarray*}
Now, we see how the hyperbolic functions come on the scene.

For the rest, Bob is your uncle, as we say in UK. Voila!

I hope that I didn't miss anything. Actually,
it took us quite a while to reach this point
largely because we did not anticipate such a short cut. We were
nearly there, but we missed the target in the previous pathetic attempts
[C.-Fu-2017].
\end{frame}

\begin{frame}{A grammatical labeling for left peaks}

To leave no doubt about the rigor of the grammatical
apparatus, we are obliged to provide a grammatical labeling. Once this
step is finished, before you know it, you may   have
  a proof without words.

The procedure is  straightforward. Given a permutation
$\sigma$ of $[n]$, display it in the style of a path,
more or less the same as
the mountain range view [T.K. Petersen, Eulerian Numbers].
Then label the steps of the path.
Wherever there is a peak, there are two $x$’s. The
remaining steps are labeled with $y$.
\end{frame}


\begin{frame}



\begin{figure}[!ht]
\begin{center}
\begin{tikzpicture}[scale=1]
\node (nine)[tn,label=90:{$9$}]{}[grow=down]
	[sibling distance=16mm,level distance=10mm]
    child {node [tn, label=270:{$1$}](one){}
     %[sibling distance=14mm,level distance=13mm]
            child[grow=130] {node [tn, label=180:{$3$}](three){}
            child {node [tn,label=90:{$5$}](five){}
            child[grow=231, dashed,line width=1pt] {node [tn,label=-90:{$0$}](fivel){}
            }}
        }}
    child {node [tn, label=270:{$4$}](four){}
    child[grow=55] {node [tn,label=0:{$6$}](six){}
    child[grow=55] {node [tn, label=90:{$8$}](eight){}
    child[grow=304] {node [tn, label=180:{$7$}](seven){}
    child[grow=304] {node [tn, label=180:{$2$}](two){}
    child[grow=304, dashed, line width=1pt] {node [tn, label=-90:{$0$}](zero){}}
    }}} }};
\coordinate[label=left:{\textcolor{red}{$x$}}] (x) at ($(nine)!.43!(one)$);
\coordinate[label=right:{$y$}] (x) at ($(three)!.36!(one)$);
\coordinate[label=right:{\textcolor{red}{$x$}}] (x) at ($(five)!.43!(three)$);
\coordinate[label=left:{\textcolor{red}{$x$}}] (x) at ($(five)!.43!(fivel)$);
\coordinate[label=left:{$y$}] (x) at ($(six)!.36!(four)$);
\coordinate[label=left:{\textcolor{red}{$x$}}] (x) at ($(eight)!.43!(six)$);
\coordinate[label=right:{\textcolor{red}{$x$}}] (x) at ($(eight)!.43!(seven)$);
\coordinate[label=right:{$y$}] (x) at ($(seven)!.36!(two)$);
\coordinate[label=right:{$y$}] (x) at ($(two)!.36!(zero)$);
\coordinate[label=right:{\textcolor{red}{$x$}}] (x) at ($(nine)!.43!(four)$);
\node[shape=circle, draw, inner sep=1.3pt, red] at (five) {};
\node[shape=circle, draw, inner sep=1.3pt, red] at (nine) {};
\node[shape=circle, draw, inner sep=1.3pt, red] at (eight) {};
\end{tikzpicture}
\end{center}
\end{figure}



The substitution rules are readily seen to be context-free, because
the insertion of $n+1$ into a permutation of $[n]$ only makes a local
impact on change of the descents. This property is precisely what is
needed to put the grammatical calculus on a firm footing,
 without thinking of the notation  $A(n,k)$ for the
Eulerian numbers.

\end{frame}


\begin{frame}

The idea of transformations of grammars   can be mobilized to
prove combinatorial identities.  Here is one stone for  two birds.

\begin{block}{Theorem (C.-Fu)}
Setting
\begin{eqnarray*}
x  =  \sqrt{\bar{x}\bar{y}}, \quad
y    =  (\bar{x} + \bar{y})/2 ,
\end{eqnarray*}
then the grammar \[ G=\{\bar{x}\rightarrow \bar{x}\bar{y}, \;\; \bar{y} \rightarrow \bar{x}\bar{y}\}\]
  is transformed into the grammar
\[
G=\{x \rightarrow xy, \quad y\rightarrow x^2\}.
\]

\end{block}

\end{frame}

\begin{frame}
 Let $D_1$ be the formal derivative with respect to the first grammar
 and let $D_2$ be the formal derivative with respect to the second grammar.
Resorting to the transformation, we have
$$ D_1(x) = xy, \quad D_1(y) = x^2.$$
Since $D_2(\bar{x}\bar{y})= (\bar{x}+\bar{y}) \bar{x} \bar{y}$, we infer that
$$
D_1(x)=D_2(\sqrt{\bar{x}\bar{y}})= {D_2(\bar{x}\bar{y}) \over 2 \sqrt{\bar{x}\bar{y}}}
= \sqrt{\bar{x}\bar{y}} \,\frac{\bar{x}+\bar{y}}{2} = xy
$$
and
$$
D_1(y)=D_2\left({\bar{x}+\bar{y} \over 2}\right) = \bar{x}\bar{y}=y^2,
$$
as required.
\end{frame}





\begin{frame}{The Petersen identity}
\begin{block}{Theorem (The bivariate form of the Petersen identity)}
For $n\geq 1$, we have
\begin{eqnarray*}
L_n\left(\sqrt{ {x} {y}},\frac{ {x}+ {y}}{2}\right)
=\sqrt{ {x} {y}^{-1}}\sum_{k=0}^n {n \choose k}
A_k( {x}, {y})\frac{( {y}- {x})^{n-k}}{2^{n-k}}.
\end{eqnarray*}
\end{block}


As long as we are furnished with the transformation on the two grammars,
it is simply a matter of formality to bring out the
connection between the Eulerian polynomials and the
left peak polynomials, due to Petersen.

\end{frame}


\begin{frame}

By the transformation of grammars, we obtain
\begin{align*}
 D^n(x)=D^n(\sqrt{\bar{x}\bar{y}})=D^n\left(\bar{x}\sqrt{\bar{x}^{-1}\bar{y}}\right).
\end{align*}
It follows that
\begin{align*}
L_n(x,y)=\sum_{k=0}^n{n\choose k} D^k(\bar{x}) D^{n-k}\left(\sqrt{\bar{x}^{-1}\bar{y}}\right).
\end{align*}
But $D^k(\bar{x})=A_k(\bar{x},\bar{y})$ and the constant property of
$\bar{x}-\bar{y}$ ensures that
\[   D^{n-k}\left(\sqrt{\bar{x}^{-1}\bar{y}}\right)=\frac{1}{2^{n-k}}(\bar{x}\bar{y}^{-1})^{\frac{1}{2}}(\bar{y}-\bar{x})^{n-k},\]
 we obtain the Petersen identity by
 switching $\bar{x}$ and $\bar{y}$ back to $x$ and $y$.

\end{frame}

\begin{frame}{The interrior peak polynomials}

Adopting the notation $M(n,k)$ for the number of
permutations of $[n]$ with $k$ interior peaks.
The bivariate interior  peak polynomials are defined by $M_0(x,y)=y$ and
for $n\geq 1$,
\begin{eqnarray} \label{LMW-xy}
M_n(x,y) & = & \sum_{k=0}^{\lfloor n /2 \rfloor} M(n,k) x^{2k+1}
        y^{n-2k}.
\end{eqnarray}
Let $D$ be the formal derivative with respect to the grammar $G$.

\begin{block}{The grammatical interpretation of Ma}
For  $n \geq 0$, we have
$$
D^n(y)=M_n(x,y).
$$
\end{block}
A grammatical labeling for interior peaks is given by [C.-Fu, 2023].

\end{frame}

\begin{frame}{The Stembridge  identity}

The above transformation of grammar also applies to  the Stembridge identity
on the Eulerian polynomials and the interior peak polynomials,
which was derived in his theory of enriched $P$-partitions.
Br\"and\'en   rediscovered this identity utilizing
the ``modified Foata-Strehl action''.

\begin{block}{Theorem (The bivariate form of the Stembridge  identity)}
For $n\geq 1$, we have
\begin{eqnarray*}
A_n( {x}, {y})=M_n\left(\sqrt{ {x} {y}},\frac{ {x}+ {y}}{2}\right).
\end{eqnarray*}
\end{block}


\end{frame}


\begin{frame}

Let $D_1$ and $D_2$ be given as before. We have
 \begin{align*}
A_n(\bar{x},\bar{y}) =D_2^n(\bar{x})=D_2^{n-1}(\bar{x}\bar{y})
 =D_1^{n-1}({x}^2)=D^{n}(y)=M_{n}(x,y).
\end{align*}
On the other hand, by the change of variables, we have
\begin{align*}
 M_{n}(x,y)=M_n\left(\sqrt{\bar{x}\bar{y}},\frac{\bar{x}+\bar{y}}{2}\right).
\end{align*}
 Thus we are led to the Stembridge identity
 by renaming $\bar{x}$ and $\bar{y}$.

Setting $y=1$, we  recover  the Stembridge  identity in the original form.

\begin{equation}\label{Stembridge-v}
 \sum_{\sigma \in {S}_{n}} x^{{\rm des}(\sigma)}=\left(\frac{1+x}{2}\right)^{n-1} \sum_{k\geq 0}M(n,k)\left(\frac{4x}{(1+x)^2}\right)^{k}.
 \end{equation}

\end{frame}




\begin{frame}{The Elizalde-Noy formula}

For a permutation $\sigma=\sigma_1\sigma_2\cdots \sigma_n$,
 an index $i$ $(3\leq n)$ is called a proper double descent
 if $\sigma_{i-2} > \sigma_{i-1} > \sigma_i$.
Let $U_n(y)$ be the generating function
for the  number of permutations of $[n]$ with $k$ proper
double descent, and let $U(y,t)$ be the
exponential generating function of $U_n(y)$.



\begin{block}{ The Elizalde-Noy formula}  The generating function $U(y,t)$ equals
\[ \frac{2\sqrt{(y-1)(y+3)}\, e^{t/2\cdot(1-y+\sqrt{(y-1)(y+3)})}}
{1+y+\sqrt{(y-1)(y+3)}-(1+y-\sqrt{(y-1)(y+3)})\, e^{t\sqrt{(y-1)(y+3)}}}.\]
\end{block}

\end{frame}

\begin{frame}

In a more general setting,
a  grammatical calculus has been carried out by Fu (2018).
As a refinement of the grammar for left peaks, Fu came up with the grammar
\[ G=\{ x\rightarrow xy, \; y \rightarrow xz, \;
      z \rightarrow zw, \; w\rightarrow xz\}. \]
It is not clear whether  this grammar measures up to the
computation of the joint distribution of
the number of left peaks and the
number of proper double descents.
 The formula of Fu turns out to be a unification of these of
 Gessel and  Elizalde-Noy,  for $y=1$ and $x=1$, respectively:
\[
 \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}}}.
 \] That's quite a remarkable feature.
\end{frame}



\begin{frame}{The $\gamma$-positivity}

With the aid of the grammar,  the $\gamma$-positivity of the Eulerian polynomials
becomes
transparent. Ma-Ma-Yeh made a change of variables:
\[ u =xy, \quad v = x+y. \]
Since
\[ D(u) = D(xy) = xy^2 + x^2 y = uv, \quad D(v)=D(x+y) =2xy =2u, \]
 the grammar $G$ is transformed into a new grammar
\[ H= \{ u \rightarrow uv, \; v \rightarrow 2u \}.\]


\end{frame}

\begin{frame}

This new grammar is obviously nonnegative, as we see nothing
negative.
Thus there is no question about the $\gamma$-positivity
(Foata-Sch\"uzenberger).
Moreover, the transformed grammar
lends a new perspective on the combinatorial interpretation
of the $\gamma$-coefficients.

Based on the grammar, we find that
the increasing binary tree and the   increasing
plane tree settings seem to be more convenient than the
permutation setting to deal with the $\gamma$-positivity.

To be more precise, the Foata-Strehl group action and
its modified versions
can be better visualized on trees,
see [C.-Fu-Yan, 2023].
\end{frame}

\begin{frame}

This argument can be pushed forward to deduce the
$e$-positivity of the trivariate generating function $C_n(x,y,z)$
associated with three statistics of Stirling permutations
introduced by Gessel and Stanley [C.-Fu-2022]. These polynomials
were introduced by Dumont, and are called the trivariate
second-order Eulerian polynomials. They are generated by
the grammar
\[ \{x\rightarrow xyz, \quad y\rightarrow xyz, \quad z\rightarrow xyz \},\]
as presented by Dumont (1980). A refined recurrence was given by Haglund and Visontai (2012).

In addition to the numbers of ascents and descents, B\'ona independently
introduced
the notion of a plateau in a Stirling permutation and showed that
all the three statistics obey the same distribution.





\end{frame}

\begin{frame}


Here is an interesting story. Ma stumbled on a paper of
Dumont in French, and thanks to the machine translation,
he realized that
the notion of a plateau  in a Stirling permutation
defined by B\'ona coincides with the statistic defined by
Dumont under the name of a repetition (in French, of course).

It might be possible that grammars can be helpful in the  further
studies of positivity questions associated with combinatorial structures
admitting context-free constructions.

\end{frame}



\begin{frame}{Up-down runs of permutations}

It seems to be an ever-lasting topic in enumerative combinatorics
to inspect the number
of up-down runs of a permutation. Roughly speaking,
the number of up-down runs equals the number of
turning points. In particular, alternating permutations
are a special class of permutations with a fixed number of up-down runs.
Given a permutation $\sigma=\sigma_1\sigma_2\cdots \sigma_n$ of $[n]$,
assume  $\sigma_0=0$, that is, a zero is patched at the beginning.
An up-down run of $\sigma$ is
a maximal segment
that is either increasing or decreasing.
For example, the permutation $3\,  7\,  5\,  8\,  6\, 1\,   4\,  9\,  2 $
has six up-down runs:
\[ 0\  3\  7\ , \; 7\  5, \; 5\  8, \; 8\  6\ 1, \; 1\   4\  9, \; 9\  2.\]

\end{frame}

\begin{frame}


Here is the grammar for up-down runs found by Ma:
\[     G=\{a \rightarrow ax, \;\, x \rightarrow xy, \;\, y\rightarrow x^2\},
\]



As expected, one can carry out the grammatical calculus to derive the
generating function, denoted by {\color{blue} $\Lambda(x,t)$},
in our proposed notation. This
has been done by [C.-Fu, 2023].
In the traditional way, as the first step,
one tries to establish a recurrence
relation by a ``clever counting'', as Professor Stanley would have put it. Even if this is done,
we are left with the tasks of setting up and solving an equation.

Here we don't intend to compare the grammatical fantasy
with the classical strategies, and I am inclined to stick
to the belief that

--- Sometimes the old ways are the best. --- Skyfall

\end{frame}

\begin{frame}{Grammar assisted bijections}



Apart from  the grammatical
calculus, we find that a grammar can be helpful in constructing
bijections and it can serve as a guide to discover something new.

It is well-known that the Euler number $E_{2n}$ can be
interpreted in terms of alternating permutations
and even increasing trees.
A.G. Kuznetsov, I.M. Pak and A.E. Postnikov have given a bijection.
We [C.-Fu, 2017]
extended this bijection to incorporate the number of left peaks.
Our construction is somehow rather
technical and we find it  more and more difficult
to remember.

\end{frame}



\begin{frame}


With the grammar in hand, we were much better off and
were able to build  a natural correspondence
which maps several permutation statistics involving up-down runs and
 peaks to tree statistics involving
 the parity of the number of children of each vertex.
 {\color{blue} The theorems are eliminated here.}

The trick can be described as a reflection principle. Hopefully, we have
hunted a most wanted correspondence  between permutations and
increasing trees that can be restricted to alternating permutations and
even increasing trees.

In summary, if a suitable grammar is at disposal and if we were
lucky, it
  may happen
that this very grammar can solve everything all at once.
\end{frame}





\begin{frame}{Dominique Dumont}


Professor Dominique Dumont was a great advocate of grammars and
made a number of remarkable discoveries. What I found the
most striking is the grammar for the Ramanujan polynomials,
in connection with  Shor's refinement of the classical
formula of Cayley.

I never had the pleasure of meeting Professor Dominique Dumont.
To show my appreciation, I expressed my wish to invite him
for a visit.
He kindly accepted the invitation and even made a plan. But, sadly,
it was a profound regret that he didn't make it.
Now, all there is to say is that
his mathematics remains to bring me joy and happiness.


\end{frame}

\begin{frame}{The Ramanujan polynomials}

When speaking of Ramanujan,
it is hard to connect him to
the enumeration of trees.
He may not have been aware of what he had done in combinatorial terms.
In the monumental edition of Ramanujan's Second Notebooks,
compiled   by B. C. Berndt, R. J. Evans and B. M. Wilson,
the Ramanujan polynomials have  ultimately found a permanent residence
accessible to combinatorialists.

J. Zeng should be attributed for observing the connection
between the Ramanujan polynomials and Shor's interpretation.
\end{frame}

\begin{frame}

This relationship brings the grammatical calculus to the territory
of  rooted trees and Abel-type identities.
We shall demonstrate how a grammar can be
employed to deal with an Abel-type identity arising
from the theory of machine learning.

Once we have the grammar in place, the identity
turns out to be   a disguise of the Leibniz formula.
This conjectural identity has
attracted quite a few combinatorialists to try
their hands from different angles.
\end{frame}

\begin{frame}

To my surprise,  this is not the end of the story.
One day, I was contacted by my friend Professor  J. Zhou at
Tsinghua University, a geometer,
about the Ramanujan polynomials and something strange to me,
such as the orbifold Euler characteristics of the
moduli spaces of stable curves.
While being astonished, I responded with the question of
how he could have the faintest idea of something in our trade.
His answer was comforting: He tried his luck with
the Online Encyclopedia of Integer
Sequences (OEIS), and the search result  put us on a common ground.
Later on, it came to my mind that this was probably a hint
that I should make a donation to the
Foundation.




\end{frame}

\begin{frame}{A question}

As to the Ramanujan polynomials, Shor asked a question
of giving a combinatorial interpretation of a recurrence relation.
Victor Guo and I worked out a rather tedious  bijection. We knew that
it was not the one we were looking for. Then  Guo went on to find
a simpler construction. Yet, I still prefer to see something simple,
not just simpler.
\end{frame}


\begin{frame}{The Ramanujan polynomials $R_n(q)$}

\begin{block}{Definition}
Set $R_1(q)=1$. For $n\geq 1$, define
\begin{equation}
 R_{n+1}(q)=n(1+q)R_{n}(q)+q^2R_{n}'(q),
\end{equation}
\end{block}

Of course, they are not just motivated by a recurrence relation.
For example,
\[ R_1(q) =1,\quad
R_2(q) =1+q, \quad
R_3(q) =3q^2 + 4q + 2 ,\]
\[
R_4(q) =15q^3 + 25q^2 + 18q + 6 .\]



\end{frame}



\begin{frame}{Positivity properties}

\begin{itemize}
\item  {\color{blue} [C.-Wang-Yang, 2011]} The Ramanujan polynomials $R_n(q)$ are strongly $q$-log-convex, that is,
\[R_{m-1}(q)R_{n+1}(q)\geq_q R_{m}(q)R_{n}(q)\]
for all $n\geq m\geq 1$, where $f(q)\geq_q g(q)$ means that  the difference $f(q)-g(q)$ has nonnegative coefficients as a polynomial of $q$.

\item  {\color{blue} [A.D. Sokal, 2021]} The Hankel matrix $(R_{i+j}(q))_{i,j\geq 0}$ associated with the Ramanujan polynomials $R_n(q)$ is {\color{blue} coefficientwise totally positive} (that is, all its minors of this Hankel matrix are polynomials with nonnegative coefficients.)

\end{itemize}


\end{frame}




\begin{frame}{Shor's refinement of Cayley's formula}
 \begin{block}{Theorem (Shor)}
Let $T_n$ denote the set of
rooted trees on $[n]$, and let
${\rm imp}(T)$ denote the number of improper edges of a rooted tree $T$. Then
\[R_n(q)=\sum_{T \in T_n} q^{{\rm imp}(T)}\]
\end{block}

An edge $(u,v)$ with $u$ being the parent and $v$ being a child
is said to be improper if there exists a descendant of $v$ that is smaller than $u$,
under the assumption that
any vertex of $T$ is considered as a descendant of itself, or equivalently,
$(u,v)$ is said to be proper if all the vertices in the subtree rooted
at $v$ are greater than $u$.

\end{frame}




\begin{frame}{The grammar of Dumont and Ramanonjisoa }
Dumont and Ramamonjisoa (1996) introduced the following grammar
for the enumeration of rooted trees with a given number of
improper edges:
\[
G=\{   A\rightarrow A^3S,\quad S\rightarrow AS^2 \}.\]
Let $D$ denote the formal derivative with respect to the grammar $G$.

 \begin{block}{Theorem (Dumont and Ramanonjisoa)}  For $n\geq1$,
  \begin{equation*}
    D^{n-1}(AS)=A^nS^{n}\sum_{T \in T_n} A^{{\rm imp}(T)}=A^nS^{n}R_n(q).
  \end{equation*}
\end{block}


\end{frame}



\begin{frame}

Dumont and Ramamonjisoa gave a proof
via the recurrence relation  of Shor.
  We found a combinatorial interpretation in terms of
 a grammatical labeling [C.-Yang,  2021].
Instead of elaborating on the definition of the grammatical labeling,
we only offer  a snapshot to show how it looks, where an improper edge
is represented by a double edge:
\begin{figure}[htp]
\centering
\begin{tikzpicture}[scale=1.0]
\node [tn,label=0:$0$](zero){}[grow=down]
	[sibling distance=18mm,level distance=12mm]
    child {node [tn,label=0:{$4(S)$}](four){}
        child {node [tn,label=180:{$1(S)$}](one){}
	       child{node [tn,label=-90:{$3(S)$}](three){}
                edge from parent
                    node[left ]{}
            }}
        child {node [tn,label=0:{$2(S)$}](two){}}
        edge from parent
            node[left ]{}
        };
\draw [double](four)--node[left=2pt]{}(one);
\draw[double](four)--node[right=2pt]{}(two);
\coordinate[label=above left:{$A$}] (x) at ($(one)!.46!(four)$);
\coordinate[label=below right:{$A$}] (x) at ($(one)!.5!(four)$);
\coordinate[label=below left:{$A$}] (x) at ($(two)!.46!(four)$);
\coordinate[label=above right:{$A$}] (x) at ($(two)!.5!(four)$);
\coordinate[label=right:{$A$}] (x) at ($(zero)!.5!(four)$);
\coordinate[label=right:{$A$}] (x) at ($(one)!.5!(three)$);
\end{tikzpicture}
\caption{The weight of $T$ is $\omega(T)=A^6S^4$.}
\end{figure}
\end{frame}




\begin{frame}{The Lacasee identity}


The Dumont-Ramamonjisoa grammar reveals that
rooted trees can be recursively constructed via local (or context-free)
operations. The grammatical labeling can be thought as a
description of the concrete procedure.

Next, we present an application of the   Dumont-Ramamonjisoa grammar (C.-Yang, 2021).

\begin{block}{Theorem (Lacasse)}
\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*}
  \end{block}


\end{frame}


\begin{frame}

This was conjectured by Lacasse
in the study of the  theory of machine learning. Since then, several proofs have been found.
\begin{itemize}
 \item Y. Sun (2013),  using the umbral calculus;
 \item  Prodinger (2013), using Cauchy's integral formula;
 \item  Chen, Peng and Yang (2013),  a combinatorial interpretation;
  \item  Gessel (2016), using the Lagrange inversion formula.
\end{itemize}
 \end{frame}

  \begin{frame}

Rewrite it as
\begin{equation*}
n^n=\sum_{j=1}^n\sum_{k=0}^{n-j}\binom{n-1}{j-1}\binom{n-j}{k}j^{j-1}k^k(n-k-j)^{n-k-j}.
\end{equation*}
Since $D(A)=A^3S$, we have the convolution formula
\begin{equation*}
D^{n}(A)=D^{n-1}(A^3S)=\sum_{i+j+k=n}\binom{n-1}{i,j-1,k}D^{i}(A)D^{j-1}(AS)D^{k}(A),
\end{equation*}
in accordance with what we are seeking, owing to the following facts
\begin{eqnarray*}
D^{n-1}(AS)|_{A=S=1} & = & n^{n-1} ,\\
  D^{n-1}(A)|_{A=S=1} & = & n^n.
   \end{eqnarray*}




\end{frame}





\begin{frame}
    It is probably the time for myself to ask a question.
    Usually, at certain point during my lecture
    I would ask my students whether they wanted to hear more.
    I always got a ``No'' without ``Thank you''.

    The late Professor S. S. Chern once
    said something like the highlight of a meeting comes
    at the moment of making an
    announcement that everyone is looking forward to.

    Now, here it is.

\end{frame}



\begin{frame}


\centering
\includegraphics[scale=0.30]{Thank-you-end.png}

\end{frame}



\end{document}


As observed by B\'ona, the generating function can be deduced from
a formula of David-Barton and an equivalent formula
was obtained by
Stanley   in regard with
permutations of $[n]$ having a given length of
the longest alternating subsequences.