A146304 - OEIS

%I #34 Mar 30 2020 08:43:11

%S 1,4,10,64,660,7744,111888,1960000,40829184,989479936,27559645440,

%T 870414361600,30942459270912,1225022400102400,53716785891102720,

%U 2589137004664520704,136573353235553058816,7838079929528363843584,487668908919708442951680,32741107405951528945844224

%N 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.

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

%H Andrew Howroyd, <a href="/A146304/b146304.txt">Table of n, a(n) for n = 1..200</a>

%H Andrew Howroyd, <a href="/A146304/a146304.txt">Algorithm and explanation of PARI code</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BishopGraph.html">Bishop Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalIndependentVertexSet.html">Maximal Independent Vertex Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalVertexCover.html">Minimal Vertex Cover</a>

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

%F a(n) = A290594(n) * A290613(n) for n > 1. - _Andrew Howroyd_, Aug 09 2017

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

%t 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]];

%t Q[sig_List, x_] := M[sig, Length[sig], 0, 0, x];

%t 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]]}]

%t a[n_] := Q[Bishop[n, 0], 1]*Q[Bishop[n, 1], 1];

%t Table[a[n], {n, 1, 20}] (* _Jean-François Alcover_, Jun 15 2017, translated from _Andrew Howroyd_'s PARI code *)

%o (PARI)

%o \\ Needs memoization - see note on algorithm for a faster version.

%o 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))}

%o Q(sig,x)=M(sig,length(sig),0,0,x);

%o Bishop(n,white)=vector(n-if(white,n%2,1-n%2),i,n-i+if(white,1-i%2,i%2));

%o a(n)=Q(Bishop(n,0),1)*Q(Bishop(n,1),1); \\ _Andrew Howroyd_, Jun 05 2017

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

%K nonn

%O 1,2

%A _Paolo Bonzini_, Oct 29 2008

%E a(10)-a(11) from _Andrew Howroyd_, May 21 2017

%E Terms a(12) and beyond from _Andrew Howroyd_, Jun 05 2017