Narayana polynomials
Narayana polynomials are a class of polynomials whose coefficients are the Narayana numbers. The Narayana numbers and Narayana polynomials are named after the Canadian mathematician T. V. Narayana (1930–1987). They appear in several combinatorial problems.[1][2][3]
Definitions
For a positive integer [math]\displaystyle{ n }[/math] and for an integer [math]\displaystyle{ k }[/math] such that [math]\displaystyle{ 1\le k\le n }[/math], the Narayana number [math]\displaystyle{ N(n,k) }[/math] is defined by
- [math]\displaystyle{ N(n,k) = \frac{1}{n}{n \choose k}{n\choose k-1}. }[/math]
The number [math]\displaystyle{ N(0,0) }[/math] is defined as [math]\displaystyle{ 1 }[/math]. For a positive integer [math]\displaystyle{ n }[/math], the [math]\displaystyle{ n }[/math]-th Narayana polynomial [math]\displaystyle{ N_n(z) }[/math] is defined by
- [math]\displaystyle{ N_n(z) = \sum_{k=1}^n N(n,k)z^n }[/math].
The polynomial [math]\displaystyle{ N_0(z) }[/math] is defined as the constant polynomial [math]\displaystyle{ 1 }[/math]. The associated Narayana polynomial [math]\displaystyle{ \mathcal N_n(z) }[/math] is defined by
- [math]\displaystyle{ \mathcal N_n(z)=z^nN_n\left(\tfrac{1}{z}\right) }[/math].
The first few Narayana polynomials are
- [math]\displaystyle{ N_0(z)=1 }[/math]
- [math]\displaystyle{ N_1(z)=z }[/math]
- [math]\displaystyle{ N_2(z)=z^2+z }[/math]
- [math]\displaystyle{ N_3(z)=z^3+3z^2+z }[/math]
- [math]\displaystyle{ N_4(z)=z^4+6z^3+6z^2+z }[/math]
- [math]\displaystyle{ N_5(z)=z^5+10z^4+20z^3+10z^2+z }[/math]
Properties
A few of the properties of the Narayana polynomials and the associated Narayana polynomials are collected below. Further information on the properties of these polynomials are available in the references cited.
Alternative form of the Narayana polynomials
The Narayana polynomials can be expressed in the following alternative form:[4]
- [math]\displaystyle{ N_n(z)= \sum_0^n \frac{1}{n+1}{n+1 \choose k}{2n-k \choose n}(z-1)^k }[/math]
Special values
- [math]\displaystyle{ N_n(1) }[/math] is the [math]\displaystyle{ n }[/math]-th Catalan number [math]\displaystyle{ C_n=\frac{1}{n+1}{2n \choose n} }[/math]. The first few Catalan numbers are [math]\displaystyle{ 1, 1, 2, 5, 14, 42, 132, 429, \ldots }[/math]. (sequence A000108 in the OEIS).[5]
- [math]\displaystyle{ N_n(2) }[/math] is the [math]\displaystyle{ n }[/math]-th large Schröder number. This is the number of plane trees having [math]\displaystyle{ n }[/math] edges with leaves colored by one of two colors. The first few Schröder numbers are [math]\displaystyle{ 1, 2, 6, 22, 90, 394, 1806, 8558, \ldots }[/math]. (sequence A006318 in the OEIS).[5]
- For integers [math]\displaystyle{ n\ge 0 }[/math], let [math]\displaystyle{ d_n }[/math] denote the number of underdiagonal paths from [math]\displaystyle{ (0,0) }[/math] to [math]\displaystyle{ (n,n) }[/math] in a [math]\displaystyle{ n\times n }[/math] grid having step set [math]\displaystyle{ S = \{(k, 0) : k \in \mathbb N^+\} \cup \{(0, k) : k \in \mathbb N^+\} }[/math]. Then [math]\displaystyle{ d_n = \mathcal N(4) }[/math].[6]
Recurrence relations
- For [math]\displaystyle{ n \ge 3 }[/math], [math]\displaystyle{ \mathcal N_n(z) }[/math] satisfies the following nonlinear recurrence relation:[6]
- [math]\displaystyle{ \mathcal N_n(z) = (1+z)N_{n-1}(z) + z \sum_{k=1}^{n-2}\mathcal N_k(z)\mathcal N_{n-k-1}(z) }[/math].
- For [math]\displaystyle{ n\ge 3 }[/math], [math]\displaystyle{ \mathcal N_n(z) }[/math] satisfies the following second order linear recurrence relation:[6]
- [math]\displaystyle{ (n+1)\mathcal N_n(z) = (2n-1)(1+z)\mathcal N_{n-1}(z) - (n-2)(z-1)^2\mathcal N_{n-2}(z) }[/math] with [math]\displaystyle{ \mathcal N_1(z)=1 }[/math] and [math]\displaystyle{ \mathcal N_2(z)=1+z }[/math].
Integral representation
The [math]\displaystyle{ n }[/math]-th degree Legendre polynomial [math]\displaystyle{ P_n(x) }[/math] is given by
- [math]\displaystyle{ P_n(x) = 2^{-n}\sum_{k=0}^{\left\lfloor \frac{n}{2}\right\rfloor } (-1)^k {n-k \choose k}{2n-2k \choose n-k}x^{n-2k} }[/math]
Then, the Narayana polynomial [math]\displaystyle{ N_n(z) }[/math] can be expressed in the following form:
- [math]\displaystyle{ N_n(z)=(z-1)^{n+1}\int_0^{\frac{z-1}{z}} P_n(2x-1)\,dx }[/math].
See also
References
- ↑ D. G. Rogers (1981). "Rhyming schemes: Crossings and coverings". Discrete Mathematics 33: 67–77. doi:10.1016/0012-365X(81)90259-4. https://core.ac.uk/download/pdf/82236401.pdf. Retrieved 2 December 2023.
- ↑ R.P. Stanley (1999). Enumerative Combinatorics, Vol. 2. Cambridge University Press.
- ↑ Rodica Simian and Daniel Ullman (1991). "On the structure of the lattice of noncrossing partitions". Discrete Mathematics 98 (3): 193–206. doi:10.1016/0012-365X(91)90376-D. https://core.ac.uk/download/pdf/82065542.pdf. Retrieved 2 December 2023.
- ↑ Ricky X. F. Chen and Christian M. Reidys (2014). "Narayana polynomials and some generalizations". arXiv:1411.2530 [math.CO].
- ↑ 5.0 5.1 Toufik Mansour, Yidong Sun (2008). "Identities involving Narayana polynomials and Catalan numbers". arXiv:0805.1274 [math.CO].
- ↑ 6.0 6.1 6.2 Curtis Coker (2003). "Enumerating a class oflattice paths". Discrete Mathematics 271 (1–3): 13–28. doi:10.1016/S0012-365X(03)00037-2. https://core.ac.uk/download/pdf/82292598.pdf. Retrieved 1 December 2023.
 |  |
