The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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 (list; table; graph; refs; listen; history; text; internal format)
 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. G. Pólya, Über eine Aufgabe der Wahrscheinlichkeitsrechnung betreffend die Irrfahrt im Straßennetz, Mathematische Annalen, 84 (1921), 149-160. 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. A002894, A000984. Cf. A007318 (Pascal, m=1), this sequence (m=2), A320824 (m=3). Sequence in context: A138801 A188958 A141902 * A143084 A188962 A076741 Adjacent sequences:  A069463 A069464 A069465 * A069467 A069468 A069469 KEYWORD easy,nice,nonn,tabl AUTHOR Martin Wohlgemuth, Mar 24 2002 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 4 21:22 EDT 2022. Contains 357240 sequences. (Running on oeis4.)