login
Irregular triangle read by rows: T(n, k) is the number of 2n-step closed walks on the square lattice having algebraic area k; n >= 0, 0 <= k <= floor(n^2/4).
3

%I #14 Oct 09 2024 21:29:00

%S 1,4,28,4,232,72,12,2156,1008,308,48,8,21944,13160,5540,1560,420,80,

%T 20,240280,168780,87192,33628,11964,3636,1200,264,72,12,2787320,

%U 2168544,1291220,610232,262612,101976,40376,13720,4900,1512,420,112,28

%N Irregular triangle read by rows: T(n, k) is the number of 2n-step closed walks on the square lattice having algebraic area k; n >= 0, 0 <= k <= floor(n^2/4).

%C Rows can be extended to negative k with T(n, -k) = T(n, k). Sums of such extended rows give A002894.

%C T(n, k) is the number of words of length 2n equal to z^k in the Heisenberg group, presented as <x, y | [x,z], [y,z]>, where z=[x,y]. In particular, T(n, 0) = A307468(n).

%H Cédric Béguin, Alain Valette and Andrzej Zuk, <a href="https://doi.org/10.1016/S0393-0440(96)00024-1">On the spectrum of a random walk on the discrete Heisenberg group and the norm of Harper's operator</a>, Journal of Geometry and Physics, 21 (1997), 337-356.

%H Li Gan, <a href="https://theses.hal.science/tel-04413106">Algebraic Area of Lattice Random Walks and Exclusion Statistics</a>, PhD thesis, Université Paris-Saclay, 2023. See Section 2.1.2, in particular Table 2.1 (divide terms in rows with nonzero A by 2 to get this table).

%H Stefan Mashkevich and Stéphane Ouvry, <a href="https://doi.org/10.1007/s10955-009-9827-9">Area Distribution of Two-Dimensional Random Walks on a Square Lattice</a>, J. Stat. Phys., 137 (2009), 71-78.

%H Morteza Mohammad-Noori, <a href="https://arxiv.org/abs/1012.3720">Enumeration of closed random walks in the square lattice according to their areas</a>, arXiv:1012.3720 [math.CO], 2010. Published as: Morteza Mohammad-Noori, Enumeration of walks in the square lattice according to their areas, Journal of Combinatorial Mathematics and Combinatorial Computing, 91 (2014), 257-274.

%e The table begins:

%e 1

%e 4

%e 28, 4

%e 232, 72, 12

%e 2156, 1008, 308, 48, 8

%e 21944, 13160, 5540, 1560, 420, 80, 20

%e 240280, 168780, 87192, 33628, 11964, 3636, 1200, 264, 72, 12

%e ...

%e T(2, 0) = 28: the 4-step walks enclosing algebraic area 0 include 16 walks of the form "some two steps, then two steps right back" and 12 walks of the form "some step, step back, a different step, step back".

%e T(2, 1) = 4: the 4-step walks enclosing algebraic area 1 are the walks around each of the 4 squares touching the origin in the positive direction; cf. A334756(2, 1) = 8, which also counts walks around these squares in the negative direction.

%t z[0, 0, 0, 0] = 1;

%t z[-1, __] = z[_, -1, __] = z[_, _, -1, _] = z[_, _, _, -1] = 0;

%t z[m1_, m2_, l1_, l2_] := z[m1, m2, l1, l2] = Expand[z[m1, m2, l1 - 1, l2] + z[m1, m2, l1, l2 - 1] + q^(l2 - l1) z[m1 - 1, m2, l1, l2] + q^(l1 - l2) z[m1, m2 - 1, l1, l2]];

%t zN[n_] := Sum[z[m, m, n/2 - m, n/2 - m], {m, 0, n/2}];

%t walks[n_] := Module[{gf = zN[2 n], e}, e = Exponent[gf, q, Max]; CoefficientList[gf q^e, q][[e + 1 ;;]]];

%t Table[walks[n], {n, 0, 8}]

%Y Row lengths are A033638 = A002620 + 1.

%Y Row n ends with 4 * A026741(n) for n > 0.

%Y Row 16 is A178106.

%Y Cf. A307468, A002894, A353091.

%Y A334756 counts self-avoiding walks only.

%K nonn,tabf,walk

%O 0,2

%A _Andrey Zabolotskiy_, Apr 05 2022