|
|
A146304
|
|
Number of distinct ways to place bishops (up to 2n-2) on an n X n chessboard so that no bishop is attacking another and that it is not possible to add another bishop.
|
|
8
|
|
|
1, 4, 10, 64, 660, 7744, 111888, 1960000, 40829184, 989479936, 27559645440, 870414361600, 30942459270912, 1225022400102400, 53716785891102720, 2589137004664520704, 136573353235553058816, 7838079929528363843584, 487668908919708442951680, 32741107405951528945844224
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Number of maximal independent vertex sets (and minimal vertex covers) in the n X n bishop graph. - Eric W. Weisstein, Jun 04 2017
|
|
LINKS
|
|
|
FORMULA
|
Conjectured to be a(n) = O(n^(n-1)).
|
|
EXAMPLE
|
For n=2, the a(2) = 4 solutions are to place two bishops on the same row (two solutions) or column (two solutions).
|
|
MATHEMATICA
|
M[sig_List, n_, k_, d_, x_] := M[sig, n, k, d, x] = If[n == 0, Boole[k == 0], If[k > 0, k*x*M[sig, n - 1, k - 1, d, x], 0] + If[k < n && sig[[n]] > d, (sig[[n]] - d)*x*M[sig, n - 1, k, d + 1, x], 0] + If[k + sig[[n]] - d < n, M[sig, n - 1, k + sig[[n]] - d, sig[[n]], x], 0]];
Q[sig_List, x_] := M[sig, Length[sig], 0, 0, x];
Bishop[n_, white_] := Table[n - i + If[white == 1, 1 - Mod[i, 2], Mod[i, 2]], {i, 1, n - If[white == 1, Mod[n, 2], 1 - Mod[n, 2]]}]
a[n_] := Q[Bishop[n, 0], 1]*Q[Bishop[n, 1], 1];
|
|
PROG
|
(PARI)
\\ Needs memoization - see note on algorithm for a faster version.
M(sig, n, k, d, x)={if(n==0, k==0, if(k>0, k*x*M(sig, n-1, k-1, d, x), 0) + if(k<n&&sig[n]>d, (sig[n]-d)*x*M(sig, n-1, k, d+1, x), 0) + if(k+sig[n]-d<n, M(sig, n-1, k+sig[n]-d, sig[n], x), 0))}
Q(sig, x)=M(sig, length(sig), 0, 0, x);
Bishop(n, white)=vector(n-if(white, n%2, 1-n%2), i, n-i+if(white, 1-i%2, i%2));
a(n)=Q(Bishop(n, 0), 1)*Q(Bishop(n, 1), 1); \\ Andrew Howroyd, Jun 05 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|