# Dellanoy Number $D(m,n)$

$D(m,n)$ is the number of paths from $(0,0)$ to $(m,n)$ that are composed of directed line segments of the form $(1,0)$, $(0,1)$, or $(1,1)$.

 26.6.1 $D(m,n)=\sum_{k=0}^{n}\binom{n}{k}\binom{m+n-k}{n}=\sum_{k=0}^{n}2^{k}\binom{m}% {k}\binom{n}{k}.$ Defines: $D(m,n)$: Dellanoy number Symbols: $\binom{m}{n}$: binomial coefficient, $k$: nonnegative integer, $m$: nonnegative integer and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.6.E1 Encodings: TeX, pMML, png

See Table 26.6.1.

# Motzkin Number $M(n)$

$M(n)$ is the number of lattice paths from $(0,0)$ to $(n,n)$ that stay on or above the line $y=x$ and are composed of directed line segments of the form $(2,0)$, $(0,2)$, or $(1,1)$.

 26.6.2 $M(n)=\sum_{k=0}^{n}\frac{(-1)^{k}}{n+2-k}\binom{n}{k}\binom{2n+2-2k}{n+1-k}.$ Defines: $M(n)$: Motzkin number Symbols: $\binom{m}{n}$: binomial coefficient, $k$: nonnegative integer and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.6.E2 Encodings: TeX, pMML, png

See Table 26.6.2.

# Narayana Number $N(n,k)$

$N(n,k)$ is the number of lattice paths from $(0,0)$ to $(n,n)$ that stay on or above the line $y=x$, are composed of directed line segments of the form $(1,0)$ or $(0,1)$, and for which there are exactly $k$ occurrences at which a segment of the form $(0,1)$ is followed by a segment of the form $(1,0)$.

 26.6.3 $N(n,k)=\frac{1}{n}\binom{n}{k}\binom{n}{k-1}.$ Defines: $N(n,k)$: Narayana number Symbols: $\binom{m}{n}$: binomial coefficient, $k$: nonnegative integer and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.6.E3 Encodings: TeX, pMML, png

See Table 26.6.3.

# Schröder Number $r(n)$

$r(n)$ is the number of paths from $(0,0)$ to $(n,n)$ that stay on or above the diagonal $y=x$ and are composed of directed line segments of the form $(1,0)$, $(0,1)$, or $(1,1)$.

 26.6.4 $r(n)=D(n,n)-D(n+1,n-1),$ $n\geq 1$. Defines: $r(n)$: Schröder number Symbols: $D(m,n)$: Dellanoy number and $n$: nonnegative integer Referenced by: §26.6(i) Permalink: http://dlmf.nist.gov/26.6.E4 Encodings: TeX, pMML, png

See Table 26.6.4.

# §26.6(ii) Generating Functions

For sufficiently small $|x|$ and $|y|$,

 26.6.5 $\sum_{m,n=0}^{\infty}D(m,n)x^{m}y^{n}=\frac{1}{1-x-y-xy},$
 26.6.6 $\sum_{n=0}^{\infty}D(n,n)x^{n}=\frac{1}{\sqrt{1-6x+x^{2}}},$
 26.6.7 $\sum_{n=0}^{\infty}M(n)x^{n}=\frac{1-x-\sqrt{1-2x-3x^{2}}}{2x^{2}},$ Symbols: $M(n)$: Motzkin number, $n$: nonnegative integer and $x$: small Referenced by: §26.6(iii) Permalink: http://dlmf.nist.gov/26.6.E7 Encodings: TeX, pMML, png
 26.6.8 $\sum_{n,k=1}^{\infty}N(n,k)x^{n}y^{k}=\frac{1-x-xy-\sqrt{(1-x-xy)^{2}-4x^{2}y}% }{2x},$
 26.6.9 $\sum_{n=0}^{\infty}r(n)x^{n}=\frac{1-x-\sqrt{1-6x+x^{2}}}{2x}.$

# §26.6(iii) Recurrence Relations

 26.6.10 $\displaystyle D(m,n)$ $\displaystyle=D(m,n-1)+D(m-1,n)+D(m-1,n-1),$ $m,n\geq 1$, Symbols: $D(m,n)$: Dellanoy number, $m$: nonnegative integer and $n$: nonnegative integer Referenced by: §26.6(iii) Permalink: http://dlmf.nist.gov/26.6.E10 Encodings: TeX, pMML, png 26.6.11 $\displaystyle M(n)$ $\displaystyle=M(n-1)+\sum_{k=2}^{n}M(k-2)\,M(n-k),$ $n\geq 2$. Symbols: $M(n)$: Motzkin number, $k$: nonnegative integer and $n$: nonnegative integer Referenced by: §26.6(iii) Permalink: http://dlmf.nist.gov/26.6.E11 Encodings: TeX, pMML, png

# §26.6(iv) Identities

 26.6.12 $\mathop{C\/}\nolimits\!\left(n\right)=\sum_{k=1}^{n}N(n,k),$
 26.6.13 $M(n)=\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}\mathop{C\/}\nolimits\!\left(n+1-k% \right),$
 26.6.14 $\mathop{C\/}\nolimits\!\left(n\right)=\sum_{k=0}^{2n}(-1)^{k}\binom{2n}{k}M(2n% -k).$