A265914 -id:A265914 - cp's OEIS frontend

A068393 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. Partitions equal under rotation or reflection are counted only once.

2, 3, 7, 44, 494, 748827, 99987552, 23904291912, 23904291912, 14647978829979, 16186345621426754, 45843626565163628751, 235646717730827228414584, 3099290829556018890177304005

Offset: 2

R. H. Hardin, Mar 03 2002

nonn

For even n > 2 the only symmetry possible is rotation by 180 degrees. For odd n > 1 the only symmetries are reflections either horizontally or vertically. - Andrew Howroyd, Apr 15 2016

			From _Andrew Howroyd_, Apr 15 2016: (Start)
Case n=4: There are 2 nonisomorphic symmetrical solutions (see illustration below). a(4)=(A068381(4)/8 + 2)/2 = 7.
    __.__.__.__.    __.__.__.__.
   |   __    __|   |   __   |  |
   |  |  |  |  |   |  |  |  |  |
   |__|  |__|  |   |  |  |__|  |
   |__.__.__.__|   |__|__.__.__|
Case n=5: There are 7 nonisomorphic symmetrical solutions (see illustration below). a(5)=(A068381(5)/8 + 7)/2 = 44.
    __.__.__.__.__.   __.__.__.__.__.   __.__.__.__.__.   __.__.__.__.__.
   |   __|  |__   |  |   __|  |__   |  |  |__    __|  |  |  |   __   |  |
   |  |__    __|  |  |  |   __   |  |  |   __|  |__   |  |  |  |  |  |  |
   |   __|  |__   |  |  |  |  |  |  |  |  |   __   |  |  |  |  |  |  |  |
   |  |__.__.__|  |  |  |__|  |__|  |  |  |__|  |__|  |  |  |__|  |__|  |
   |__.__.__.__.__|  |__.__.__.__.__|  |__.__.__.__.__|  |__.__.__.__.__|
    __.__.__.__.__.   __.__.__.__.__.   __.__.__.__.__.
   |__.__    __.__|  |__    __    __|  |   __    __   |
   |   __|  |__   |  |  |  |  |  |  |  |__|  |  |  |__|
   |  |   __   |  |  |  |  |  |  |  |  |   __|  |__   |
   |  |__|  |__|  |  |  |__|  |__|  |  |  |__.__.__|  |
   |__.__.__.__.__|  |__.__.__.__.__|  |__.__.__.__.__|
(End)

Cf. A068381, A068416, A068392, A265914.

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

A331001 Number of symmetrical self-avoiding walks with maximum length on an n X n board which start in the upper left corner and go right on the first step.

Original entry on oeis.org

1, 1, 1, 2, 8, 24, 282, 888, 46933, 238119, 36027060, 187011538, 130162111969, 1084873972934, 2200211600730504, 18559765767843341, 174907641314142138422, 2355130982684196593401, 65250573687646264926302133, 884112393542714503429381555, 114482128183138374886637093070429, 2465467527044697154210112460659081

Offset: 1

S. Brunner, Feb 02 2020

If you allow going down on the first step you get two times a(n) for n > 1.

All symmetrical self-avoiding walks on a square board with odd length seem to have a 180-degree rotational symmetry, and all symmetrical self-avoiding walks on a square board with even length seem to have either vertically or horizontally reflection symmetry.

			The solutions for n=3 and n=4:
  n=3:  |    n=4:
  1     |    1          2
  >>v   |   >>>v   |   >v>
  v<<   |   v<<<   |   v<^<
  >>    |   >>>v   |   v>v^
        |    <<<   |   >^>^

S. Brunner, Python program.
Peter Kagey, Example of a(5) = 8.

Cf. A145157, A265914.

a(11)-a(20) from Andrew Howroyd, Feb 20 2020
a(21) from Andrew Howroyd, Oct 16 2024
a(22) from Oliver R. Bellwood, Jul 18 2025

A328931 Number of Hamiltonian paths in an n X n square, starting from an edge, finishing anywhere, all symmetries excluded.

Original entry on oeis.org

1, 1, 4, 51, 660, 30745, 1621471, 312637285, 72599875346, 60968508324409, 64128000370443037, 240651566540823214362, 1162174738476331286327484, 19776621796151182708398884540, 441809773825445785471324877668710

Offset: 1

David Lawrence, Oct 31 2019

Given an n X n grid, start from any outside edge, enter the grid, and visit every square. 1 X 1 is a trivial example. 2 X 2 can only be traversed clockwise or counterclockwise (therefore considered the same solution). For 3 X 3 with the cells labeled ABC/DEF/GHI, the four solutions are ADEBCFIHG, ADGHIFEBC, ADGHIFCE and ADGHEBCFI. All others are rotations or reflections.

Discovered programmatically by exhaustive recursive search.

			All distinct paths through a 1 X 1 labyrinth visiting all cells.
  +  +
  |**|
  +--+
.
All distinct paths through a 2 X 2 labyrinth visiting all cells.
  +  +--+
  |  |**|
  +  +  +
  |     |
  +--+--+
.
All distinct paths through a 3 X 3 labyrinth visiting all cells.
  +  +--+--+
  |  |     |
  +  +  +  +
  |     |  |
  +--+--+  +
  |**      |
  +--+--+--+
.
  +  +--+--+
  |  |   **|
  +  +  +--+
  |  |     |
  +  +--+  +
  |        |
  +--+--+--+
.
  +  +--+--+
  |  |     |
  +  +  +  +
  |  |**|  |
  +  +--+  +
  |        |
  +--+--+--+
.
  +  +--+--+
  |  |     |
  +  +  +  +
  |  |  |  |
  +  +  +  +
  |     |**|
  +--+--+--+

David Lawrence, All paths up to 4 X 4

Cf. A120443, A121789, A145157, A265914.

a(8)-a(15) from Andrew Howroyd, Oct 31 2019

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.

cp's OEIS Frontend

A068393 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. Partitions equal under rotation or reflection are counted only once.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A331001 Number of symmetrical self-avoiding walks with maximum length on an n X n board which start in the upper left corner and go right on the first step.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A328931 Number of Hamiltonian paths in an n X n square, starting from an edge, finishing anywhere, all symmetries excluded.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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