Counting self-avoiding paths on grid graphs

The problem

Take an n × n square grid of points, with each point joined to its immediate neighbours up, down, left and right. That object is the grid graph P_n × P_n. Now count the paths through it that never visit the same point twice — self-avoiding paths.

The question is easy to state and famously hard to answer. There is no known formula. Nobody has found one, and the general problem of counting self-avoiding walks is one of the long-standing open problems of combinatorics and statistical physics. Every term of these sequences has to be computed, and the computations get worse very fast.

How fast is the point. For the 3 × 3 grid there are 653 such paths, a number you could in principle check by hand. For 13 × 13 there are more than 7.7 × 10³⁸ — a 39-digit number. A machine listing them at one path per nanosecond would need roughly a trillion times the present age of the universe to finish. They cannot be enumerated one at a time; they have to be counted without ever being listed.

Why each term costs more than the last

This is A236753 — directed self-avoiding paths on the n × n grid — in full. The right-hand column is each term divided by the one before it, and it is the reason the sequence is flagged hard: the growth rate is itself growing.

The last row is Lara Solomon's contribution, added to the OEIS on 30 July 2026. The previous term, a(12), had stood since the sequence was created by Jaimal Ichharam in January 2014.

The three contributions

1. A236753 Number of simple (non-intersecting) directed paths on the grid graph P_n × P_n a(13) — 30 July 2026

   Created by Jaimal Ichharam, January 2014. Keyword hard. The 13 × 13 value is a 39-digit number:

   779 903 870 849 450 440 101 587 633 989 096 314 113
2. A288032 Number of (undirected) paths in the n × n grid graph a(13) — 30 July 2026

   Created by Eric W. Weisstein, June 2017. The undirected companion, contributed the same day:

   389 951 935 424 725 220 050 793 816 994 548 156 972
3. A288518 Array read by antidiagonals: T(m,n) = number of (undirected) paths in the grid graph P_m × P_n b-file extended from 276 to 351 terms

   The general rectangular case, created by Andrew Howroyd in June 2017. The sequence's data file previously held 276 terms — the first 23 antidiagonals, since 1 + 2 + … + 23 = 276. It now holds 351, or 26 complete antidiagonals: 75 new values covering every rectangle P_m × P_n with m + n up to 27.

How it was computed

The paths are never enumerated. They are counted by a frontier transfer-matrix search: the grid is swept one cell at a time, and the only thing carried forward is the state of the frontier — a boundary of 13 cells recording which of them are currently occupied by a path and how the partial path fragments crossing the boundary are connected to one another. Two partial configurations that agree on the frontier behave identically for the rest of the sweep, so they can be merged and counted together. That collapse is what turns an impossible enumeration into a feasible one.

The counts themselves overflow ordinary machine integers long before n = 13, so the arithmetic is carried out modulo several primes and the true 39-digit value reconstructed afterwards by the Chinese Remainder Theorem.

The result was validated by rerunning the same program over the rectangular case and reproducing all 276 previously published values of the parent table A288518 — values computed independently by Andrew Howroyd. A method that reproduces 276 known answers exactly is unlikely to be wrong on the 277th.

How the two results check each other

A236753 and A288032 count the same objects with one difference: A236753 counts each path once per direction of travel, A288032 counts it once. Every path with two or more points therefore contributes exactly twice to the directed count and once to the undirected one. The single exceptions are the degenerate one-point paths, of which an n × n grid has exactly n²: they have no direction to reverse, so they are counted once in both.

That gives a hard identity between the two sequences:

A236753(n)  =  2 × A288032(n)  +  n²

It holds for every one of the thirteen known terms. At n = 13 it reads 2 × 389,951,935,424,725,220,050,793,816,994,548,156,972 + 169 = 779,903,870,849,450,440,101,587,633,989,096,314,113 — exact, to all 39 digits.

Two sequences created three years apart by different contributors, extended on the same day, agreeing exactly at a scale where a single misplaced path would break the equality. That is the check that makes the pair worth trusting.

Reference

All three sequences and their credits are on the OEIS, which is the authoritative record:

• oeis.org/A236753 — a(13) from Lara Solomon, Jul 30 2026
• oeis.org/A288032 — a(13) from Lara Solomon, Jul 30 2026
• oeis.org/A288518 — b-file, terms 1..351, contributed by Lara Solomon
• Every OEIS entry crediting Lara Solomon

Note for searchers: an OEIS author search for author:solomon will not find these. The credits sit in the extensions and link fields rather than the author field, so a full-text search for "Lara Solomon" is the one that works.