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
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
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];
Table[a[n], {n, 1, 20}] (* Jean-François Alcover, Jun 15 2017, translated from Andrew Howroyd's PARI code *)
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
KEYWORD
nonn
AUTHOR
Paolo Bonzini, Oct 29 2008
EXTENSIONS
a(10)-a(11) from Andrew Howroyd, May 21 2017
Terms a(12) and beyond from Andrew Howroyd, Jun 05 2017
STATUS
approved