A068392 -id:A068392 - cp's OEIS frontend

A113900 Number of partitions of 2n X 2n checkerboard into two congruent edgewise-connected sets, counting partitions equal under rotation or reflection only once.

1, 6, 255, 92263, 281035054, 7490694495750, 1789509008288411290

Offset: 1

Joseph Sardinha (jsardi3(AT)juno.com), Jan 29 2006

			All partitions are radially symmetric, hence can be identified by half the cut. The solution for 4 X 4 follows, with coordinates of starting point and direction of each subsequent incremental cut (North is positive Y).
(1,0)NNNES (1,0)NNE (1,0)NEN (1,0)NEENW (2,0)NN (2,0)NENW total = 6

Howard Eves, A Survey of Geometry, 1963, p265.

Giovanni Resta, Illustrations for a(2) = 6 and a(3) = 255.

Cf. A064941, A068392, A257952.

a(5) corrected by Giovanni Resta, May 14 2015

New value of a(5) confirmed by and additional values a(6) and a(7) from Andrew Howroyd, Apr 13 2016

A068416 Number of partitionings of n X n checkerboard into two edgewise-connected sets.

Original entry on oeis.org

0, 6, 53, 627, 16213, 1123743, 221984391, 127561384993, 215767063451331, 1082828220389781579, 16209089366362071416785, 726438398002211876667379681, 97741115155002465272674416929195, 39565596445488219947994403962984729307

Offset: 1

R. H. Hardin, Mar 02 2002

nonn

One of the partitions may completely surround the other. (Cf. A271802) - Andrew Howroyd, Apr 14 2016

Number of minimal edge cuts in the n X n grid graph. - Andrew Howroyd, Dec 11 2024

			Illustration of a(2)=6:
   11   12   12   12   11   11
   22   12   22   11   12   21
Illustration of a few solutions of a(3):
   111   112   122   111   111
   121   111   112   212   111
   111   111   222   222   222

Anthony J. Guttmann and Iwan Jensen, Table of n, a(n) for n = 1..26
Benjamin Fifield, Kosuke Imai, Jun Kawahara, and Christopher T. Kenny, The Essential Role of Empirical Validation in Legislative Redistricting Simulation, Tech. rep., Department of Government and Department of Statistics, Harvard University (2019).
Anthony J. Guttmann and Iwan Jensen, The gerrymander sequence, or A348456, arXiv:2211.14482 [math.CO], 2022.
Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Minimal Edge Cut.

Cf. A068392, A166755, A271802, A068381, A068417, A113900, A348456, A358289.

a(n) = A271802(n) + A140517(n-2). - Andrew Howroyd, Apr 14 2016

a(n) = A166755(n)/2. - Andrew Howroyd, Dec 11 2024

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

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.

Original entry on oeis.org

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

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.

Original entry on oeis.org

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

cp's OEIS Frontend

A113900 Number of partitions of 2n X 2n checkerboard into two congruent edgewise-connected sets, counting partitions equal under rotation or reflection only once.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Extensions

A068416 Number of partitionings of n X n checkerboard into two edgewise-connected sets.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

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

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