login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

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 (mail(AT)matroid.com), 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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 21 21:30 EST 2020. Contains 331128 sequences. (Running on oeis4.)