An identity involving Narayana numbers (Q2426447)

From MaRDI portal
scientific article
Language Label Description Also known as
English
An identity involving Narayana numbers
scientific article

    Statements

    An identity involving Narayana numbers (English)
    0 references
    0 references
    0 references
    22 April 2008
    0 references
    Narayana's numbers, defined by \(N_{n,k}=\frac 1n \binom nk \binom n{k-1}\) count the number of plane trees with \(n\) edges and \(k\) leaves. The matrix \((N_{n,k})\) is lower triangular. Motivated by some observed identities involving the product of several elements of this matrix, the authors use a bijective algorithm of \textit{W.Y.C. Chen} [Proc. Natl. Acad. Sci. USA 87, No. 24, 9635--9639 (1990; Zbl 0707.05019)] and a related involution to give a combinatorial proof of the following general identity, for all \(m\geq 0\) \[ \begin{aligned} & N_{n,k+m-1}N_{n+1,k+m-2}N_{n+2,k+m-3}\cdots N_{n+m-2,k+1}N_{n+m-1,k}N_{n+m,k+m}\\ & =N_{n,k}N_{n+1,k+m}N_{n+2,k+m-1}\cdots N_{n+m-2,k+3}N_{n+m-1,k+2}N_{n+m,k+1} \end{aligned} \] The cases \(m=2\) and \(m=n=4, k=1\) yield the two motivating identities.
    0 references
    0 references
    Narayana numbers
    0 references
    labelled plane trees
    0 references
    0 references