A000532 -id:A000532 - cp's OEIS frontend

A068381 Number of partitions of n X n checkerboard by two edgewise-connected sets which produce the maximum n^2-2n+2 frontier edges between the two sets.

12, 32, 96, 648, 7736, 228424, 11974112, 1599762776, 382467306272, 234367651907856, 258981528765867728, 733498025032488425464, 3770347483688546402804760, 49588653272896250824990166768

Offset: 2

R. H. Hardin, Mar 04 2002

nonn

Not divided by 4 because that property may not continue.

Each partition is counted twice in this sequence. The sequence can be computed by counting Hamiltonian paths on a n-1 x n-1 grid that start at any vertex on the grid boundary and terminate at another boundary vertex. Counts for whether the path starts or terminates on a corner or non-corner need to be computed separately as there are different multiplication factors. - Andrew Howroyd, Apr 13 2016

			Illustration of a(2)=6*2:
    __.__     __.__     __.__    __.__     __.__     __.__
   |__|  |   |  |__|   |   __|  |__   |   |__.__|   |  |  |
   |__.__|   |__.__|   |__|__|  |__|__|   |__.__|   |__|__|
Illustration of relation of a Hamiltonian path in a 3 x 3 grid to solutions of a(4):
                 .__.__.__.__.   .__.__.__.__.   .__.__.__.__.   .__.__.__.__.
   .__.__        |__.__.__.  |   |  |__.__.  |   |__.__.__.  |   |  |__.__.  |
    __.__|  <=>  |  .__.__|  |   |  .__.__|  |   |  .__.__|  |   |  .__.__|  |
   |__.__.       |  |__.__.__|   |  |__.__.__|   |  |__.__.  |   |  |__.__.  |
                 |__.__.__.__|   |__.__.__.__|   |__.__.__|__|   |__.__.__|__|

Cf. A068392, A068393.

Cf. A001184, A000532, A121789.

a(7)-a(15) from Andrew Howroyd, Apr 13 2016

A329633 Triangle read by rows: T(n,k) is the number of self-avoiding paths of length n-1+2*k from NW to SW corners in the n X n grid graph (0 <= k <= A000217(n-1), n >= 1).

Original entry on oeis.org

1, 1, 1, 1, 3, 5, 2, 1, 6, 16, 39, 61, 47, 8, 1, 10, 40, 125, 400, 1048, 1905, 2372, 1839, 764, 86, 1, 15, 85, 335, 1237, 4638, 15860, 44365, 99815, 181995, 262414, 285086, 218011, 104879, 26344, 1770

Offset: 1

Seiichi Manyama, Mar 30 2020

			T(3,0) = 1;
   S
   |
   *
   |
   E
T(3,1) = 3;
   S--*      S--*      S
      |         |      |
   *--*         *      *--*
   |            |         |
   E         E--*      E--*
T(3,2) = 5;
   S--*--*   S--*--*   S--*--*   S--*      S
         |         |         |      |      |
   *--*--*      *--*         *      *--*   *--*--*
   |            |            |         |         |
   E         E--*      E--*--*   E--*--*   E--*--*
T(3,3) = 2;
   S--*--*   S  *--*
         |   |  |  |
   *--*  *   *--*  *
   |  |  |         |
   E  *--*   E--*--*
Triangle starts:
==========================================================
n\k| 0   1    2    3     4     5      6 ...    10 ...  15
---|------------------------------------------------------
1  | 1;
2  | 1,  1;
3  | 1,  3,   5,   2;
4  | 1,  6,  16,  39,   61,   47,     8;
5  | 1, 10,  40, 125,  400, 1048,  1905, ... , 86;
6  | 1, 15,  85, 335, 1237, 4638, 15860, ......... , 1770;

Seiichi Manyama, Rows n = 1..9, flattened

Row sums give A271507.
T(n,(n-1)*n/2) gives A000532(n).
Cf. A000217, A333520.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A329633(n):
    if n == 1: return [1]
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, n
    paths = GraphSet.paths(start, goal)
    return [paths.len(n - 1 + 2 * k).len() for k in range(n * (n - 1) // 2 + 1)]
print([i for n in range(1, 7) for i in A329633(n)])

T(n,0) = 1.

T(n,1) = A000217(n-1).

A333903 Number of directed Hamiltonian paths in a 2*n X n grid starting at the upper left corner and finishing in the lower left corner.

Original entry on oeis.org

1, 1, 16, 264, 117852, 43399371, 443064195958, 3575671586791915, 831655228913958996424, 147303585340262824414389642, 774577888161337889995061257722609, 3015734636186832309974653370241824509796, 356606519352227259565296610082412177642016167446

Offset: 1

Seiichi Manyama, Apr 09 2020

nonn

			a(1) = 1;
   S
   |
   *
   |
   E
a(2) = 1;
   S--*
      |
   *--*
   |
   *--*
      |
   E--*
a(3) = 16;
   S--*--*   S--*--*   S--*--*   S--*--*
         |         |         |         |
   *--*--*   *--*--*   *--*--*   *--*--*
   |         |         |         |
   *--*--*   *--*--*   *  *--*   *  *--*
         |         |   |  |  |   |  |  |
   *--*--*   *--*  *   *--*  *   *  *  *
   |         |  |  |         |   |  |  |
   *--*--*   *  *  *   *--*  *   *--*  *
         |   |  |  |   |  |  |         |
   E--*--*   E  *--*   E  *--*   E--*--*
   S--*--*   S--*--*   S--*--*   S--*--*
         |         |         |         |
   *--*  *   *--*  *   *--*  *   *--*  *
   |  |  |   |  |  |   |  |  |   |  |  |
   *  *--*   *  *--*   *  *  *   *  *  *
   |         |         |  |  |   |  |  |
   *--*--*   *  *--*   *  *--*   *  *  *
         |   |  |  |   |         |  |  |
   *--*  *   *--*  *   *--*--*   *  *  *
   |  |  |         |         |   |  |  |
   E  *--*   E--*--*   E--*--*   E  *--*
   S  *--*   S  *--*   S  *--*   S  *--*
   |  |  |   |  |  |   |  |  |   |  |  |
   *--*  *   *--*  *   *--*  *   *--*  *
         |         |         |         |
   *--*--*   *--*--*   *--*  *   *--*  *
   |         |         |  |  |   |  |  |
   *--*--*   *  *--*   *  *--*   *  *  *
         |   |  |  |   |         |  |  |
   *--*  *   *--*  *   *--*--*   *  *  *
   |  |  |         |         |   |  |  |
   E  *--*   E--*--*   E--*--*   E  *--*
   S  *--*   S  *--*   S  *--*   S  *--*
   |  |  |   |  |  |   |  |  |   |  |  |
   *  *  *   *  *  *   *  *  *   *  *  *
   |  |  |   |  |  |   |  |  |   |  |  |
   *--*  *   *--*  *   *  *  *   *  *  *
         |         |   |  |  |   |  |  |
   *--*--*   *--*  *   *--*  *   *  *  *
   |         |  |  |         |   |  |  |
   *--*--*   *  *  *   *--*  *   *--*  *
         |   |  |  |   |  |  |         |
   E--*--*   E  *--*   E  *--*   E--*--*

Ed Wynn, Table of n, a(n) for n = 1..18

Cf. A000532, A271592, A333604, A333606, A333863.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333903(n):
    universe = tl.grid(n - 1, 2 * n - 1)
    GraphSet.set_universe(universe)
    start, goal = 1, 2 * n
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
print([A333903(n) for n in range(1, 8)])

a(n) = A271592(2*n,n).

a(9), a(11), a(13) from Seiichi Manyama

a(8), a(10), a(12), a(14)-a(18) from Ed Wynn, Jun 28 2023

A350148 Number of distinct (left- or right-handed, but not both) two-dimensional, Hilbert-style space-filling curve motifs on the 2n+1 X 2n+1 square subdivision, that, when recursively iterated using strict edge-replacement, create always self-avoiding paths formed of sub-square edges in the lattice.

Original entry on oeis.org

1, 0, 1, 7, 10101, 20305328

Offset: 0

Douglas M. McKenna, Dec 16 2021

The paper proves that all motifs for a given n>=0 fall into F(n-1) zipping modes, where F(n) is the n-th Fibonacci number. Each mode represents a fixed state of all edges along the boundary of the motif that allows it to zip with itself. For n=4, 10101 = 600 + 9441 (F(4-1) = 2 modes); For n=5, 20305328 = 58936 + 19854452 + 391940 (F(5-1) = 3 modes).

A000532 represent Hilbert-style motifs also, but they are self-avoiding paths connecting sub-square centers. This sequence counts Hilbert-style motifs as self-avoiding paths along sub-square edges. In both cases, these self-avoiding paths in the square lattice can be considered Hamiltonian cycles on a 2D toroidal grid-graph.

			The n=0 case is the trivial/idempotent identity motif and does not converge to a space-filling curve.  There are no solutions for the 2n X 2n case.

Douglas M. McKenna, Fibbinary Zippers in a Monoid of Toroidal Hamiltonian Cycles that Generate Hilbert-style Square-filling Curves, Enumerative Combinatorics and Applications, 2:2 #S2R13 (2021).
Douglas M. McKenna, Are Maximally Unbalanced Hilbert-Style Square-Filling Curve Motifs a Drawing Medium?, Bridges Conf. Proc.; Math., Art, Music, Architecture, Culture (2023) 91-98.

Cf. A000532.

A384173 Number of Hamiltonian paths from NW to SW corners in an n X n grid reduced for symmetry, i.e., where reflection about the x-axis is not counted as distinct.

Original entry on oeis.org

1, 1, 1, 5, 43, 897, 44209, 4467927, 1043906917, 506673590576, 555799435739334, 1284472450789974196, 6625529679919810063544, 72597408139909172033687226, 1762085630816152820582838187465, 91326629994353561722347679614188407

Offset: 1

Oliver R. Bellwood, May 21 2025

When n is odd there are no symmetric Hamiltonian paths from NW to SW corners, and therefore a(n) = A000532(n)/2.

			The two paths of A000532(3) = 2 are equivalent under reflection about the x-axis:
  + - + - +
          |
  + - +   +
  |   |   |
  +   + - +
  +   + - +
  |   |   |
  + - +   +
          |
  + - + - +

J. L. Jacobsen, Exact enumeration of Hamiltonian circuits, walks and chains in two and three dimensions, J. Phys. A: Math. Theor. 40 (2007) 14667-14678.
J.-M. Mayer, C. Guez and J. Dayantis, Exact computer enumeration of the number of Hamiltonian paths in small square plane lattices, Physical Review B, Vol. 42 Number 1, 1990.

Oliver R. Bellwood, Heitor P. Casagrande, and William J. Munro, Fractal Path Strategies for Efficient 2D DMRG Simulations, arXiv:2507.11820 [cond-mat.str-el], 2025. See p. 4.

Cf. A265914, A209077.

a(n) = A000532(n)/2 for odd n.

A363577 Number of inequivalent Hamiltonian paths starting in the lower left corner of an n X n grid graph (paths differing only by rotations and reflections are regarded as equivalent).

Original entry on oeis.org

1, 1, 3, 23, 347, 10199, 683227, 85612967, 25777385143, 14396323278040, 19799561204761862, 50351228336401026361, 319210377672595552740369, 3736517399241599771428011100, 109790442395888863208285555153329, 5952238893391106787883489313797219949

Offset: 1

Lars Blomberg, Jun 10 2023

Equivalently, number of inequivalent Hamiltonian paths starting in a corner of an n X n grid graph (paths differing only by rotations and reflections are regarded as equivalent). - Martin Ehrenstein, Jul 08 2023

			There are 3 paths for n=3:
  +--+--+    +--+--+    +--+  +
  |     |    |     |    |  |  |
  +  +  +    +  +--+    +  +  +
  |  |  |    |  |       |  |  |
  +  +--+    +  +--+    +  +--+
A fourth path:
  +--+--+
        |
  +--+  +
  |  |  |
  +  +--+
is the same as the second one in the row above after a 90-degree rotation.
All paths starting E are the same as the corresponding ones starting N after reflection in the forward diagonal.

Oliver R. Bellwood, Heitor P. Casagrande, and William J. Munro, Fractal Path Strategies for Efficient 2D DMRG Simulations, arXiv:2507.11820 [cond-mat.str-el], 2025. See p. 4.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Hamiltonian Path
Index entries for sequences related to graphs, Hamiltonian

Cf. A000532, A001184, A003763, A007764, A120443, A121785, A121789, A145157, A271507, A384173.

a(1) added by N. J. A. Sloane, Jun 10 2023
a(8)-a(9) from Martin Ehrenstein, Jul 08 2023
a(10)-a(16) from Oliver R. Bellwood, Jun 06 2025

cp's OEIS Frontend

A068381 Number of partitions of n X n checkerboard by two edgewise-connected sets which produce the maximum n^2-2n+2 frontier edges between the two sets.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A329633 Triangle read by rows: T(n,k) is the number of self-avoiding paths of length n-1+2*k from NW to SW corners in the n X n grid graph (0 <= k <= A000217(n-1), n >= 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

A333903 Number of directed Hamiltonian paths in a 2*n X n grid starting at the upper left corner and finishing in the lower left corner.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A384173 Number of Hamiltonian paths from NW to SW corners in an n X n grid reduced for symmetry, i.e., where reflection about the x-axis is not counted as distinct.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A363577 Number of inequivalent Hamiltonian paths starting in the lower left corner of an n X n grid graph (paths differing only by rotations and reflections are regarded as equivalent).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions