§26.6 Other Lattice Path Numbers

§26.6(i) Definitions

Delannoy 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}\genfrac{(}{)}{0.0pt}{}{n}{k}\genfrac{(}{)}{0.0pt}{}{m+n-% k}{n}=\sum_{k=0}^{n}2^{k}\genfrac{(}{)}{0.0pt}{}{m}{k}\genfrac{(}{)}{0.0pt}{}{% n}{k}.$ ⓘ Defines: $D(m,n)$: Delannoy number (locally) Symbols: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{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 also: Annotations for §26.6(i), §26.6(i), §26.6 and Ch.26

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}\genfrac{(}{)}{0.0pt}{}{n}{k}\genfrac% {(}{)}{0.0pt}{}{2n+2-2k}{n+1-k}.$ ⓘ Defines: $M(n)$: Motzkin number (locally) Symbols: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$: binomial coefficient, $k$: nonnegative integer and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.6.E2 Encodings: TeX, pMML, png See also: Annotations for §26.6(i), §26.6(i), §26.6 and Ch.26

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}\genfrac{(}{)}{0.0pt}{}{n}{k}\genfrac{(}{)}{0.0pt}{}{n}{k-1}.$ ⓘ Defines: $N(n,k)$: Narayana number (locally) Symbols: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$: binomial coefficient, $k$: nonnegative integer and $n$: nonnegative integer Permalink: http://dlmf.nist.gov/26.6.E3 Encodings: TeX, pMML, png See also: Annotations for §26.6(i), §26.6(i), §26.6 and Ch.26

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 (locally) Symbols: $n$: nonnegative integer and $D(m,n)$: Delannoy number Referenced by: §26.6(i) Permalink: http://dlmf.nist.gov/26.6.E4 Encodings: TeX, pMML, png See also: Annotations for §26.6(i), §26.6(i), §26.6 and Ch.26

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},$ ⓘ Symbols: $m$: nonnegative integer, $n$: nonnegative integer, $D(m,n)$: Delannoy number, $x$: small and $y$: small Permalink: http://dlmf.nist.gov/26.6.E5 Encodings: TeX, pMML, png See also: Annotations for §26.6(ii), §26.6 and Ch.26
 26.6.6 $\sum_{n=0}^{\infty}D(n,n)x^{n}=\frac{1}{\sqrt{1-6x+x^{2}}},$ ⓘ Symbols: $n$: nonnegative integer, $D(m,n)$: Delannoy number and $x$: small Permalink: http://dlmf.nist.gov/26.6.E6 Encodings: TeX, pMML, png See also: Annotations for §26.6(ii), §26.6 and Ch.26
 26.6.7 $\sum_{n=0}^{\infty}M(n)x^{n}=\frac{1-x-\sqrt{1-2x-3x^{2}}}{2x^{2}},$ ⓘ Symbols: $n$: nonnegative integer, $M(n)$: Motzkin number and $x$: small Referenced by: §26.6(iii) Permalink: http://dlmf.nist.gov/26.6.E7 Encodings: TeX, pMML, png See also: Annotations for §26.6(ii), §26.6 and Ch.26
 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},$ ⓘ Symbols: $k$: nonnegative integer, $n$: nonnegative integer, $N(n,k)$: Narayana number, $x$: small and $y$: small Permalink: http://dlmf.nist.gov/26.6.E8 Encodings: TeX, pMML, png See also: Annotations for §26.6(ii), §26.6 and Ch.26
 26.6.9 $\sum_{n=0}^{\infty}r(n)x^{n}=\frac{1-x-\sqrt{1-6x+x^{2}}}{2x}.$ ⓘ Symbols: $n$: nonnegative integer, $r(n)$: Schröder number and $x$: small Permalink: http://dlmf.nist.gov/26.6.E9 Encodings: TeX, pMML, png See also: Annotations for §26.6(ii), §26.6 and Ch.26

§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: $m$: nonnegative integer, $n$: nonnegative integer and $D(m,n)$: Delannoy number Referenced by: §26.6(iii) Permalink: http://dlmf.nist.gov/26.6.E10 Encodings: TeX, pMML, png See also: Annotations for §26.6(iii), §26.6 and Ch.26 26.6.11 $\displaystyle M(n)$ $\displaystyle=M(n-1)+\sum_{k=2}^{n}M(k-2)\,M(n-k),$ $n\geq 2$. ⓘ Symbols: $k$: nonnegative integer, $n$: nonnegative integer and $M(n)$: Motzkin number Referenced by: §26.6(iii) Permalink: http://dlmf.nist.gov/26.6.E11 Encodings: TeX, pMML, png See also: Annotations for §26.6(iii), §26.6 and Ch.26

§26.6(iv) Identities

 26.6.12 $C\left(n\right)=\sum_{k=1}^{n}N(n,k),$ ⓘ Symbols: $C\left(\NVar{n}\right)$: Catalan number, $k$: nonnegative integer, $n$: nonnegative integer and $N(n,k)$: Narayana number Permalink: http://dlmf.nist.gov/26.6.E12 Encodings: TeX, pMML, png See also: Annotations for §26.6(iv), §26.6 and Ch.26
 26.6.13 $M(n)=\sum_{k=0}^{n}(-1)^{k}\genfrac{(}{)}{0.0pt}{}{n}{k}C\left(n+1-k\right),$
 26.6.14 $C\left(n\right)=\sum_{k=0}^{2n}(-1)^{k}\genfrac{(}{)}{0.0pt}{}{2n}{k}M(2n-k).$