login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A146304 Number of distinct ways to place bishops (up to 2n-2) on an n*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

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)).

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

EXAMPLE

For n=2, the a(n) = 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

CROSSREFS

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

Sequence in context: A298162 A203226 A300642 * A189893 A197939 A207160

Adjacent sequences:  A146301 A146302 A146303 * A146305 A146306 A146307

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 12 04:21 EST 2019. Contains 329051 sequences. (Running on oeis4.)