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

Author

Geoffrey Critzer, Oct 04 2013

Keywords

• nonn
• walk
• tabl

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

Examples

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

Links

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

Programs

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

Formula

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