BBC Russian

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

(list; graph; refs; listen; history; text; internal format)

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

LINKS

Table of n, a(n) for n=2..15.

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):

.__.__.__.__. .__.__.__.__. .__.__.__.__. .__.__.__.__.

.__.__ |__.__.__. | | |__.__. | |__.__.__. | | |__.__. |

__.__| <=> | .__.__| | | .__.__| | | .__.__| | | .__.__| |

|__.__. | |__.__.__| | |__.__.__| | |__.__. | | |__.__. |