login
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.
6
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,2
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
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.
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)
EXAMPLE
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}
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 *)
PROG
(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
CROSSREFS
T(2*n, n) = A008977(n).
Cf. A007318 (Pascal, m=1), this sequence (m=2), A320824 (m=3).
Sequence in context: A138801 A188958 A141902 * A143084 A188962 A076741
KEYWORD
easy,nice,nonn,tabl
AUTHOR
Martin Wohlgemuth, Mar 24 2002
STATUS
approved