A227997 Triangular array read by rows. T(n,k) is the number of square lattice walks that start and end at the origin after 2n steps having k primitive loops; n>=1, 1<=k<=n.

4, 20, 16, 176, 160, 64, 1876, 1808, 960, 256, 22064, 22048, 13248, 5120, 1024, 275568, 282528, 182528, 83456, 25600, 4096, 3584064, 3747456, 2542464, 1284096, 481280, 122880, 16384, 47995476, 50981136, 35851968, 19365120, 8186880, 2617344, 573440, 65536, 657037232, 707110432, 511288256, 290053120, 133084160, 48799744, 13647872, 2621440, 262144, 9150655216, 9958458656, 7363711104, 4338317824, 2113592320, 851398656, 276856832, 68943872, 11796480, 1048576

Offset

1,1

Comments

The walk consists of steps in the four directions NW,NE,SW,SE. A primitive loop is a walk that starts and ends at the origin but does not otherwise touch the origin.

Row sums are A002894.

Column 1 is A054474

Links

Table of n, a(n) for n=1..55.

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 90.

Formula

G.f.: 1/( 1 - y*(1 - 1/A(x)) ) where A(x) is the o.g.f. for A002894.

Example

4,
20, 16,
176, 160, 64,
1876, 1808, 960, 256,
22064, 22048, 13248, 5120, 1024,
275568, 282528, 182528, 83456, 25600, 4096

Mathematica

nn=6; a=Sum[Binomial[2n, n]^2x^n, {n, 0, nn}]; Map[Select[#, #>0&]&, Drop[CoefficientList[Series[1/(1-y(1-1/a)), {x, 0, nn}], {x, y}], 1]]//Grid

Crossrefs

Sequence in context: A213822 A182456 A196380 * A130316 A131745 A261755

Adjacent sequences: A227994 A227995 A227996 * A227998 A227999 A228000

Keyword

nonn,walk,tabl

Author

Geoffrey Critzer, Oct 04 2013

Status

approved