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