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

Author

R. H. Hardin, Mar 04 2002

Keywords

• nonn

Comments

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

Examples

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

Crossrefs

Cf. A068392, A068393.

Cf. A001184, A000532, A121789.

Extensions

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