# An Identity Involving Narayana Numbers

Let $N(n,m)$ denote the Narayana number defined by $$N(n,m)=\frac{1}{n}{n\choose m}{n\choose m-1}.$$ Let $$A(n,k,\ell)=\sum_{\substack{i_0+i_1+\cdots+i_k=n\\ j_0+j_1+\cdots+j_k=\ell}}\,\prod_{t=0}^kN(i_t,j_t+1),$$ where the sum ranges over all compositions $(i_0,i_1,\ldots,i_k)$ of $n$ into exactly $k+1$ parts and all weak compositions $(j_0,j_1,\ldots,j_k)$ of $\ell$ into exactly $k+1$ parts. From numerical evidence, I have conjectured that $$A(n,k,\ell)=\frac{k+1}{n}{n\choose \ell}{n\choose \ell+k+1}.$$ This seems like a simple enough formula, but I am at a loss for how to prove it. Any help would be greatly appreciated.

Suppose we have the Narayana number $$N(n,m) = \frac{1}{n} {n\choose m} {n\choose m-1}$$

and let $$A(n,k, l) = {\Large \sum_{i_0+i_1+\cdots+i_k=n \atop j_0+j_1+\cdots+j_k=l} \prod_{t=0}^k N(i_t, j_t+1)}$$

where the compositions for $n$ are regular and the ones for $l$ are weak and we seek to verify that $$A(n,k,l) = \frac{k+1}{n} {n\choose l} {n\choose l+k+1}.$$

Introducing $$G(z, u) = \sum_{p\ge 1} z^p \sum_{q\ge 0} u^q \frac{1}{p} {p\choose q+1} {p\choose q} \\ = \sum_{p\ge 1} \frac{1}{p} z^p \sum_{q\ge 0} u^q {p\choose q+1} {p\choose q}$$

we have by inspection that $$A(n,k,l) = [z^n] [u^l] G(z, u)^{k+1}.$$

To evaluate this introduce for the inner sum term $${p\choose q+1} = {p\choose p-q-1} = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{p-q}} (1+w)^p \; dw.$$

We get for the inner sum $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{p}} (1+w)^p \sum_{q\ge 0} {p\choose q} u^q w^q \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{p}} (1+w)^p (1+uw)^p \; dw \\ = \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{1}{w^{p}} (1+w(1+u+uw)))^p \; dw.$$

Extracting the coefficient from this we get $$[w^{p-1}] \sum_{q=0}^p {p\choose q} w^q (1+u+uw)^q \\ = \sum_{q=0}^{p-1} {p\choose q} [w^{p-1-q}] (1+u+uw)^q \\ = \sum_{q=0}^{p-1} {p\choose q} {q\choose p-1-q} u^{p-1-q} (1+u)^{2q+1-p}.$$

This is $$\sum_{q=0}^{p-1} {p\choose p-1-q} {p-1-q\choose q} u^q (1+u)^{p-1-2q} \\ = \sum_{q=0}^{p-1} {p\choose q+1} {p-1-q\choose q} u^q (1+u)^{p-1-2q}.$$

Now observe that $$\frac{1}{p} {p\choose q+1} {p-1-q\choose q} = \frac{1}{q+1} {p-1\choose q} {p-1-q\choose q} \\ = \frac{1}{q+1} {p-1\choose p-1-q} {p-1-q\choose q} = \frac{1}{q+1} {p-1\choose 2q} {2q\choose q}.$$

where $$C_q = \frac{1}{q+1} {2q\choose q}$$ is a Catalan number.

We thus get for the sum $$\sum_{p\ge 1} z^p \sum_{q=0}^{p-1} {p-1\choose 2q} C_q u^q (1+u)^{p-1-2q} \\ = z \sum_{p\ge 0} z^p \sum_{q=0}^{p} {p\choose 2q} C_q u^q (1+u)^{p-2q} \\ = z \sum_{q\ge 0} C_q u^q (1+u)^{-2q} \sum_{p\ge q} {p\choose 2q} z^p (1+u)^p \\ = z \sum_{q\ge 0} C_q u^q (1+u)^{-2q} \sum_{p\ge 2q} {p\choose 2q} z^p (1+u)^p \\ = z \sum_{q\ge 0} C_q u^q (1+u)^{-2q} (1+u)^{2q} z^{2q} \sum_{p\ge 0} {p+2q\choose 2q} z^p (1+u)^p \\ = z \sum_{q\ge 0} C_q u^q z^{2q} \frac{1}{(1-z(1+u))^{2q+1}}.$$

Using the generating function of the Catalan numbers $$Q(w) = \sum_{q\ge 0} C_q w^q = \frac{1-\sqrt{1-4w}}{2w}$$

which has functional equation $$Q(w) = 1 + w Q(w)^2$$

we obtain $$Q\left(\frac{uz^2}{(1-z(1+u))^2}\right) = 1 + \frac{uz^2}{(1-z(1+u))^2} Q\left(\frac{uz^2}{(1-z(1+u))^2}\right)^2$$

which is $$G(z, u) \frac{1-z(1+u)}{z} = 1 + u G(z, u)^2.$$

Extract the coefficient in $z$ first. We get from the functional equation $$z = \frac{G(z,u)}{u G(z,u)^2 + (1+u) G(z,u) + 1}.$$

The coefficient extractor integral is $$[z^n] G(z, u) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} G(z, u)^{k+1} \; dz.$$

which becomes with $G(z, u) = v$

$$\frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(uv^2+(1+u)v+1)^{n+1}}{v^{n+1}} \\ \times v^{k+1} \left(\frac{1}{uv^2+(1+u)v+1} - \frac{v}{(uv^2+(1+u)v+1)^2}(2uv+(1+u))\right) \; dv \\ = \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(uv^2+(1+u)v+1)^{n-1}}{v^{n-k}} (1 - uv^2) \; dv.$$

This is $$\frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n-1} (1+uv)^{n-1}}{v^{n-k}} (1 - uv^2) \; dv.$$

Extracting the coefficient on $[u^l]$ we get two pieces which are, first piece $A$

$${n-1\choose l} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n-1} v^l}{v^{n-k}} \; dv = {n-1\choose l} {n-1\choose n-k-l-1}$$

which is $${n-1\choose l} {n-1\choose k+l} = {n-1\choose l} \frac{k+l+1}{n} {n\choose k+l+1} \\ = (n-l)\frac{k+l+1}{n^2} {n\choose l} {n\choose k+l+1}.$$

and piece $B$ which is $$- {n-1\choose l-1} \frac{1}{2\pi i} \int_{|v|=\epsilon} \frac{(1+v)^{n-1} v^{l-1}}{v^{n-k}} \; v^2 dv = -{n-1\choose l-1} {n-1\choose n-k-l-2}$$

which is $$- {n-1\choose l-1} {n-1\choose k+l+1} = - {n-1\choose l-1} \frac{n-k-l-1}{n} {n\choose k+l+1} \\ = - l \frac{n-k-l-1}{n^2} {n\choose l} {n\choose k+l+1}.$$

Collecting the two pieces we finally obtain $$\left((n-l)\frac{k+l+1}{n^2} + l \frac{-n+k+l+1}{n^2} \right) {n\choose l} {n\choose k+l+1} \\ = \left(n\frac{k+l+1}{n^2} + l \frac{-n}{n^2} \right) {n\choose l} {n\choose k+l+1} \\ = \frac{k+1}{n} {n\choose l} {n\choose k+l+1}$$

as claimed, QED.

Remark. The closed form of $G(z,u)$ can be computed as follows: $$\frac{z}{1-z(1+u)} \frac{1-\sqrt{1-4uz^2/(1-z(1+u))^2}}{2 uz^2/(1-z(1+u))^2} \\ = \frac{z}{(1-z(1+u))^2} \frac{1-z(1+u)-\sqrt{1-2z(1+u)+z^2(1+u)^2-4uz^2}}{2 uz^2/(1-z(1+u))^2} \\ = \frac{1-z(1+u)-\sqrt{1-2z(1+u)+z^2(1+u)^2-4uz^2}}{2 uz}.$$

The above material incorporates data from OEIS A055151 and from OEIS A001263 on Narayana numbers.

I originally deleted this question because I found a solution that I didn't want to bother typing. I didn't think there was any interest in the question. However, I have been asked to undelete it, so I have done so. I have also included my solution here.

Define $N_k(n,r)=\displaystyle{\frac{k+1}{n}{n\choose r+k}{n\choose r-1}}$ so that $N(n,r)=N_0(n,r)$.

Let $L$ be the set of lattice paths that use the steps $(1,0)$, $(0,1)$, $(-1,0)$, and $(0,-1)$ and never pass below the $x$-axis. Let $w_p(u,v)$ be the number of paths in $L$ that start at $(0,0)$, end at $(u,v)$, and use exactly $p$ steps. It is known that $$N_k(n,r)=w_{n-1}(2r-n+k-1,k).$$

Choose a composition $(i_0,i_1,\ldots,i_k)$ of $n$ and a weak composition $(j_0,j_1,\ldots,j_k)$ of $\ell$. For each $t\in\{0,1,\ldots,k\}$, form a lattice path $\mathscr P_t$ in $L$ that starts at $(0,0)$, ends at $(2j_t-i_t+1,0)$, and uses exactly $i_t-1$ steps. The equation above tells us that the number of ways to choose each path $\mathscr P_t$ is $N(i_t,j_t+1)$, so the number of ways to make all of these choices is $A(n,k,\ell)$. Now, translate each of the paths $\mathscr P_1,\mathscr P_2,\ldots,\mathscr P_k$ so that the new starting point of the path $\mathscr P_t$ is one unit above the new ending point of $\mathscr P_{t-1}$. Attach the new endpoint of $\mathscr P_{t-1}$ to the new starting point of $\mathscr P_t$ a $(0,1)$ step. The result is a lattice path $P$ in $L$ that starts at $(0,0)$, ends at $(2\ell-n+k+1,k)$, and uses exactly $n-1$ steps. The new ending point of $\mathscr P_t$ is the last point in $P$ whose $y$-coordinate is $t$. Therefore, if we are given the path $P$, we can determine exactly which composition $(i_0,i_1,\ldots,i_k)$, weak composition $(j_0,j_1,\ldots,j_k)$, and paths $\mathscr P_0,\mathscr P_1,\ldots,\mathscr P_k$ were used to obtain it. This shows that $$A(n,k,\ell)=w_{n-1}(2\ell-n+k+1,k)=N_k(n,\ell+1)=\frac{k+1}{n}{n\choose \ell+k+1}{n\choose \ell}.$$

• Thank you for undeleting the question. Oct 27 '15 at 5:14
• No problem. Sorry I deleted it in the first place. Oct 27 '15 at 5:35