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}.$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.