login
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.
3
12, 32, 96, 648, 7736, 228424, 11974112, 1599762776, 382467306272, 234367651907856, 258981528765867728, 733498025032488425464, 3770347483688546402804760, 49588653272896250824990166768
OFFSET
2,1
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
EXAMPLE
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
KEYWORD
nonn
AUTHOR
R. H. Hardin, Mar 04 2002
EXTENSIONS
a(7)-a(15) from Andrew Howroyd, Apr 13 2016
STATUS
approved