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
and for an integer
, the Narayana number
is defined by
![{\displaystyle N(n,k)={\frac {1}{n}}{n \choose k}{n \choose k-1}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9366087addcf2bcc31b5737210d537b93f17454)
The number
is defined as
for
and as
for
.
For a nonnegative integer
, the
-th Narayana polynomial
is defined by
![{\displaystyle N_{n}(z)=\sum _{k=0}^{n}N(n,k)z^{k}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aef18669bdb90f02aa115a117db11ca27ef8847b)
The associated Narayana polynomial
is defined as the reciprocal polynomial of
:
.
Examples
The first few Narayana polynomials are
![{\displaystyle N_{0}(z)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c565ac84fee7392d48163229747d2a5eae55fda)
![{\displaystyle N_{1}(z)=z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76a616554ea5b077418c476822ca75cacd982cd7)
![{\displaystyle N_{2}(z)=z^{2}+z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ba9c7f42490a21ab762261e823b11fc12fdd220)
![{\displaystyle N_{3}(z)=z^{3}+3z^{2}+z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7d1ee5cd3ea0a912420175dfe68f49a1f840f6da)
![{\displaystyle N_{4}(z)=z^{4}+6z^{3}+6z^{2}+z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/810ac86f0058a50ccfefb8130d33ccb2b424d6f6)
![{\displaystyle N_{5}(z)=z^{5}+10z^{4}+20z^{3}+10z^{2}+z}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4285732079e9452837f9cbebf5337b8b029adf96)
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.
The Narayana polynomials can be expressed in the following alternative form:[4]
![{\displaystyle N_{n}(z)=\sum _{0}^{n}{\frac {1}{n+1}}{n+1 \choose k}{2n-k \choose n}(z-1)^{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/038c38ac876a8be38c69d067806867e81a73c459)
Special values
is the
-th Catalan number
. The first few Catalan numbers are
. (sequence A000108 in the OEIS).[5]
is the
-th large Schröder number. This is the number of plane trees having
edges with leaves colored by one of two colors. The first few Schröder numbers are
. (sequence A006318 in the OEIS).[5] - For integers
, let
denote the number of underdiagonal paths from
to
in a
grid having step set
. Then
.[6]
Recurrence relations
- For
,
satisfies the following nonlinear recurrence relation:[6]
.
- For
,
satisfies the following second order linear recurrence relation:[6]
with
and
.
Generating function
The ordinary generating function the Narayana polynomials is given by
![{\displaystyle \sum _{n=0}^{\infty }N_{n}(z)t^{n}={\frac {1+t-tz-{\sqrt {1-2(1+z)t+(1-z)^{2}t^{2}}}}{2t}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3025e5889d39b76918023e0450ac2af7ced1593)
Integral representation
The
-th degree Legendre polynomial
is given by
![{\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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d64a6a63e133a41306b73607de1b25e6f71cfc58)
Then, for n > 0, the Narayana polynomial
can be expressed in the following form:
.
See also
References
- ^ D. G. Rogers (1981). "Rhyming schemes: Crossings and coverings" (PDF). Discrete Mathematics. 33: 67–77. doi:10.1016/0012-365X(81)90259-4. 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" (PDF). Discrete Mathematics. 98 (3): 193–206. doi:10.1016/0012-365X(91)90376-D. Retrieved 2 December 2023.
- ^ Ricky X. F. Chen and Christian M. Reidys (2014). "Narayana polynomials and some generalizations". arXiv:1411.2530 [math.CO].
- ^ a b Toufik Mansour, Yidong Sun (2008). "Identities involving Narayana polynomials and Catalan numbers". arXiv:0805.1274 [math.CO].
- ^ a b c Curtis Coker (2003). "Enumerating a class oflattice paths" (PDF). Discrete Mathematics. 271 (1–3): 13–28. doi:10.1016/S0012-365X(03)00037-2. Retrieved 1 December 2023.