# §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}\binom{n}{k}\binom{m+n-k}{n}=\sum_{k=0}^{n}2^{k}\binom{m}% {k}\binom{n}{k}.$ Defines: $D(m,n)$: Delannoy number (locally) Symbols: $\binom{\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)

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 (locally) Symbols: $\binom{\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)

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 (locally) Symbols: $\binom{\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)

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)

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.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.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.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.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(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.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(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).$