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

1, 4, 12, 2, 40, 8, 4, 124, 42, 16, 6, 2, 416, 160, 92, 28, 16, 4, 4, 1348, 678, 362, 174, 88, 34, 22, 8, 6, 2, 4624, 2548, 1624, 756, 460, 200, 156, 56, 40, 20, 12, 4, 4, 15632, 10062, 6336, 3586, 2110, 1106, 742, 388, 278, 152, 82, 46, 34, 14, 8, 6, 2

Offset: 0

Author

Andrei Zabolotskii, Aug 04 2025

Keywords

• nonn
• tabf

Comments

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

The algebraic area is Integral y dx over the walk, which equals (Sum_{steps right} y) - (Sum_{steps left} y).

Examples

			The triangle begins:
     1
     4
    12,   2
    40,   8,   4
   124,  42,  16,   6,  2
   416, 160,  92,  28, 16,  4,  4
  1348, 678, 362, 174, 88, 34, 22, 8, 6, 2
   ...
T(3, 1) = 8: RUR (right, up, right), LUR, RDL, LDL, URU, URD, DLU, DLD.
		

Crossrefs

Row lengths are A033638 = A002620 + 1.

A352838 is an analog that gives the number of closed walks.

Cf. A029552, A098613.

Programs

Python

d = [{((0, 0), 0): 1}]
for _ in range(10):
    nd = {}
    for key, nw in d[-1].items():
        pos, ar = key
        x, y = pos
        for key in [
            ((x+1, y), ar + y),
            ((x-1, y), ar - y),
            ((x, y+1), ar),
            ((x, y-1), ar)
            ]:
            if key in nd:
                nd[key] += nw
            else:
                nd[key] = nw
    d.append(nd)
t = []
for nd in d:
    a = [0] * (max(ar for _, ar in nd) + 1)
    for key, nw in nd.items():
        _, ar = key
        if ar >= 0:
            a[ar] += nw
    t.append(a)
print(t)

Formula

It appears that T(2*n, n^2 - k) = 2 * A029552(k) for k < n and T(2*n+1, n^2+n - k) = 4 * A098613(k) for k < n.