cp's OEIS Frontend

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.

%I A146304 #35 Feb 16 2025 08:33:09
%S A146304 1,4,10,64,660,7744,111888,1960000,40829184,989479936,27559645440,
%T A146304 870414361600,30942459270912,1225022400102400,53716785891102720,
%U A146304 2589137004664520704,136573353235553058816,7838079929528363843584,487668908919708442951680,32741107405951528945844224
%N 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.
%C A146304 Number of maximal independent vertex sets (and minimal vertex covers) in the n X n bishop graph. - _Eric W. Weisstein_, Jun 04 2017
%H A146304 Andrew Howroyd, <a href="/A146304/b146304.txt">Table of n, a(n) for n = 1..200</a>
%H A146304 Andrew Howroyd, <a href="/A146304/a146304.txt">Algorithm and explanation of PARI code</a>
%H A146304 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/BishopGraph.html">Bishop Graph</a>
%H A146304 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MaximalIndependentVertexSet.html">Maximal Independent Vertex Set</a>
%H A146304 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MinimalVertexCover.html">Minimal Vertex Cover</a>
%F A146304 Conjectured to be a(n) = O(n^(n-1)).
%F A146304 a(n) = A290594(n) * A290613(n) for n > 1. - _Andrew Howroyd_, Aug 09 2017
%e A146304 For n=2, the a(2) = 4 solutions are to place two bishops on the same row (two solutions) or column (two solutions).
%t A146304 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 A146304 Q[sig_List, x_] := M[sig, Length[sig], 0, 0, x];
%t A146304 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 A146304 a[n_] := Q[Bishop[n, 0], 1]*Q[Bishop[n, 1], 1];
%t A146304 Table[a[n], {n, 1, 20}] (* _Jean-François Alcover_, Jun 15 2017, translated from _Andrew Howroyd_'s PARI code *)
%o A146304 (PARI)
%o A146304 \\ Needs memoization - see note on algorithm for a faster version.
%o A146304 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 A146304 Q(sig,x)=M(sig,length(sig),0,0,x);
%o A146304 Bishop(n,white)=vector(n-if(white,n%2,1-n%2),i,n-i+if(white,1-i%2,i%2));
%o A146304 a(n)=Q(Bishop(n,0),1)*Q(Bishop(n,1),1); \\ _Andrew Howroyd_, Jun 05 2017
%Y A146304 Cf. A146303, A122749, A201862, A288182, A288183, A290594, A290613.
%K A146304 nonn
%O A146304 1,2
%A A146304 _Paolo Bonzini_, Oct 29 2008
%E A146304 a(10)-a(11) from _Andrew Howroyd_, May 21 2017
%E A146304 Terms a(12) and beyond from _Andrew Howroyd_, Jun 05 2017