% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} \usepackage{xspace} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \def\red{\textcolor{red} } \def\l{\ell} \def\w{w} \def\cop{cyclically ordered partition\xspace} \def\cops{cyclically ordered partitions\xspace} \def\u{\ensuremath{\mathcal U}\xspace} \newtheorem{theorem}{Theorem}%[section] \newtheorem{cor}[theorem]{Corollary} \newtheorem{prop}[theorem]{Proposition} \newtheorem{conj}[theorem]{Conjecture} \newtheorem{remark}[theorem]{Remark} \newtheorem{question}[theorem]{Question} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{definition}[theorem]{Definition} \newtheorem{ex}[theorem]{Example} \newcommand{\sech}{\ensuremath{\mathrm{sech\ }}} \newcommand{\mcb}{\mathfrak{C}_8} \newcommand\mm{{\rm mod\ }} \newcommand{\sn}{{\rm sn\,}} \newcommand{\cn}{{\rm cn\,}} \newcommand{\dn}{{\rm dn\,}} \newcommand{\pk}{{\rm pk\,}} \newcommand{\val}{{\rm val\,}} \newcommand{\lpk}{{\rm pk^{\emph{l}}\,}} \newcommand{\open}{{\rm open\,}} \newcommand{\close}{{\rm close\,}} \newcommand{\des}{{\rm des\,}} \newcommand{\ades}{{\rm ades\,}} \newcommand{\OP}{\textmd{OP}} \newcommand{\man}{\mathfrak{A}_n} \newcommand{\ma}{\mathfrak{A}_1} \newcommand{\mb}{\mathfrak{A}_2} \newcommand{\mc}{\mathfrak{A}_3} \newcommand{\msb}{\mathfrak{S}_8} \newcommand{\msk}{\mathfrak{S}_k} \newcommand{\mcn}{\mathfrak{C}_{2n}} \newcommand{\mcnn}{\mathfrak{C}_{2n+1}} \newcommand{\msn}{\mathfrak{S}_n} \newcommand{\msnn}{\mathfrak{S}_{2n}} \newcommand{\ud}{{\rm ud\,}} \newcommand{\as}{{\rm as\,}} \newcommand{\bn}{{\rm\bf n}} \newcommand{\rz}{{\rm RZ}} \newcommand{\lrf}[1]{\lfloor #1\rfloor} \newcommand{\lrc}[1]{\lceil #1\rceil} \newcommand{\sep}{\preceq} \newcommand{\Eulerian}[2]{\genfrac{<}{>}{0pt}{}{#1}{#2}} \newcommand{\Stirling}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Some combinatorial arrays related to the Lotka-Volterra system} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{David Callan\\ \small Department of Statistics\\[-0.8ex] \small University of Wisconsin-Madison\\[-0.8ex] \small Madison, WI 53706.\\ \small\tt callan@stat.wisc.edu\\ \and Shi-Mei~Ma\thanks{The second author is responsible for all the communications and he was supported by NSFC (11401083), the Fundamental Research Funds for the Central Universities (N130423010), the Research Foundation for Science and Technology Pillar Program of Northeastern University at Qinhuangdao (XNK201303) and the Natural Science Foundation of Hebei Province (A2013501070).}\\ \small School of Mathematics and Statistics\\[-0.8ex] \small Northeastern University at Qinhuangdao\\[-0.8ex] \small Hebei 066004, P.R. China.\\ \small\tt shimeimapapers@163.com\\ \and Toufik Mansour\\ \small Department of Mathematics\\[-0.8ex] \small University of Haifa\\[-0.8ex] \small 3498838 Haifa, Israel\\ \small\tt tmansour@univ.haifa.ac.il} % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{}{}\\ \small Mathematics Subject Classifications: 05A05, 05A18} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} The purpose of this paper is to investigate several context-free grammars suggested by the Lotka-Volterra system. Some combinatorial arrays, involving the Stirling numbers of the second kind and Eulerian numbers, are generated by these context-free grammars. In particular, we present grammatical characterization of some statistics on cyclically ordered partitions. % keywords are optional \bigskip\noindent \textbf{Keywords:} Lotka-Volterra system; Context-free grammars; Cyclically ordered partitions; Eulerian numbers \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Throughout this paper a context-free grammar is in the sense of Chen~\cite{Chen93}: for an alphabet $A$, let $\mathbb{Q}[[A]]$ be the rational commutative ring of formal power series in monomials formed from letters in $A$. A context-free grammar over A is a function $G: A\rightarrow \mathbb{Q}[[A]]$ that replace a letter in $A$ by a formal function over $A$. The formal derivative $D$ is a linear operator defined with respect to a context-free grammar $G$. More precisely, the derivative $D=D_G$: $\mathbb{Q}[[A]]\rightarrow \mathbb{Q}[[A]]$ is defined as follows: for $x\in A$, we have $D(x)=G(x)$; for a monomial $u$ in $\mathbb{Q}[[A]]$, $D(u)$ is defined so that $D$ is a derivation, and for a general element $q\in\mathbb{Q}[[A]]$, $D(q)$ is defined by linearity. Let $[n]=\{1,2,\ldots,n\}$. The {\it Stirling number of the second kind} $\Stirling{n}{k}$ is the number of ways to partition $[n]$ into $k$ blocks. Let $\msn$ be the symmetric group of all permutations of $[n]$. A {\it descent} of a permutation $\pi\in\msn$ is a position $i$ such that $\pi(i)>\pi(i+1)$. Denote by $\des(\pi)$ the number of descents of $\pi$. The {\it Eulerian number} $\Eulerian{n}{k}$ is the number of permutations in $\msn$ with $k-1$ descents, where $1\leq k\leq n$ (see~\cite[A008292]{Sloane}). Let us now recall two classical results. \begin{prop}[{\cite[Eq. 4.8]{Chen93}}] For $A=\{x,y\}$ and $G=\{x\rightarrow xy, y\rightarrow y\}$, we have \begin{equation*} D^n(x)=x\sum_{k=1}^n\Stirling{n}{k}y^k\quad\textrm{for $n\ge 1$}. \end{equation*} \end{prop} \begin{prop}[{\cite[Section 2.1]{Dumont96}}]\label{Dumont96:01} For $A=\{x,y\}$ and $G=\{x\rightarrow xy, y\rightarrow xy\}$, we have \begin{equation*} D^n(x)=\sum_{k=1}^{n}\Eulerian{n}{k}x^{k}y^{n-k+1}\quad\textrm{for $n\ge 1$}. \end{equation*} \end{prop} One of the most commonly used models of two species predator-prey interaction is the classical {\it Lotka-Volterra system}: \begin{equation}\label{Lotka-Volterra-model} \frac{dx}{dt}=x(a-by), \frac{dy}{dt}=y(-c+dx), \end{equation} where $y(t)$ and $x(t)$ represent, respectively, the predator population and the prey population as functions of time, and $a,b,c,d$ are positive constants. %In general, %an $n$-th order {\it Lotka-Volterra system} takes the form %\begin{equation}\label{Lotka-Volterra-model-2} %\frac{dx_i}{dt}=\lambda_ix_i+x_i\sum_{j=1}^nM_{i,j}x_j, i=1,2,\ldots,n, %\end{equation} %where $\lambda_i,M_{i,j}$ are real constants. The differential system~\eqref{Lotka-Volterra-model} is ubiquitous and arises often in mathematical ecology, dynamical system theory and other branches of mathematics (see~\cite{Allen07,Chauvet02}). Motivated by~\eqref{Lotka-Volterra-model}, we shall consider context-free grammars of the form: \begin{equation}\label{Context:01} A=\{x,y\},~G=\{x\rightarrow x+p(x,y), y\rightarrow y+q(x,y)\}, \end{equation} where $p(x,y)$ and $q(x,y)$ are polynomials in $x$ and $y$. For convenience, we shall call $$G'=\{x\rightarrow p(x,y), y\rightarrow q(x,y)\}$$ the ancestor of $G$. This paper is a continuation of~\cite{Chen93,Dumont96,Ma1302}. Throughout this paper, arrays are indexed by $n,i$ and $j$. Call $(a_{n,i,j})$ a combinatorial array if the numbers $a_{n,i,j}$ are nonnegative integers. For any function $H(x,p,q)$, we denote by $H_y$ the partial derivative of $H$ with respect to $y$, where $y\in\{x,p,q\}$. In the next section, we present grammatical characterization of some statistics on cyclically ordered partitions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Some permutation statistics on cyclically ordered partitions}\label{sec:02} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Recall that a partition $\pi$ of $[n]$, written $\pi\vdash [n]$, is a collection of disjoint and nonempty subsets $B_1,B_2,\ldots,B_k$ of $[n]$ such that $\bigcup_{i=1}^kB_i=[n]$, where each $B_i$ ($1\leq i\leq k$) is called a block of $\pi$. A {\it cyclically ordered partition} of $[n]$ is a partition of $[n]$ whose blocks are endowed with a cyclic order. We always use a {\it canonical representation} for cyclically ordered partitions, where the block containing 1 comes first and the integers in each block are in increasing order. For example, $(123),~(12)(3),~(13)(2),~(1)(23),~(1)(2)(3),~(1)(3)(2)$ are all cyclically ordered partitions of $[3]$. The {\it opener} of a block is its least element. For example, the list of openers of $(13)(2)$ and $(1)(3)(2)$ are respectively given by $12$ and $132$. In this section, we shall study some statistics on the list of openers. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Descent statistic} %\hspace*{\parindent} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \hspace*{\parindent} Consider the grammar \begin{equation}\label{Grammar:01} G=\{x\rightarrow x+xy, y\rightarrow y+xy\}. \end{equation} The combinatorial context for the ancestor $G'$ of $G$ has been given in Proposition~\ref{Dumont96:01}. From~\eqref{Grammar:01}, we have \begin{equation*} \begin{split} D(x)&=x+xy,\\ D^2(x)&=x+3xy+xy^2+x^2y,\\ D^3(x)&=x+7xy+6xy^2+xy^3+6x^2y+4x^2y^2+x^3y. \end{split} \end{equation*} For $n\geq 0$, we define $D^n(x)=\sum_{i\geq1,j\geq 0}a_{n,i,j}x^iy^j$. Since \begin{align*} D^{n+1}(x)&=D\left(\sum_{i,j}a_{n,i,j}x^iy^j\right)\\ &=\sum_{i,j}(i+j)a_{n,i,j}x^{i}y^{j}+\sum_{i,j}ia_{n,i,j}x^{i}y^{j+1}+\sum_{i,j}ja_{n,i,j}x^{i+1}y^{j}, \end{align*} we get \begin{equation}\label{eq:anij} a_{n+1,i,j}=(i+j)a_{n,i,j}+ia_{n,i,j-1}+ja_{n,i-1,j} \end{equation} for $i,j\geq 1$, with the initial conditions $a_{0,i,j}$ to be $1$ if $(i,j)=(1,0)$, and to be $0$ otherwise. Clearly, $a_{n,1,0}=1$ and $a_{n,i,0}=0$ for $i\geq 2$. \begin{ex} The following table contains the values of $a_{4,i,j}$.\\ \begin{tabular}{|p{2.0in}|c|c|c|c|c|} \hline \centering \textbf{$a_{4,i,j}$} & $j=0$ &$j=1$&$j=2$ &$j=3$&$j=4$\\ \hline \centering $i=1$ & 1 & 15&25&10&1\\ \centering $i=2$ & 0& 25&40 &11&0\\ \centering $i=3$ & 0& 10&11 &0&0\\ \centering $i=4$ & 0& 1&0 &0&0\\ \hline \end{tabular} \end{ex} Define $$A=A(x,p,q)=\sum_{n,i,j\geq0}a_{n,i,j}\frac{x^{n}}{n!}p^iq^j.$$ We now present the first main result of this paper. \begin{theorem}\label{mainthm:01} The generating function $A$ is given by $$A=\frac{p(p-q)e^x}{p-qe^{(p-q)(e^x-1)}}.$$ Moreover, for all $n,i,j\geq1$, \begin{equation}\label{Explicit:anij} a_{n,i,j}=\Stirling{n+1}{i+j}\Eulerian{i+j-1}{i}. \end{equation} \end{theorem} \begin{proof} By rewriting~\eqref{eq:anij} in terms of generating function $A$, we have \begin{equation}\label{eq:Axpq} A_x=p(1+q)A_p+q(1+p)A_q. \end{equation} It is routine to check that the generating function $$\widetilde{A}(x,p,q)=\frac{p(p-q)e^x}{p-qe^{(p-q)(e^x-1)}}$$ satisfies (\ref{eq:Axpq}). Also, this generating function gives $\widetilde{A}(0,p,q)=p$, $\widetilde{A}(x,p,0)=pe^x$ and $\widetilde{A}(x,0,q)=0$ with $q\neq0$. Hence, $A=\widetilde{A}$. Now let us prove that $a_{n,i,j}=\Stirling{n+1}{i+j}\Eulerian{i+j-1}{i}$. Note that \begin{align*} \frac{d}{dx}\sum_{n,i,k\geq0}a_{n,i,k+1-i}\frac{x^{n+1}}{(n+1)!}v^{i+1}w^k &=v\frac{d}{dx}\sum_{k\geq0}\left(\sum_{n\geq k+1}\Stirling{n+1}{k+1}\frac{x^{n+1}}{(n+1)!}\sum_{i=0}^k\Eulerian{k}{i}v^i\right)w^k\\ &=v\frac{d}{dx}\sum_{k\geq0}\left(\sum_{i=0}^k\Eulerian{k}{i}v^i\right)\frac{(e^x-1)^{k+1}}{(k+1)!}w^k. \end{align*} By using the fact that $$\sum_{k\geq0}\left(\sum_{i=0}^k\Eulerian{k}{i}p^i\right)u^k=\int_0^u\frac{p-1}{p-e^{u'(p-1)}}du'= \frac{1}{p}(u(p-1)-\ln(e^{u(p-1)}-p)+\ln(1-p)),$$ we obtain that \begin{align*} v\frac{d}{dx}\sum_{n,i,k\geq0}a_{n,i,k+1-i}\frac{x^{n+1}}{(n+1)!}v^iw^k &=\frac{wv(v-1)e^x}{v-e^{(e^x-1)w(v-1)}}, \end{align*} which implies \begin{align*} A(x,vw,w)=\frac{wv(v-1)e^x}{v-e^{(e^x-1)w(v-1)}}, \end{align*} as required. \end{proof} Let $a_n=\sum_{i\geq1,j\geq 0}a_{n,i,j}$. Clearly, $a_n=\sum_{k= 0}^nk!\Stirling{n+1}{k+1}$. \begin{prop} $\Stirling{n}{k} \Eulerian{k-1}{i}$ is the number of cyclically ordered partitions of $[n]$ with $k$ blocks whose list of openers contains $i-1$ descents. \end{prop} Proof. To form such a cyclically ordered partition, start with a partition of $[n]$ into $k$ blocks in canonical form, each block increasing and blocks arranged in order of increasing first entries (there are $\Stirling{n}{k}$ choices). The first opener is thus 1. Then leave the first block in place and rearrange the $k-1$ remaining blocks so that their openers, viewed as a list, contain $i-1$ descents (there are $\Eulerian{k-1}{i}$ choices). We can now conclude the following corollary from the discussion above. \begin{cor}\label{openers-descents} For all $n,i,j\geq1$, $a_{n,i,j}$ is the number of cyclically ordered partitions of $[n+1]$ with $i+j$ blocks whose list of openers contains $i-1$ descents. \end{cor} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Peak statistics} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \hspace*{\parindent} The idea of a peak (resp.~valley) in a list of integers $(\w_i)_{i=1}^n$ is an entry that is greater (resp.~smaller) than its neighbors. The number of peaks in a permutation is an important combinatorial statistic. See, e.g.,~\cite{Aguiar04,Dilks09,Francon79,Ma121} and the references therein. However, the question of whether the first and/or last entry may qualify as a peak (or valley) gives rise to several different definitions. In this paper, we consider only left peaks and right valleys. A {\it left peak index} is an index $i\in[n-1]$ such that $\w_{i-1}<\w_{i}>\w_{i+1}$, where we take $\w_0=0$, and the entry $\w_i$ is a {\it left peak}. Similarly, a {\it right valley} is an entry $\w_i$ with $i\in[2,n]$ such that $\w_{i-1}>\w_{i}<\w_{i+1}$, where we take $\w_{n+1}=\infty$. Thus the last entry may be a right valley but not a left peak. For example, the list $64713258$ has 3 left peaks and 3 right valleys. Clearly, left peaks and right valleys in a list are equinumerous: they alternate with a peak first and a valley last. Peaks and valleys were considered in~\cite{Francon79}. The left peak statistic first appeared in~\cite[Definition 3.1]{Aguiar04}. Let $P(n,k)$ be the number of permutations in $\msn$ with $k$ left peaks. Let $P_n(x)=\sum_{k\geq 0}P(n,k)x^k$. It is well known~\cite[A008971]{Sloane} that \begin{eqnarray*} % \nonumber to remove numbering (before each equation) P(x,z) &=&1+ \sum_{n\geq 1}P_n(x)\frac{z^n}{n!}\\ &=& \frac{\sqrt{1-x}}{\sqrt{1-x}\cosh(z\sqrt{1-x})-\sinh(z\sqrt{1-x})} \end{eqnarray*} Let $D$ be the differential operator $\frac{d}{d\theta}$. Set $x=\sec \theta$ and $y=\tan \theta$. Then \begin{equation*}\label{tansec} D(x)=xy,D(y)=x^2. \end{equation*} Furthermore, if $G'=\{x\rightarrow xy, y\rightarrow x^2\}$, then $$D^n_{G'}(x)=\sum_{k=0}^{\lrf{\frac{n}{2}}}P(n,k)x^{2k+1}y^{n-2k}\quad\textrm{for $n\ge 1$},$$ which was given in~\cite[Section 2]{Ma121}. There is a large literature devoted to the repeated differentiation of the secant and tangent functions (see \cite{Franssens07,Hoffman99,Ma121,Ma13} for instance). Consider the grammar \begin{equation}\label{Grammar:02} G=\{x\rightarrow x+xy, y\rightarrow y+x^2\}. \end{equation} From~\eqref{Grammar:02}, we have \begin{equation*} \begin{split} D(x)&=x+xy,\\ D^2(x)&=x+3xy+xy^2+x^3,\\ D^3(x)&=x+7xy+6xy^2+xy^3+6x^3+5x^3y. \end{split} \end{equation*} Define $$D^n(x)=\sum_{i\geq1,j\geq 0}b_{n,i,j}x^iy^j.$$ Since \begin{align*} D^{n+1}(x)&=D\left(\sum_{i\geq1,j\geq 0}b_{n,i,j}x^iy^j\right)\\ &=\sum_{i,j}(i+j)b_{n,i,j}x^{i}y^{j}+\sum_{i,j}ib_{n,i,j}x^{i}y^{j+1}+ \sum_{i,j}jb_{n,i,j}x^{i+2}y^{j-1}, \end{align*} we get \begin{equation}\label{eq:bnij} b_{n+1,i,j}=(i+j)b_{n,i,j}+ib_{n,i,j-1}+(j+1)b_{n,i-2,j+1} \end{equation} for $i\geq 1$ and $j\geq 0$, with the initial conditions $b_{0,i,j}$ to be $1$ if $(i,j)=(1,0)$, and to be $0$ otherwise. Clearly, $b_{n,1,0}=1$ for $n\geq 1$. \begin{ex} The following table contains the values of $b_{4,i,j}$.\\ \begin{tabular}{|p{2.0in}|c|c|c|c|c|} \hline \centering \textbf{$b_{4,i,j}$} & $j=0$ &$j=1$&$j=2$ &$j=3$&$j=4$\\ \hline \centering $i=1$ & 1 & 15&25&10&1\\ \centering $i=3$ & 25& 50&18&0&0\\ \centering $i=5$ & 5& 0&0 &0&0\\\hline \end{tabular} \end{ex} Define $$B=B(x,p,q)=\sum_{n,i,j\geq0}b_{n,i,j}p^iq^j\frac{x^n}{n!}.$$ We now present the second main result of this paper. \begin{theorem}\label{mainthm:02} The generating function $B$ is given by $$B(x,p,q)=\frac{p\sqrt{q^2-p^2}e^x}{\sqrt{q^2-p^2}\cosh(\sqrt{q^2-p^2}(e^x-1))-q\sinh(\sqrt{q^2-p^2}(e^x-1))}.$$ Moreover, for all $n,i,j\geq1$, \begin{equation}\label{Explicit:bnij} b_{n,2i-1,j}=\Stirling{n+1}{2i-1+j}P(2i-2+j,i-1). \end{equation} \end{theorem} \begin{proof} The recurrence~\eqref{eq:bnij} can be written as \begin{equation}\label{eq:Bxpq} B_x=p(1+q)B_p+(p^2+q)B_q. \end{equation} It is routine to check that the generating function $$\widetilde{B}=\widetilde{B}(x,p,q)=\frac{p\sqrt{q^2-p^2}e^x}{\sqrt{q^2-p^2}\cosh(\sqrt{q^2-p^2}(e^x-1))-q\sinh(\sqrt{q^2-p^2}(e^x-1))}$$ satisfies~\eqref{eq:Bxpq}). Also, this generating function gives $\widetilde{B}(0,p,q)=p$ and $\widetilde{B}(x,0,q)=0$. Hence, $B=\widetilde{B}$. It follows from~\eqref{eq:bnij} that $b_{n,2i,j}=0$ for all $(i,j)\neq (0,0)$. Now let us prove that $$b_{n,2i-1,j}=\Stirling{n+1}{2i-1+j}P(2i-2+j,i-1).$$ Note that \begin{align*} \sum_{n,i,j\geq0}b_{n,i,j+1-2i}p^iq^j\frac{x^n}{n!}&=\sum_{n\geq0,i,j\geq1}b_{n,2i-1,j+1-2i}p^iq^j\frac{x^n}{n!}=p\sum_{n\geq0,j\geq1}\Stirling{n+1}{j}P_{j-1}(p)q^j\frac{x^n}{n!}\\ &=pe^x\sum_{j\geq1}\frac{(e^x-1)^{j-1}}{(j-1)!}P_{j-1}(p)q^j=pqe^xP(p,q(e^x-1)), \end{align*} Hence, \begin{equation*} \sum_{n,i,j\geq0}b_{n,i,j}p^iq^j\frac{x^n}{n!}=pe^xP(p^2/q^2,q(e^x-1))=B(x,p,q), \end{equation*} as required. \end{proof} Let $b_n=\sum_{i\geq1,j\geq 0}b_{n,i,j}$. It follows from~\eqref{Explicit:bnij} that $b_n=a_n$. In the following discussion, we shall present a combinatorial interpretation for $b_{n,i,j}$. %Along the same lines as Corollary~\ref{openers-descents}, we now get a combinatorial interpretation for $b_{n,i,j}$. \begin{lemma} \label{insert} Suppose that $(\w_i)_{i=1}^k$ is a list of distinct integers containing $\ell$ right valleys and that $\w_1=1$. Then, among the $k$ ways to insert a new entry $m>\max(\w_i)$ into the list in a noninitial position, $2\ell+1$ of them will not change the number of right valleys and $k-(2\ell+1)$ will increase it by 1. \end{lemma} Proof. As observed above, peaks and valleys alternate, a peak occurring first, and a valley occurring last. Thus there are $\l$ peaks. If $m$ is inserted immediately before or after a peak or at the very end, the number of valleys is unchanged, otherwise it is increased by 1. \begin{prop} The number $u_{n,k,\l}$ of \cops on $[n]$ with $k$ blocks and $\l$ right valleys in the list of openers satisfies the recurrence \begin{equation}\label{eq:recurrenceu} u_{n,k,\l} = k u_{n-1,k,\l} + (2\l+1)u_{n-1,k-1,\l} + (k-2\l)u_{n-1,k-1,\l-1} \end{equation} for $n\ge 2,\ \l \ge 0, \ 2\l+1 \le k \le n$. \end{prop} Proof. Each \cop of size $n$ is obtained by inserting $n$ into one of size $n-1$, either as the last entry in an existing block or as a new singleton block. Let $\u_{n,k,\l}$ denote the set of \cops counted by $u_{n,k,\l}$. To obtain an element of $\u_{n,k,\l}$ we can insert $n$ into any existing block of an element of $\u_{n-1,k,\l}$ (this gives \,$k u_{n-1,k,\l}$ choices\,), or insert $n$ as a singleton block into an element of $\u_{n-1,k-1,\l}$ so that the number of right valleys is unchanged (this gives\,$(2\l+1)u_{n-1,k-1,\l}$ choices\,), or insert $n$ as a singleton block into an element of $\u_{n-1,k-1,\l-1}$ so that the number of right valleys is increased by 1 (this gives \,$(k-2\l)u_{n-1,k-1,\l-1}$ choices\,). The last two counts of choices follow from Lemma~\ref{insert}. \begin{cor} For all $n,i,j\geq1$, $b_{n,i,j}$ is the number of cyclically ordered partitions of $[n+1]$ with $i+j$ blocks and $\frac{i-1}{2}$ right valleys (equivalently, $\frac{i-1}{2}$ left peaks) in the list of openers. \end{cor} Proof. Comparing recurrence relations~\eqref{eq:bnij} and~\eqref{eq:recurrenceu}, we see that $b_{n,i,j}=u_{n+1,i+j,(i-1)/2}$. %, which explains combinatorially why $c_{n,i,j}=0$ for even $i$. \begin{remark} A cyclically ordered partition of size $n$ with $k$ blocks and $\ell$ right valleys in the list of openers is obtained by selecting a partition of $[n]$ with $k$ blocks in $\Stirling{n}{k}$ ways, and then arranging the blocks suitably, in $P(k,\ell)$ ways. Hence $u_{n,k,\l}= \Stirling{n}{k}P(k,\ell)$ and we get a combinatorial proof that $b_{n,2i-1,j}=\Stirling{n+1}{2i-1+j}P(2i-2+j,i-1)$. \end{remark} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{The longest alternating subsequences} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \hspace*{\parindent} Let $\pi=\pi(1)\pi(2)\cdots \pi(n)\in\msn$. An {\it alternating subsequence} of $\pi$ is a subsequence $\pi({i_1})\cdots \pi({i_k})$ satisfying $$\pi({i_1})>\pi({i_2})<\pi({i_3})>\cdots \pi({i_k}).$$ Let $\as(\pi)$ be the length (number of terms) of the longest alternating subsequence of $\pi$. Denote by $a_k(n)$ the number of permutations $\pi$ in $\msn$ such that $\as(\pi)=k$. The study of the distribution of the length of the longest alternating subsequences of permutations was recently initiated by Stanley~\cite{Sta08}. Let $L_n(x)=\sum_{k=0}^na_k(n)x^k$, and let \begin{equation*}\label{Txz-def} L(x,z)=\sum_{n\geq 0}L_n(x)\frac{z^n}{n!}. \end{equation*} Stanley~\cite[Theorem 2.3]{Sta08} obtained the following closed-form formula: \begin{equation*}\label{Stanley} L(x,z)=(1-x)\frac{1+\rho+2xe^{\rho z}+(1-\rho)e^{2\rho z}}{1+\rho-x^2+(1-\rho-x^2)e^{2\rho z}}, \end{equation*} where $\rho=\sqrt{1-x^2}$. Let $\pi=\pi(1)\pi(2)\cdots \pi(n)\in\msn$. We say that $\pi$ changes direction at position $i$ if either $\pi({i-1})<\pi(i)>\pi(i+1)$, or $\pi(i-1)>\pi(i)<\pi(i+1)$, where $i\in\{2,3,\ldots,n-1\}$. We say that $\pi$ has $k$ {\it alternating runs} if there are $k-1$ indices $i$ such that $\pi$ changes direction at these positions. The {\it up-down runs} of a permutation $\pi$ are the alternating runs of $\pi$ endowed with a 0 in the front. For example, the permutation $\pi=514632$ has 3 alternating runs and 4 up-down runs. One can easily verify that $a_k(n)$ also counts permutations in $\msn$ with $k$ up-down runs. It follows from~\cite[Corollary 8]{Ma1303} that \begin{equation}\label{Ma} L(x,z)=-\sqrt{\frac{x-1}{x+1}}\left(\frac{\sqrt{x^2-1}+x\sin(z\sqrt{x^2-1})}{1-x\cos(z\sqrt{x^2-1})}\right). \end{equation} Set $P_0(x)=L_0(x)=1$. There is a closely connection between the polynomials $P_n(x)$ and $L_n(x)$ (see~\cite[Corollary 7]{Ma1303}): $$L_{n+1}(x)=x\sum_{k=0}^n\binom{n}{k}L_k(x)P_{n-k}(x^2).$$ We now present a grammatical characterization of the numbers $a_k(n)$. \begin{prop}[{\cite[Theorem 6]{Ma1303}}]\label{Prop:runs} For $A=\{w,x,y\}$ and $G'=\{w\rightarrow wx, x\rightarrow xy, y\rightarrow x^2\}$, we have \begin{equation*} D^n_{G'}(w)=w\sum_{k=0}^na_k(n)x^ky^{n-k}. \end{equation*} \end{prop} Consider the grammar \begin{equation}\label{Grammar:03} G=\{w\rightarrow w+wx, x\rightarrow x+xy, y\rightarrow y+x^2\}, \end{equation} which is the descendant of $G'$ introduced in Proposition~\ref{Prop:runs}. From~\eqref{Grammar:03}, we have \begin{equation*} \begin{split} D(w)&=w(1+x),\\ D^2(w)&=w(1+3x+xy+x^2);\\ D^3(w)&=w(1+7x+6xy+xy^2+6x^2+3x^2y+2x^3). \end{split} \end{equation*} Define $$D^n(w)=w\sum_{i,j\geq 0}t_{n,i,j}x^{i}y^{j}.$$ Since \begin{align*} D^{n+1}(w)&=D\left(w\sum_{i,j\geq 0}t_{n,i,j}x^{i}y^{j}\right)\\ &=\sum_{i,j}(1+i+j)t_{n,i,j}x^{i}y^{j}+\sum_{i,j}t_{n,i,j}x^{i+1}y^j+ \sum_{i,j}it_{n,i,j}x^{i}y^{j+1}+ \sum_{i,j}jt_{n,i,j}x^{i+2}y^{j-1}. \end{align*} we get \begin{equation}\label{eq:tnij} t_{n+1,i,j}=(1+i+j)t_{n,i,j}+t_{n,i-1,j}+it_{n,i,j-1}+(j+1)t_{n,i-2,j+1} \end{equation} for $i,j\geq 0$ , with the initial conditions $t_{0,i,j}$ to be $1$ if $(i,j)=(0,0)$ or $(i,j)=(1,0)$, and to be $0$ otherwise. Clearly, $t_{n,0,0}=1$ for $n\geq 0$. \begin{ex} The following table contains the values of $t_{4,i,j}$.\\ \begin{tabular}{|p{2.0in}|c|c|c|c|} \hline \centering \textbf{$t_{4,i,j}$} & $j=0$ &$j=1$&$j=2$ &$j=3$\\ \hline \centering $i=0$ & 1 & 0&0&0\\ \centering $i=1$ & 15& 25&10&1\\ \centering $i=2$ & 25& 30&7 &0\\ \centering $i=3$ & 20& 11&0 &0\\ \centering $i=4$ & 5& 0&0 &0\\\hline \end{tabular} \end{ex} Define $$T=T(x,p,q)=\sum_{n,i,j\geq0}t_{n,i,j}p^iq^j\frac{x^n}{n!}.$$ We now present the following. \begin{theorem}\label{mainthm:03} The generating function $T$ is given by $$T(x,p,q)=e^x\sqrt{\frac{p-q}{p+q}}\frac{\sqrt{p^2-q^2}+p\sin((e^x-1)\sqrt{p^2-q^2})}{p\cos((e^x-1)\sqrt{p^2-q^2})-q}.$$ Moreover, for all $n\geq 1,i\geq 1$ and $j\geq0$, \begin{equation}\label{Explicit:tnij} t_{n,i,j}=\Stirling{n+1}{i+j+1}a_i(i+j). \end{equation} \end{theorem} \begin{proof} The recurrence~\eqref{eq:tnij} can be written as \begin{equation}\label{eq:Txpq} T_x=T+p(1+q)T_p+(p^2+q)T_q. \end{equation} It is routine to check that the generating function $$\widetilde{T}=\widetilde{T}(x,p,q)=e^x\sqrt{\frac{p-q}{p+q}}\frac{\sqrt{p^2-q^2}+p\sin((e^x-1)\sqrt{p^2-q^2})}{p\cos((e^x-1)\sqrt{p^2-q^2})-q}$$ satisfies~\eqref{eq:Txpq}). Also, this generating function gives $\widetilde{T}(0,p,q)=1$ and $\widetilde{T}(x,0,q)=e^x$. Hence, $T=\widetilde{T}$. Now let us prove that $t_{n,2i-1,j}=\Stirling{n+1}{i+j+1}a_i(i+j)$. Note that \begin{align*} \sum_{n,i,j\geq0}t_{n,i,j-i}p^iq^j\frac{x^n}{n!}&=\sum_{n,i,j\geq0}t_{n,i,j-i}p^iq^j\frac{x^n}{n!}=\sum_{n,j\geq0}\Stirling{n+1}{j+1}L_{j}(p)q^j\frac{x^n}{n!}\\ &=e^x\sum_{j\geq0}\frac{(e^x-1)^{j}}{(j)!}L_{j}(p)q^j=e^xL(p,q(e^x-1)), \end{align*} Hence, \begin{equation*} \sum_{n,i,j\geq0}t_{n,i,j}p^iq^j\frac{x^n}{n!}=e^xL(p/q,q(e^x-1))=T(x,p,q), \end{equation*} as required. \end{proof} Let $t_n=\sum_{i\geq1,j\geq 0}t_{n,i,j}$. It follows from~\eqref{Explicit:tnij} that $t_n=\sum_{k= 0}^nk!\Stirling{n+1}{k+1}$. Along the same lines as the proof of Corollary~\ref{openers-descents}, we get the following. \begin{cor}\label{openers-alt} For all $n\geq 1,i\geq 1$ and $j\geq0$, $t_{n,i,j}$ is the number of cyclically ordered partitions of $[n+1]$ having $i+j+1$ blocks such that the list of openers has the longest alternating subsequence of length $i$. \end{cor} %Let $f_n=\sum_{i,j\geq 0}f_{n,i,j}$. %We have %$f_n=2^na_n=2^n\sum_{k=1}^n\Eulerian{n}{k}2^k$. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Concluding remarks}\label{sec:05} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %In this section, we shall explore the combinatorial interpretations of the numbers %$a_{n,i,j},b_{n,i,j}$ and $d_{n,i,j}$. \hspace*{\parindent} In this paper, we explore some context-free grammars suggested by~\eqref{Lotka-Volterra-model}. In fact, there are many other extension of~\eqref{Lotka-Volterra-model}. For example, many authors investigated the following generalized Lotka-Volterra system (see~\cite{Ollagnier01}): \begin{equation*}\label{L-V-2} \frac{dx}{dt}=x(Cy+z), \frac{dy}{dt}=y(Az+x), \frac{dz}{dt}=z(Bx+y). \end{equation*} Consider the grammar \begin{equation*}\label{Grammar:07} G=\{x\rightarrow x(y+z), y\rightarrow y(z+x), z\rightarrow z(x+y)\}. \end{equation*} Define $$D^n(x)=\sum_{i\geq1,j\geq 0}g_{n,i,j}x^iy^jz^{n+1-i-j}.$$ By induction, one can easily verify the following: for all $n\geq 1,i\geq1$ and $j\geq0$, we have \begin{equation*} g_{n,i,0}=\Eulerian{n}{i},~ g_{n,i,n+1-i}=\Eulerian{n}{i},~ g_{n,1,j}=\Eulerian{n+1}{j+1}. \end{equation*} \section*{Acknowledgements.} The authors thank the referee for many detailed suggestions leading to a substantial improvement of this paper. %\begin{question} %Chen~\cite{Chen93} and Dumont~\cite{Dumont96} studied grammars by using a label method. %Could we along the same lines to study the grammars considered in this paper? In other words, could we find a correspondence between the words with %\end{question} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \bibliographystyle{plain} % \bibliography{myBibFile} % If you use BibTeX to create a bibliography % then copy and past the contents of your .bbl file into your .tex file \begin{thebibliography}{16} \bibitem{Aguiar04} M. Aguiar, N. Bergeron, K. Nyman. \newblock The peak algebra and the descent algebras of types $B$ and $D$. \newblock{\em Trans. Amer. Math. Soc.}, 356(7): 2781--2824, 2004. \bibitem{Allen07} L.J.S. Allen. \newblock An Introduction to Mathematical Biology. Prentice Hall, New Jersey, 2007. \bibitem{Chauvet02} E. Chauvet, J.E. Paullet, J.P. Previte, Z. Walls. \newblock A Lotka-Volterra Three-species Food Chain. \newblock {\em Math. Mag.}, 75: 243--255, 2002. \bibitem{Chen93} W.Y.C. Chen. \newblock Context-free grammars, differential operators and formal power series. \newblock {\em Theoret. Comput. Sci.}, 117: 113--129, 1993. \bibitem{Dilks09} K. Dilks, T.K. Petersen, J.R. Stembridge. \newblock Affine descents and the Steinberg torus. \newblock {\em Adv. in Appl. Math.}, 42: 423--444, 2009. \bibitem{Dumont96} D. Dumont. \newblock Grammaires de William Chen et d\'erivations dans les arbres et arborescences. \newblock {\em S\'em. Lothar. Combin.}, 37, Art. B37a: 1--21, 1996. \bibitem{Francon79} J. Fran\c{c}on and G. Viennot. \newblock Permutations selon leurs pics, creux, doubles mont\'{e}es et double descentes, nombres d'Euler et nombres de Genocchi. \newblock{\em Discrete Math.}, 28: 21--35, 1979. \bibitem{Franssens07} G. R. Franssens. \newblock Functions with derivatives given by polynomials in the function itself or a related function. \newblock {\em Anal. Math.}, 33: 17--36, 2007. \bibitem{Hoffman99} M. E. Hoffman. Derivative polynomials, Euler polynomials, and associated integer sequences. \newblock {\em Electron. J. Combin.}, 6: \#R21, 1999. \bibitem{Ma121} S.-M. Ma. \newblock Derivative polynomials and enumeration of permutations by number of interior and left peaks. \newblock {\em Discrete Math.}, 312: 405--412, 2012. \bibitem{Ma13} S.-M. Ma. \newblock A family of two-variable derivative polynomials for tangent and secant. \newblock {\em Electron. J. Combin.}, 20(1): \#P11, 2013. \bibitem{Ma1302} S.-M. Ma. \newblock Some combinatorial arrays generated by context-free grammars. \newblock{\em European J. Combin.}, 34: 1081--1091, 2013. \bibitem{Ma1303} S.-M. Ma. \newblock Enumeration of permutations by number of alternating runs. \newblock{\em Discrete Math.}, 313: 1816--1822, 2013. \bibitem{Ollagnier01} J.M. Ollagnier. \newblock Liouvillian integration of the Lotka-Volterra system. \newblock{\em Qual. Theory Dyn. Syst.}, 2: 307--358, 2001. \bibitem{Sloane} N.J.A. Sloane. \newblock {\em The On-Line Encyclopedia of Integer Sequences}, published electronically at http://oeis.org, 2010. \bibitem{Sta08} R.P. Stanley. \newblock Longest alternating subsequences of permutations. \newblock {\em Michigan Math. J.}, 57: 675--687, 2008. \end{thebibliography} \end{document}