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

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

Offset: 1

Author

R. H. Hardin, Mar 02 2002

Keywords

• nonn

Comments

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

Examples

			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
		

Links

• 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.

Crossrefs

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

Formula

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

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

Extensions

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