% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all commands that change parameters such as % margins or page sizes. % Packages amssymb and amsthm are already loaded. % We recommend these AMS packages: \usepackage{amsmath,amssymb} % We recommend the graphicx package for importing figures: \usepackage{graphicx} % Use this command to create hyperlinks (optional and recommended): \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % Theorem-like environments that are declared in the style file are: % theorem, lemma, corollary, proposition, fact, observation, claim, % definition, example, conjecture, open, problem, question, remark, note \newcommand{\bk}{{\rm bk\,}} \newcommand{\X}{{\rm x\,}} \newcommand{\CLS}{{\rm CLS\,}} \newcommand{\NN}{{\rm N\,}} \newcommand{\MM}{{\rm M\,}} \newcommand{\Jc}{{\rm Jc\,}} \newcommand{\Lc}{{\rm Lc\,}} \newcommand{\LSD}{{\rm LSD\,}} \newcommand{\LS}{{\rm LS\,}} \newcommand{\cdd}{{\rm cdd\,}} \newcommand{\JS}{{\rm JS\,}} \newcommand{\CLSS}{\mathcal {CLS}} \newcommand{\LSS}{\mathcal{LS}} \newcommand{\bn}{{\rm\bf n}} \newcommand{\lrf}[1]{\lfloor #1\rfloor} \newcommand{\lrc}[1]{\lceil #1\rceil} \newcommand{\mbn}{{\mathcal B}_n} \newcommand{\mq}{\mathcal{Q}} \newcommand{\mqn}{\mathcal{Q}_n} \newcommand{\z}{ \mathbb{Z}} \DeclareMathOperator{\N}{\mathbb{N}} \DeclareMathOperator{\LHP}{LHP} \DeclareMathOperator{\R}{\mathbb{R}} \DeclareMathOperator{\Q}{\mathbb{Q}} \newcommand{\stirling}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} \newcommand{\Stirling}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} \linespread{1.25} %%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Give the submission and acceptance dates in the format shown. % The editors will insert the publication date in the third argument. \dateline{Aug 5, 2018}{Dec 2,2018}{TBD} % Give one or more subject codes separated by commas. % Codes are available from http://www.ams.org/mathscinet/freeTools.html \MSC{05A18, 05A19} % Uncomment exactly one of the following copyright statements. Alternatively, % you can write your own copyright statement subject to the approval of the journal. % See https://creativecommons.org/licenses/ for a full explanation of the % Creative Commons licenses. % % We strongly recommend CC BY-ND or CC BY. Both these licenses allow others % to freely distribute your work while giving credit to you. The difference between % them is that CC BY-ND only allows distribution unchanged and in whole, while % CC BY also allows remixing, tweaking and building upon your work. % % One author: %\Copyright{The author.} %\Copyright{The author. Released under the CC BY license (International 4.0).} %\Copyright{The author. Released under the CC BY-ND license (International 4.0).} % More than one author: %\Copyright{The authors.} %\Copyright{The authors. Released under the CC BY license (International 4.0).} \Copyright{The authors. Released under the CC BY-ND license (International 4.0).} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % If needed, include a line break (\\) at an appropriate place in the title. \title{On certain combinatorial expansions of the Legendre-Stirling numbers} % Input author, affiliation, address and support information as follows; % The address should include the country, but does not have to include % the street address. Give at least one email address. \author{Shi-Mei Ma\thanks{Supported by Natural Science Foundation of Hebei Province (A2017501007) and NSFC (11401083).}\\ \small School of Mathematics and Statistics\\[-0.8ex] \small Northeastern University at Qinhuangdao\\[-0.8ex] \small Hebei, P.R. China\\ \small\tt shimeimapapers@163.com\\ \and Jun Ma\thanks{Supported by NSFC 11571235.}\\ \small Department of Mathematics\\[-0.8ex] \small Shanghai Jiao Tong University\\[-0.8ex] \small Shanghai, P.R. China\\ \small\tt majun904@sjtu.edu.cn\\ \and Yeong-Nan Yeh\thanks{Supported by NSC 107-2115-M-001-009-MY3.}\\ \small Institute of Mathematics\\[-0.8ex] \small Academia Sinica\\[-0.8ex] \small Taipei, Taiwan\\ \small\tt mayeh@math.sinica.edu.tw} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract may be distributed without the rest of the % paper so it must be entirely self-contained. Try to include all words % and phrases that someone might search for when looking for your paper. \begin{abstract} The Legendre-Stirling numbers of the second kind were introduced by Everitt et al. in the spectral theory of powers of the Legendre differential expressions. As a continuation of the work of Andrews and Littlejohn (Proc. Amer. Math. Soc., 137 (2009), 2581--2590), we provide a combinatorial code for Legendre-Stirling set partitions. As an application, we obtain expansions of the Legendre-Stirling numbers of both kinds in terms of binomial coefficients. \bigskip\noindent \textbf{Keywords:} Legendre-Stirling numbers; Jacobi-Stirling numbers; Binomial coefficients \end{abstract} \section{Introduction} The study on Legendre-Stirling numbers and Jacobi-Stirling numbers has become an active area of research in the past decade. In particular, these numbers are closely related to set partitions~\cite{Andrews09}, symmetric functions~\cite{Mongelli12}, special functions~\cite{Merca15} and so on. %For example, in~\cite{Merca15}, Merca established a connection between Jacobi-Stirling numbers and Bernoulli polynomials. Let $\ell[y](t)=-(1-t^2)y''(t)+2ty'(t)$ be the Legendre differential operator. Then the Legendre polynomial $y(t)=P_n(t)$ is an eigenvector for the differential operator $\ell$ corresponding to $n(n+1)$, i.e., $\ell[y](t)=n(n+1)y(t)$. Following Everitt et al.~\cite{Everitt02}, for $n\in \N$, the {\it Legendre-Stirling numbers $\LS(n,k)$ of the second kind} appeared originally as the coefficients in the expansion of the $n$-th composite power of $\ell$, i.e., \begin{align*} \ell^n[y](t)&=\sum_{k=0}^n(-1)^k\LS(n,k)((1-t^2)^ky^{(k)}(t))^{(k)}. \end{align*} %In the last decade, the combinatorial interpretations of the Legendre-Stirling numbers and Jacobi-Stirling numbers of both kinds received considerable attention, see~\cite{Andrews13,Andrews11,Andrews09,Egge10,Zeng10,Gessel12} for instance. For each $k\in \N$, Everitt et al.~\cite[Theorem 4.1)]{Everitt02} obtained that \begin{equation}\label{vertical-GF} \prod_{r=0}^k\frac{1}{1-r(r+1)x}=\sum_{n=0}^\infty\LS(n,k)x^{n-k},~\left(|x| < \frac{1}{k(k+1)} \right). \end{equation} According to~\cite[Theorem 5.4]{Andrews11}, the numbers $\LS(n,k)$ have the following horizontal generating function \begin{equation}\label{xnJsnkz01} x^n=\sum_{k=0}^n\LS(n,k)\prod_{i=0}^{k-1}(x-i(1+i)). \end{equation} It follows from~\eqref{xnJsnkz01} that the numbers $\LS(n,k)$ satisfy the recurrence relation \begin{equation*} \LS(n,k)=\LS(n-1,k-1)+k(k+1)\LS(n-1,k). \end{equation*} with the initial conditions $\LS(n,0)=\delta_{n,0}$ and $\LS(0,k)=\delta_{0,k}$, where $\delta_{i,j}$ is the Kronecker's symbol. By using~\eqref{vertical-GF}, Andrews et al.~\cite[Theorem~5.2]{Andrews11} derived that the numbers $\LS(n,k)$ satisfy the vertical recurrence relation $$\LS(n,j)=\sum_{k=j}^n\LS(k-1,j-1)(j(j+1))^{n-k}.$$ Following~\cite[Theorem 4.1]{Everitt07}, the {\it Jacobi-Stirling number $\JS_n^k(z)$ of the second kind} may be defined by \begin{equation}\label{xnJsnkz} x^n=\sum_{k=0}^n\JS_n^k(z)\prod_{i=0}^{k-1}(x-i(z+i)). \end{equation} It follows from~\eqref{xnJsnkz} that the numbers $\JS_n^k(z)$ satisfy the recurrence relation \begin{align*} \JS_n^k(z)=\JS_{n-1}^{k-1}(z)+k(k+z)\JS_{n-1}^k(z), \end{align*} with the initial conditions $\JS_n^0(z)=\delta_{n,0}$ and $\JS_0^k(z)=\delta_{0,k}$ (see~\cite{Merca15} for instance). It is clear that $\JS_n^k(1)=\LS(n,k)$. In~\cite{Gessel12}, Gessel, Lin and Zeng studied generating function of the coefficients of $\JS_{n+k}^n(z)$. Note that $\JS_{n+k}^n(1)=\LS(n+k,n)$. This paper is devoted to the following problem. \begin{problem}\label{problem01} Let $k$ be a given nonnegative integer. Could the numbers $\LS(n+k,n)$ be expanded in the binomial basis? \end{problem} A particular value of $\LS(n,k)$ is provided at the end of~\cite{Andrews09}: \begin{equation}\label{LSnk01} \LS(n+1,n)=2\binom{n+2}{3}. \end{equation} In~\cite[Eq.~(19)]{Egge10}, Egge obtained that \begin{align*} \LS(n+2,n)&=40\binom{n+2}{6}+72\binom{n+2}{5}+36\binom{n+2}{4}+4\binom{n+2}{3}. \end{align*} Using the triangular recurrence relation $\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$, we get \begin{equation}\label{LSnk02} \LS(n+2,n)=40\binom{n+3}{6}+32\binom{n+3}{5}+4\binom{n+3}{4}. \end{equation} Egge~\cite[Theorem 3.1]{Egge10} showed that for $k\geq 0$, the quantity $\LS(n+k,n)$ is a polynomial of degree $3k$ in $n$ with leading coefficient $\frac{1}{3^kk!}$. As a continuation of~\cite{Andrews09} and~\cite{Egge10}, in Section~\ref{Section02}, we give a solution of Problem~\ref{problem01}. Moreover, we get an expansion of the Legendre-Stirling numbers of the first kind in terms of binomial coefficients. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Main results}\label{Section02} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \hspace*{\parindent} The combinatorial interpretation of the Legendre-Stirling numbers $\LS(n,k)$ of the second kind was first given by Andrews and Littlejohn~\cite{Andrews09}. For $n\geq 1$, let $\MM_n$ denote the multiset $\{1,\overline{1},2,\overline{2},\ldots,n,\overline{n}\}$, in which we have one unbarred copy and one barred copy of each integer $i$, where $1\leq i\leq n$. Throughout this paper, we always assume that the elements of $\MM_n$ are ordered by $$\overline{1}=1<\overline{2}=2<\cdots <\overline{n}=n.$$ A {\it Legendre-Stirling set partition} of $\MM_n$ is a set partition of $\MM_n$ with $k+1$ blocks $B_0,B_1,\ldots, B_k$ and with the following rules: \begin{itemize} \item [\rm ($r_1$)] The `zero box' $B_0$ is the only box that may be empty and it may not contain both copies of any number; \item [\rm ($r_2$)] The `nonzero boxes' $B_1,B_2,\ldots,B_k$ are indistinguishable and each is non-empty. For any $i\in [k]$, the box $B_i$ contains both copies of its smallest element and does not contain both copies of any other number. \end{itemize} Let $\LSS(n,k)$ denote the set of Legendre-Stirling set partitions of $\MM_n$ with one zero box and $k$ nonzero boxes. The {\it standard form} of an element of $\LSS(n,k)$ is written as $$\sigma=B_1B_2\cdots B_kB_0,$$ where $B_0$ is the zero box and the minima of $B_i$ is less than that of $B_j$ when $1\leq i$ and curly bracket symbol $\{k,\overline{k},\ldots\}$ denote the zero box and nonzero box, respectively. In particular, let $<>$ denote the empty zero box. For example, $\{1,\overline{1},3\}\{2,\overline{2}\}<\overline{3}>\in\LSS(3,2)$. A classical result of Andrews and Littlejohn~\cite[Theorem 2]{Andrews09} says that $$\LS(n,k)=\#\LSS(n,k).$$ We now provide a combinatorial code for Legendre-Stirling partitions ($\CLS$-sequence for short). \begin{definition}\label{CLS-def} We call $Y_n=(y_1,y_2,\ldots,y_n)$ a {\it $\CLS$-sequence} of length $n$ if $y_1=X$ and $$y_{k+1}\in \{X,A_{i,j},B_s,\overline{B}_s,1\leq i,j,s\leq n_x(Y_k),i\neq j\}\quad\textrm{for $k=1,2,\ldots,n-1$},$$ where $n_x(Y_k)$ is the number of the symbol $X$ in $Y_k=(y_1,y_2,\ldots,y_k)$. \end{definition} For example, $(X,X,A_{1,2})$ is a $\CLS$-sequence, while $(X,X,A_{1,2},B_3)$ is not since $y_4=B_3$ and $3>n_x(Y_3)=2$. Let $\CLSS_n$ denote the set of $\CLS$-sequences of length $n$. The following lemma is a fundamental result. \begin{lemma}\label{Lemma01} For $n\geq 1$, we have $\LS(n,k)=\#\{Y_n\in\CLSS_n\mid n_x(Y_n)=k\}$. \end{lemma} \begin{proof} Let $\CLSS(n,k)=\{Y_n\in\CLSS_n\mid n_x(Y_n)=k\}$. Now we start to construct a bijection, denoted by $\Phi$, between $\LSS(n,k)$ and $\CLSS(n,k)$. When $n=1$, we have $y_1=X$. Set $\Phi(Y_1)=\{1,\overline{1}\}<>$. This gives a bijection from $\CLSS(1,1)$ to $\LSS(1,1)$. Let $n=m$. Suppose $\Phi$ is a bijection from $\CLSS(n,k)$ to $\CLSS(n,k)$ for all $k$. Consider the case $n=m+1$. Let $$Y_{m+1}=(y_1,y_2,\ldots,y_m,y_{m+1})\in \CLSS_{m+1}.$$ Then $Y_m=(y_1,y_2,\ldots,y_m)\in \CLSS(m,k)$ for some $k$. Assume $\Phi(Y_m)\in\LSS(m,k)$. Consider the following three cases: \begin{enumerate} \item [\rm ($i$)] If $y_{m+1}=X$, then let $\Phi(Y_{m+1})$ be obtained from $\Phi(Y_m)$ by putting the box $\{m+1,\overline{m+1}\}$ just before the zero box. In this case, $\Phi(Y_{m+1})\in\LSS(m+1,k+1)$. \item [\rm ($ii$)] If $y_{m+1}=A_{i,j}$, then let $\Phi(Y_{m+1})$ be obtained from $\Phi(Y_m)$ by inserting the entry $m+1$ to the $i$th nonzero box and inserting the entry $\overline{m+1}$ to the $j$th nonzero box. In this case, $\Phi(Y_{m+1})\in\LSS(m+1,k)$. \item [\rm ($iii$)] If $y_{m+1}=B_{s}$ (resp. $y_{m+1}=\overline{B}_{s}$), then let $\Phi(Y_{m+1})$ be obtained from $\Phi(Y_m)$ by inserting the entry $m+1$ (resp. $\overline{m+1}$) to the $s$th nonzero box and inserting the entry $\overline{m+1}$ (resp. $m+1$) to the zero box. In this case, $\Phi(Y_{m+1})\in\LSS(m+1,k)$. \end{enumerate} After the above step, it is clear that the obtained $\Phi(Y_{m+1})$ is in standard form. By induction, we see that $\Phi$ is the desired bijection from $\CLSS(n,k)$ to $\CLSS(n,k)$, which also gives a constructive proof of Lemma~\ref{Lemma01}. \end{proof} \begin{example} Let $Y_5=(X,X,A_{2,1},B_2,\overline{B}_1)$. The correspondence between $Y_5$ and $\Phi(Y_5)$ is built up as follows: \begin{align*} X&\Leftrightarrow \{1,\overline{1}\}<>;\\ X&\Leftrightarrow \{1,\overline{1}\}\{2,\overline{2}\}<>;\\ A_{2,1}&\Leftrightarrow \{1,\overline{1},\overline{3}\}\{2,\overline{2},3\}<>;\\ B_2&\Leftrightarrow \{1,\overline{1},\overline{3}\}\{2,\overline{2},3,4\}<\overline{4}>;\\ \overline{B}_1&\Leftrightarrow \{1,\overline{1},\overline{3},\overline{5}\}\{2,\overline{2},3,4\}<\overline{4},5>. %-2&\rightarrow ^{1}3^{2}3^{-1}1^{3}4^{4}4^{\textbf{-2}}2^{-3}2^{-4}1^{0}\Leftrightarrow 3314455221. %2&\rightarrow ^{1}3^{\textbf{2}}3^{-1}1^{3}4^{4}4^{5}5^{6}5^{-2}2^{-3}2^{-4}1^{0}\Leftrightarrow 366314455221. \end{align*} \end{example} As an application of Lemma~\ref{Lemma01}, we present the following lemma. \begin{lemma}\label{lemma02} Let $k$ be a given positive integer. Then for $n\geq 1$, we have \begin{equation}\label{LSNK01} \LS(n+k,n)=2^k\sum_{t_k=1}^n\binom{t_k+1}{n}\sum_{t_{k-1}=1}^{t_k}\binom{t_{k-1}+1}{2}\cdots \sum_{t_2=1}^{t_3}\binom{t_2+1}{2}\sum_{t_1=1}^{t_2}\binom{t_1+1}{2}. \end{equation} \end{lemma} \begin{proof} It follows from Lemma~\ref{Lemma01} that $$\LS(n+k,n)=\#\{Y_{n+k}\in\CLSS_{n+k}\mid n_x(Y_{n+k})=n\}.$$ Let $Y_{n+k}=(y_1,y_2,\ldots,y_{n+k})$ be a given element in $\CLSS_{n+k}$. Since $n_x(Y_{n+k})=n$, it is natural to assume that $y_i=X$ except $i=t_1+1,t_2+2,\cdots, t_k+k$. Let $\sigma$ be the corresponding Legendre-Stirling partition of $Y_{n+k}$. For $1\leq \ell\leq k$, consider the value of $y_{t_\ell+\ell}$. Note that the number of the symbols $X$ before $y_{t_\ell+\ell}$ is $t_\ell$. Let $\widehat{\sigma}$ be the corresponding Legendre-Stirling set partition of $(y_1,y_2,\ldots, y_{t_\ell+\ell-1})$. Now we insert $y_{t_\ell+\ell}$. We distinguish two cases: \begin{enumerate} \item [\rm ($i$)] If $y_{t_\ell+\ell}=A_{i,j}$, then we should insert the entry $t_\ell+\ell$ to the $i$th nonzero box of $\widehat{\sigma}$ and insert $\overline{t_\ell+\ell}$ to the $j$th nonzero box. This gives $2\binom{t_\ell}{2}$ possibilities, since $1\leq i,j\leq t_\ell$ and $i\neq j$. \item [\rm ($ii$)] If $y_{t_\ell+\ell}=B_{s}$ (resp. $y_{t_\ell+\ell}=\overline{B}_{s}$), then we should insert the entry $t_\ell+\ell$ (resp. $\overline{t_\ell+\ell}$) to the $s$th nonzero box of $\widehat{\sigma}$ and insert $\overline{t_\ell+\ell}$ (resp. ${t_\ell+\ell}$) to the zero box. This gives $2\binom{t_\ell}{1}$ possibilities, since $1\leq s\leq t_\ell$. \end{enumerate} Therefore, there are exactly $2\binom{t_\ell}{2}+2\binom{t_\ell}{1}=2\binom{t_\ell+1}{2}$ Legendre-Stirling set partitions of $\MM_{t_\ell+\ell}$ can be generated from $\widehat{\sigma}$ by inserting the entry $y_{t_\ell+\ell}$. Note that $1\leq t_{j-1}\leq t_j\leq n$ for $2\leq j\leq k$. Applying the product rule for counting, we immediately get~\eqref{LSNK01}. \end{proof} The following simple result will be used in our discussion. \begin{lemma}\label{lemma03} Let $a$ and $b$ be two given integers. Then \begin{equation*} \binom{x-b}{2}\binom{x}{a}=\binom{a+2}{2}\binom{x}{a+2}+(a+1)(a-b)\binom{x}{a+1}+\binom{a-b}{2}\binom{x}{a}. \end{equation*} In particular, \begin{equation*} \binom{x-1}{2}\binom{x}{a}=\binom{a+2}{2}\binom{x}{a+2}+(a^2-1)\binom{x}{a+1}+\binom{a-1}{2}\binom{x}{a}. \end{equation*} \end{lemma} \begin{proof} Note that $$\binom{a+2}{2}\frac{(x-a)(x-a-1)}{(a+2)(a+1)}+(a+1)(a-b)\frac{x-a}{a+1}+\binom{a-b}{2}=\binom{x-b}{2}.$$ This yields the desired result. \end{proof} We can now conclude the main result of this paper from the discussion above. \begin{theorem}\label{thm01} Let $k$ be a given nonnegative integer. For $n\geq 1$, the numbers $\LS(n+k,n)$ can be expanded in the binomial basis as \begin{equation}\label{LSNK-binomial} \LS(n+k,n)=2^k\sum_{i=k+2}^{3k}\gamma(k,i)\binom{n+k+1}{i}, \end{equation} where the coefficients $\gamma(k,i)$ are all positive integers for $k+2\leq i\leq 3k$ and satisfy the recurrence relation \begin{equation}\label{LSNK-recu} \gamma(k+1,i)=\binom{i-k-1}{2}\gamma(k,i-1)+(i-1)(i-k-2)\gamma(k,i-2)+\binom{i-1}{2}\gamma(k,i-3), \end{equation} with the initial conditions $\gamma(0,0)=1$, $\gamma(0,i)=\gamma(i,0)=0$ for $i\neq 0$. Let $\gamma_k(x)=\sum_{i=k+2}^{3k}\gamma(k,i)x^i$. Then the polynomials $\gamma_k(x)$ satisfy the recurrence relation \begin{equation}\label{LSNK-recu02} \gamma_{k+1}(x)=\left(\frac{k(k+1)}{2}-kx+x^2\right)x\gamma_k(x)- (k+(k-2)x-2x^2)x^2\gamma_k'(x)+\frac{(1+x)^2x^3}{2}\gamma_k''(x), \end{equation} with the initial conditions $\gamma_0(x)=1,\gamma_1(x)=x^3$ and $\gamma_2(x)=x^4+8x^5+10x^6$. \end{theorem} \begin{proof} We prove~\eqref{LSNK-binomial} by induction on $k$. It is clear that $\LS(n,n)=1=\binom{n+1}{0}$. When $k=1$, by using the {\it Chu Shih-Chieh's identity} $$\binom{n+1}{k+1}=\sum_{i=k}^n\binom{i}{k},$$ we obtain $$\sum_{t_1=1}^{n}\binom{t_1+1}{2}=\binom{n+2}{3},$$ and so~\eqref{LSnk01} is established. When $k=2$, it follows from Lemma~\ref{lemma02} that \begin{align*} \LS(n+2,n)&=4\sum_{t_2=1}^{n}\binom{t_2+1}{2}\sum_{t_1=1}^{t_2}\binom{t_1+1}{2}\\ &=4\sum_{t_2=1}^{n}\binom{t_2+1}{2}\binom{t_2+2}{3}. \end{align*} Setting $x=t_2+2$ and $a=3$ in Lemma~\ref{lemma03}, we get \begin{align*} \LS(n+2,n)&=4\sum_{t_2=1}^{n}\left(10\binom{t_2+2}{5}+8\binom{t_2+2}{4}+\binom{t_2+2}{3}\right)\\ &=4\left(10\binom{n+3}{6}+8\binom{n+3}{5}+\binom{n+3}{4}\right), \end{align*} which yields~\eqref{LSnk02}. Along the same lines, it is not hard to verify that \begin{align*} \LS(n+3,n)&=8\sum_{t_3=1}^{n}\binom{t_3+1}{2}\left(10\binom{t_3+3}{6}+8\binom{t_3+3}{5}+\binom{t_3+3}{4}\right)\\ &=8\left(280\binom{n+4}{9}+448\binom{n+4}{8}+219\binom{n+4}{7}+34\binom{n+4}{6}+\binom{n+4}{5}\right). \end{align*} Hence the formula~\eqref{LSNK-binomial} holds for $k=0,1,2,3$, so we proceed to the inductive step. For $k\geq 3$, assume that \begin{equation*}\label{LSNK02} \LS(n+k,n)=2^k\sum_{i=k+2}^{3k}\gamma(k,i)\binom{n+k+1}{i}. \end{equation*} It follows from Lemma~\ref{lemma02} that \begin{align*} \LS(n+k+1,n)&=2^{k+1}\sum_{t_{k+1}=1}^{n}\binom{t_{k+1}+1}{2}\sum_{i=k+2}^{3k}\gamma(k,i)\binom{t_{k+1}+k+1}{i} \end{align*} By using Lemma~\ref{lemma03} and the Chu Shih-Chieh's identity, it is routine to verify that the coefficients $\gamma(k,i)$ satisfy the recurrence relation~\eqref{LSNK-recu}, and so~\eqref{LSNK-binomial} is established for general $k$. Multiplying both sides of~\eqref{LSNK-recu} by $x^i$ and summing for all $i$, we immediately get~\eqref{LSNK-recu02}. \end{proof} In~\cite{Andrews11}, Andrews et al. introduced the {\it (unsigned) Legendre-Stirling numbers $\Lc(n,k)$ of the first kind}, which may be defined by the recurrence relation $$\Lc(n,k)=\Lc(n-1,k-1)+n(n-1)\Lc(n-1,k),$$ with the initial conditions $\Lc(n,0)=\delta_{n,0}$ and $\Lc(0,n)=\delta_{0,n}$. Let $f_k(n)=\LS(n+k,n)$. According to Egge~\cite[Eq.~(23)]{Egge10}, we have \begin{equation}\label{First-second-Legendre} \Lc(n-1,n-k-1)=(-1)^kf_k(-n) \end{equation} for $k\geq 0$. For $m,k\in \N$, we define $$\binom{-m}{k}=\frac{(-m)(-m-1)\cdots (-m-k+1)}{k!}.$$ Combining~\eqref{LSNK-binomial} and~\eqref{First-second-Legendre}, we immediately get the following result. \begin{corollary} Let $k$ be a given nonnegative integer. For $n\geq 1$, the numbers $\Lc(n-1,n-k-1)$ can be expanded in the binomial basis as \begin{equation} \Lc(n-1,n-k-1)=(-1)^k2^k\sum_{i=k+2}^{3k}\gamma(k,i)\binom{-n+k+1}{i}, \end{equation} where the coefficients $\gamma(k,i)$ are defined by~\eqref{LSNK-recu}. \end{corollary} It follows from~\eqref{LSNK-recu02} that \begin{align*} \gamma(k+1,k+3)&=\left(\frac{k(k+1)}{2}-k(k+2)+\frac{(k+2)(k+1)}{2}\right)\gamma(k,k+2),\\ \gamma(k+1,3k+3)&=\left(1+6k+\frac{3k(3k-1)}{2}\right)\gamma(k,3k),\\ \gamma_{k+1}(-1)&=-\left(\frac{k(k+1)}{2}+k+1\right)\gamma_k(-1). \end{align*} Since $\gamma(1,3)=1$ and $\gamma_1(-1)=-1$, it is easy to verify that for $k\geq 1$, we have $$\gamma(k,k+2)=1,~\gamma(k,3k)=\frac{(3k)!}{k!(3!)^k},~\gamma_{k}(-1)=(-1)^k\frac{(k+1)!k!}{2^k}.$$ It should be noted that the number $\gamma(k,3k)$ is the number of partitions of $\{1,2,\ldots,3k\}$ into blocks of size 3, and the number $\frac{(k+1)!k!}{2^k}$ is the product of first $k$ positive triangular numbers. Moreover, if the number $\LS(n+k,n)$ is viewed as a polynomial in $n$, then its degree is $3k$, which is implied by the quantity $\binom{n+k+1}{3k}$. Furthermore, the leading coefficient of $\LS(n+k,n)$ is given by $2^k\gamma(k,3k)\frac{1}{(3k)!}=2^k\frac{(3k)!}{k!(3!)^k}\frac{1}{(3k)!}=\frac{1}{k!3^k}$, which yields~\cite[Theorem 3.1]{Egge10}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\section{Grammatical interpretations of Jacobi-Stirling numbers of both kinds}\label{Section03} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%% \section{Concluding remarks} %%%\hspace*{\parindent} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\hspace*{\parindent} In this paper, by introducing the $\CLS$-sequence, we present a combinatorial expansion of $\LS(n+k,n)$. It should be noted that the $\CLS$-sequence has several other variants. %We end our paper by providing a variant of the $\CLS$-sequence. For an alphabet $A$, let $\mathbb{Q}[[A]]$ be the rational commutative ring of formal Laurent series in monomials formed from letters in $A$. Following Chen~\cite{Chen93}, 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=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. The reader is referred to~\cite{Ma1801} for recent results on context-free grammars. As a variant of the $\CLS$-sequence, we now introduce a marked scheme for Legendre-Stirling set partitions. Given a set partition $\sigma=B_1B_2\cdots B_kB_0\in\LSS(n,k)$, where $B_0$ is the zero box of $\sigma$. We mark the box vector $(B_1,B_2,\ldots,B_k)$ by the label $a_k$. We mark any box pair $(B_i,B_j)$ by a label $b$ and mark any box pair $(B_s,B_0)$ by a label $c$, where $1\leq i