A069466 Triangle T(n, k) of numbers of square lattice walks that start and end at origin after 2*n steps and contain exactly k steps to the east, possibly touching origin at intermediate stages.

1, 2, 2, 6, 24, 6, 20, 180, 180, 20, 70, 1120, 2520, 1120, 70, 252, 6300, 25200, 25200, 6300, 252, 924, 33264, 207900, 369600, 207900, 33264, 924, 3432, 168168, 1513512, 4204200, 4204200, 1513512, 168168, 3432, 12870, 823680, 10090080, 40360320, 63063000, 40360320, 10090080, 823680, 12870

Offset: 0

Author

Martin Wohlgemuth, Mar 24 2002

Keywords

• easy
• nice
• nonn
• tabl

Comments

A Pólya plane walk takes steps (N,E,S,W) along cardinal directions in the plane, visiting only points of Z^2 (cf. Links). T(n,k) is the number of walks departing from and returning to the origin, with exactly 2*k steps along the NS axis and 2*(n-k) steps along the EW direction. Equivalently, triangle T(n,k) is the number of distinct permutations of a 2*n-letter word with letters (N,E,S,W) in multiplicity (k,n-k,k,n-k). Moving only along either NS or EW directions, T(n,0) = T(n,n) = A000894(n). Row sums appear as Equation 4 in the original Pólya article, Sum_{k=0..n} T(n,k) = A002894(n). This identity is proven routinely using Zeilberger's algorithm. - Bradley Klee, Aug 12 2018

Examples

			Triangle begins:
    1,
    2,    2,
    6,   24,     6,
   20,  180,   180,    20,
   70, 1120,  2520,  1120,   70,
  252, 6300, 25200, 25200, 6300, 252
  ...
T(4,2) = 2520 because there are 2520 distinct lattice walks of length 2*4=8 starting and ending at the origin and containing exactly 2 steps to the east.
For T(2,k), the lattice-path words are:
T(2,0):{EEWW, WEEW, WWEE, EWWE, WEWE, EWEW}
T(2,1):{NESW, NEWS, NSEW, NSWE, NWES, NWSE, ENSW, ENWS, ESNW, ESWN, EWNS, EWSN, SNEW, SNWE, SENW, SEWN, SWNE, SWEN, WNES, WNSE, WENS, WESN, WSNE, WSEN}
T(2,2):{NNSS, SNNS, SSNN, NSSN, SNSN, NSNS}
		

Links

• Muniru A Asiru, Table of n, a(n) for n = 0..1325 (Rows n=0..50, flattened)
• A. Bostan, Calcul Formel pour la Combinatoire des Marches, Habilitation à Diriger des Recherches, Université Paris 13, 2017, page 11.
• G. Pólya, Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz, Mathematische Annalen, 84 (1921), 149-160.

Crossrefs

T(2*n, n) = A008977(n).

Cf. A002894, A000984.

Cf. A007318 (Pascal, m=1), this sequence (m=2), A320824 (m=3).

Programs

GAP

T:=Flat(List([0..8],n->List([0..n],k->Binomial(2*n,n)*(Binomial(n,k))^2))); # Muniru A Asiru, Oct 21 2018

Maple

T:=(n,k)->binomial(2*n,n)*(binomial(n,k))^2: seq(seq(T(n,k),k=0..n),n=0..8); # Muniru A Asiru, Oct 21 2018

Mathematica

T[k_, r_] := Binomial[2k, k]*Binomial[k, r]^2; Table[T[k, r], {k, 0, 8}, {r, 0, k}] // Flatten (* Jean-François Alcover, Nov 21 2012, from explicit formula *)

Formula

Recurrences: T(1, 0) = T(1, 1)=2; T(k, r) = 2*k*(2*k-1)/(k-r)^2 * T(k-1, r); T(k, r) = (k+1-r)^2/r^2 * T(k, r-1).

T(n, k) = binomial(2*n, n) * binomial(n, k)^2.

Sum_{k=0..n} T(n, k) = A002894(n).

From Bradley Klee, Aug 12 2018: (Start)

T(n,k) = (2*n)!/((n-k)!*k!)^2.

T(n,k) = C(2*n,2*k)*C(2*(n-k),n-k)*C(2*k,k).

Sum_{k=0..n} T(n,k) = Sum_{k=0..n} C(2*n,2*k)*C(2*(n-k),n-k)*C(2*k,k) = C(2*n,n)^2.

Sum_{k=0..n} T(n,k) = Sum_{k=0..n} (2n)!/(k!(n-k)!)^2 = C(2*n,n)^2.

(End)