Differential operators and Narayana numbers

1. Introduction

It is well known that the central binomial coefficients have the following expressions; $$\binom{2n}{n}=\sum_{k=0}^n{\binom{n}{k}}^2,~\binom{2n+1}{n}=\sum_{k=0}^n{\binom{n}{k}}\binom{n+1}{k}.$$

For \(0\leq k\leq n\), the Narayana numbers of types \(A\) are defined as; $$N(n,k)=\frac{1}{n}\binom{n}{k+1}\binom{n}{k}.$$

Let \(N_n(x)=\sum_{k=0}^{n-1}N(n,k)x^k\) be the Narayana polynomials of types \(A\) (see [1]). It is well known that \(N_n(x)\) is the rank-generating function of the lattice of non-crossing partition lattice with cardinality \(\frac{1}{n+1}\binom{2n}{n}\) (see[2]). Hence the Catalan numbers have the following expression; $$\frac{1}{n+1}\binom{2n}{n}=\sum_{k=0}^{n-1}\frac{1}{n}\binom{n}{k+1}\binom{n}{k}.$$

The Narayana numbers of type \(B\) are given as; $$M(n,k)=\binom{n}{k}^2.$$

Let \(M_n(x)=\sum_{k=0}^nM(n,k)x^k\). Reiner [2] showed that \(M_n(x)\) is the rank-generating function of a ranked self-dual lattice with the cardinality \(\binom{2n}{n}\).

Let \(P(n,k)={\binom{n}{k}}\binom{n+1}{k},\) and \(S=\mathbb{P}\times \mathbb{P}\). According to [3 Proposition 1], \(P(n,k)\) is the number of paths in \(A_1(n+1)\) having \(k+1\) steps, where \(A_1(n)\) is the set of all lattice paths running from \((0;-1)\) to \((n;n)\) that use the steps in \(S\) and that remain strictly above the line \(y=-1\) except initially.

The numbers \(N(n,k),M(n,k)\) and \(P(n,k)\) have been extensively studied. The readers are referred to[4] for details. In [5], Daboul et al., reveals that $$\frac{d^n}{dx^n}(e^{1/x})=(-1)^ne^{1/x}\sum_{k=1}^{n}{\binom{n}{k}\binom{n-1}{k-1}(n-k)!x^{-n-k}},$$ where the \(\binom{n}{k}\binom{n-1}{k-1}(n-k)!\) are the Lah numbers. Motivated by this result, in this paper we show that the numbers \(M(n,k),N(n,k)\) and \(P(n,k)\) can be generated by higher-order derivative of functions of \(e^x\). As an application, we obtain new recurrence relations for these classical combinatorial numbers.

2. Differential operators and Narayana polynomials

Let \(P_n(x)=\sum_{k=0}^nP(n,k)x^{n-k},~Q_n(x)=\sum_{k=0}^nP(n,k)x^{k},\) then \(Q_n(x)=x^nP_n(1/x)\). The first few \(N_n(x),M_n(x)\) and \(P_n(x)\) are listed as follows; \begin{align*} N_1(x)&=1,~N_2(x)=1+x,N_3(x)=1+3x+x^2,~N_4(x)=1+6x+6x^2+x^3,\\ M_1(x)&=1+x,~M_2(x)=1+4x+x^2,M_3(x)=1+9x+9x^2+x^3,\\ P_1(x)&=2+x,~P_2(x)=3+6x+x^2,P_3(x)=4+18x+12x^2+x^3. \end{align*} We define \(\overline{N}(n,k)=(n+1)!n!N(n,k)\) and \(\overline{M}(n,k)=n!^2M(n,k)\). By using the explicit formulas of \(\overline{N}(n,k)\) and \(\overline{M}(n,k)\), it is routine to verify the following lemma.

Lemma 1. For \(0\leq k\leq n+1\), we have \begin{align*} \overline{N}(n+1,k)&=((n+1)(n+2)+2nk+k^2+3k)\overline{N}(n,k)+(4n+2n^2-2(k^2-1)){\overline{N}}(n,k-1)\\&\,\,\,\,\,\,+(n(n-1)-(k-2)(2n-k+1))\overline{N}(n,k-2),\\ \overline{M}(n+1,k)&=((n+1)^2+2(n+1)k+k^2)\overline{M}(n,k)+(1+4n+2n^2-2k(k-1)){\overline{M}}(n,k-1)\\&\,\,\,\,\,\,+(n^2-(2n+2-k)(k-2))\overline{M}(n,k-2), \end{align*} with initial conditions \(\overline{N}(0,0)=\overline{M}(0,0)=1\) and \(\overline{N}(0,k)=\overline{M}(0,k)=0\) for \(k\neq 0\).

In the following discussion, let \(D=\frac{d}{dx}\).

Theorem 1. For \(n\geq 1\), we have

Proof. Note that \begin{eqnarray*} (De^xD)\left(\frac{1}{1-e^x}\right)&=&\frac{2e^{2x}}{(1-e^x)^{3}},\\(De^xD)^2\left(\frac{1}{1-e^x}\right)&=&\frac{12e^{3x}(1+e^x)}{(1-e^x)^{5}},\\ (De^xD)^3\left(\frac{1}{1-e^x}\right)&=&\frac{144e^{4x}(1+3e^x+e^{2x})}{(1-e^x)^{7}}. \end{eqnarray*} Hence the formula (1) holds for \(n=1,2,3\). Assume that the result holds for \(n\), where \(n\geq 3\). Let \(\overline{N}_n(x)=\sum_{k=0}^{n-1}\overline{N}(n,k)x^k\). Note that \begin{align*} &(De^xD)^{n+1}\left(\frac{1}{1-e^x}\right)=(De^xD)\left(\frac{e^{(n+1)x}\overline{N}_n(e^x)}{(1-e^x)^{2n+1}}\right). \end{align*} It follows that
\( \overline{N}_{n+1}(x)=((n+1)(n+2)+(4n+2n^2)x+n(n-1)x^2)\overline{N}_n(x)+(4x-6x^2+2x^3+2nx(1-x^2))D(\overline{N}_n(x))\\+x^2(1-x)^2D^2(\overline{N}_n(x)). \) Equating the coefficients of \(x^k\) in both sides, we immediately get the recurrence relation of \(\overline{N}(n,k)\) given in Lemma 1. Therefore, the result holds for \(n+1\). Similarly, note that \begin{eqnarray*} (e^xD^2)\left(\frac{1}{1-e^x}\right)&=&\frac{e^{2x}(1+e^x)}{(1-e^x)^{3}},\\(e^xD^2)^2\left(\frac{1}{1-e^x}\right)&=&\frac{4e^{3x}(1+4e^x+e^{2x})}{(1-e^x)^{5}},\\ (e^xD^2)^3\left(\frac{1}{1-e^x}\right)&=&\frac{36e^{4x}(1+9e^x+9e^{2x}+e^{3x})}{(1-e^x)^{7}}. \end{eqnarray*} Hence the formula (2) holds for \(n=1,2,3\). Assume it holds for \(n\), where \(n\geq 3\). Let \(\overline{M}_n(x)=\sum_{k=0}^{n}\overline{M}(n,k)x^k\). Note that \begin{align*} &(e^xD^2)^{n+1}\left(\frac{1}{1-e^x}\right)=(e^xD^2)\left(\frac{e^{(n+1)x}\overline{M}_n(e^x)}{(1-e^x)^{2n+1}}\right). \end{align*} It follows that
\( \overline{M}_{n+1}(x)=(1+x+n^2(1+x)^2+n(2+4x))\overline{M}_n(x)+(3x-4x^2+x^3+2nx(1-x^2))D(\overline{M}_n(x))\\+x^2(1-x)^2D^2(\overline{M}_n(x)). \) Equating the coefficients of \(x^k\) in both sides, we immediately get the recurrence relation of \(\overline{M}(n,k)\) given in Lemma 1. Therefore, the result holds for \(n+1\). Along the same lines, it is routine to derive (3). This completes the proof.

Note that \(P(n,n-k)={\binom{n}{n-k}}\binom{n+1}{n-k},\) then \(P(n+1,n+1-k)={\binom{n+1}{n+1-k}}\binom{n+2}{n+1-k}.\) It is easy to verify the following lemma;

Lemma 2. For \(0\leq k\leq n+1\), we have \( (n+1)(n+2)P(n+1,n+1-k)=[(n+2)^2+(2n+5)k+k(k-1)]P(n,n-k)\\+[2(n^2+3n+1)-6(k-1)-2(k-1)(k-2)]P(n,n-k+1)+[n^2-(2n-1)(k-2)+(k-2)(k-3)]P(n,n-k+2). \)

Theorem 2. For \(n\geq 1\), we have

Proof. Note that $$(D^2e^x)\frac{e^x}{(1-e^x)^2}=\frac{2e^{2x}(2+e^x)}{(1-e^x)^4},$$ $$(D^2e^x)^2\frac{e^x}{(1-e^x)^2}=\frac{12e^{3x}(3+6e^x+e^{2x})}{(1-e^x)^6}.$$ Hence the result holds for \(n=1,2\). Assume that the result holds for \(n\). Then from (4), we get the recurrence relation
\( (n+1)(n+2)P_{n+1}(x)=[n^{2}x^2+(2+n)^2+2x(1+3n+n^2)]P_n(x)+x(1-x)[(2n-1)x+2n+5]P_n'(x)+x^2(1-x)^2P_n''(x). \) Equating the coefficients of \(x^k\) in both sides, we get the recurrence relation of the numbers \(P(n,n-k)\), which is given in Lemma 2, as desired. Along the same lines, one can derive (5). This completes the proof.

By a change of variable \(y=e^x\), we end our paper by giving a corollary;

Corollary 1. For \(n\geq 1\), let \(D_y=\frac{d}{dy}\), we have

1. \((yD_yy^2D_y)^n\left(\frac{1}{1-y}\right)=\frac{n!(n+1)!y^{n+1}N_n(y)}{(1-y)^{2n+1}},\)
2. \((y^2D_yyD_y)^n\left(\frac{1}{1-y}\right)=\frac{n!^2y^{(n+1)}M_n(y)}{(1-y)^{2n+1}},\)
3. \((yD_yyD_yy)^n\left(\frac{1}{1-y}\right)=\frac{n!^2y^{n}M_n(y)}{(1-y)^{2n+1}},\)
4. \((yD_yyD_yy)^n\frac{y}{(1-y)^2}=\frac{n!(n+1)!y^{(n+1)}P_n(y)}{(1-y)^{2n+2}},\)
5. \((yD_yy^2D_y)^n\frac{y}{(1-y)^2}=\frac{n!(n+1)!y^{(n+1)}Q_n(y)}{(1-y)^{2n+2}}.\)

Proof. It's not hard to verify the equations hold when \(n=1,2\)$$(yD_yy^2D_y)\left(\frac{1}{1-y}\right)=\frac{2y^{2}}{(1-y)^{3}},$$ $$(yD_yy^2D_y)^2\left(\frac{1}{1-y}\right)=\frac{12y^{3}(1+y)}{(1-y)^{5}}.$$ Assume the result holds for \(m\), where \(m\geq3\). Setting \(y=e^x\), we get \begin{align*} (yD_yy^2D_y)(yD_yy^2D_y)^{m}\left(\frac{1}{1-y}\right)=(e^xD_ye^{2x}D_y)\frac{m!(m+1)!y^{n+1}N_m(y)}{(1-y)^{2m+1}}\\=(De^xD)\frac{m!(m+1)!e^{(m+1)x}N_m(e^x)}{(1-e^x)^{2m+1}}\\=\frac{(m+1)!(m+2)!e^{(m+2)x}N_{m+1}(e^x)}{(1-e^x)^{2m+3}}\\=\frac{(m+1)!(m+2)!y^{m+1}N_{m+1}(y)}{(1-y)^{2m+3}}. \end{align*} Along the same lines, we can get the other statements. This completes the proof.

Acknowledgments

The authors appreciate the careful review, corrections and helpful suggestions to this paper made by the referee.

Author Contributions

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

Conflicts of Interest:

The authors declare no conflict of interest.