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.

1, 4, 10, 64, 660, 7744, 111888, 1960000, 40829184, 989479936, 27559645440, 870414361600, 30942459270912, 1225022400102400, 53716785891102720, 2589137004664520704, 136573353235553058816, 7838079929528363843584, 487668908919708442951680, 32741107405951528945844224

Offset: 1

Author

Paolo Bonzini, Oct 29 2008

Keywords

• nonn

Comments

Number of maximal independent vertex sets (and minimal vertex covers) in the n X n bishop graph. - Eric W. Weisstein, Jun 04 2017

Examples

			For n=2, the a(2) = 4 solutions are to place two bishops on the same row (two solutions) or column (two solutions).
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..200
• Andrew Howroyd, Algorithm and explanation of PARI code
• Eric Weisstein's World of Mathematics, Bishop Graph
• Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
• Eric Weisstein's World of Mathematics, Minimal Vertex Cover

Crossrefs

Cf. A146303, A122749, A201862, A288182, A288183, A290594, A290613.

Programs

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];
Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Jun 15 2017, translated from Andrew Howroyd's PARI code *)

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(kd,(sig[n]-d)*x*M(sig,n-1,k,d+1,x),0) + if(k+sig[n]-dAndrew Howroyd, Jun 05 2017

Formula

Conjectured to be a(n) = O(n^(n-1)).

a(n) = A290594(n) * A290613(n) for n > 1. - Andrew Howroyd, Aug 09 2017

Extensions

a(10)-a(11) from Andrew Howroyd, May 21 2017

Terms a(12) and beyond from Andrew Howroyd, Jun 05 2017