|
%I #53 Apr 20 2020 02:27:19
%S 1,2,2,6,24,6,20,180,180,20,70,1120,2520,1120,70,252,6300,25200,25200,
%T 6300,252,924,33264,207900,369600,207900,33264,924,3432,168168,
%U 1513512,4204200,4204200,1513512,168168,3432,12870,823680,10090080,40360320,63063000,40360320,10090080,823680,12870
%N 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.
%C 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
%H Muniru A Asiru, <a href="/A069466/b069466.txt">Table of n, a(n) for n = 0..1325</a> (Rows n=0..50, flattened)
%H A. Bostan, <a href="https://specfun.inria.fr/bostan/HDR.pdf">Calcul Formel pour la Combinatoire des Marches</a>, Habilitation à Diriger des Recherches, Université Paris 13, 2017, page 11.
%H G. Pólya, <a href="https://eudml.org/doc/158886">Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz</a>, Mathematische Annalen, 84 (1921), 149-160.
%F 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).
%F T(n, k) = binomial(2*n, n) * binomial(n, k)^2.
%F Sum_{k=0..n} T(n, k) = A002894(n).
%F From _Bradley Klee_, Aug 12 2018: (Start)
%F T(n,k) = (2*n)!/((n-k)!*k!)^2.
%F T(n,k) = C(2*n,2*k)*C(2*(n-k),n-k)*C(2*k,k).
%F 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.
%F Sum_{k=0..n} T(n,k) = Sum_{k=0..n} (2n)!/(k!(n-k)!)^2 = C(2*n,n)^2.
%F (End)
%e Triangle begins:
%e 1,
%e 2, 2,
%e 6, 24, 6,
%e 20, 180, 180, 20,
%e 70, 1120, 2520, 1120, 70,
%e 252, 6300, 25200, 25200, 6300, 252
%e ...
%e 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.
%e For T(2,k), the lattice-path words are:
%e T(2,0):{EEWW, WEEW, WWEE, EWWE, WEWE, EWEW}
%e 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}
%e T(2,2):{NNSS, SNNS, SSNN, NSSN, SNSN, NSNS}
%p 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
%t 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 *)
%o (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
%Y T(2*n, n) = A008977(n).
%Y Cf. A002894, A000984.
%Y Cf. A007318 (Pascal, m=1), this sequence (m=2), A320824 (m=3).
%K easy,nice,nonn,tabl
%O 0,2
%A _Martin Wohlgemuth_, Mar 24 2002
|
