A290594 -id:A290594 - 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.

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

Offset: 1

Paolo Bonzini, Oct 29 2008

nonn

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

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

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

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

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

\\ 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

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

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

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

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

A288183 Triangle read by rows: T(n,k) = number of arrangements of k non-attacking bishops on the black squares of an n X n board with every square controlled by at least one bishop.

Original entry on oeis.org

2, 1, 4, 0, 4, 4, 0, 0, 22, 8, 0, 0, 16, 64, 8, 0, 0, 6, 128, 228, 16, 0, 0, 0, 72, 784, 528, 16, 0, 0, 0, 0, 1056, 4352, 1688, 32, 0, 0, 0, 0, 432, 9072, 18336, 3584, 32, 0, 0, 0, 0, 120, 7776, 76488, 87168, 11024, 64, 0, 0, 0, 0, 0, 2880, 109152, 484416, 313856, 22592, 64

Offset: 2

Andrew Howroyd, Jun 06 2017

See A146304 for algorithm and PARI code to produce this sequence.
Equivalently, the coefficients of the maximal independent set polynomials on the n X n black bishop graph.
The product of the first nonzero term in each row of this sequence and that of A288182 give A122749.

			Triangle begins:
  2;
  1, 4;
  0, 4,  4;
  0, 0, 22,   8;
  0, 0, 16,  64,    8;
  0, 0,  6, 128,  228,   16;
  0, 0,  0,  72,  784,  528,    16;
  0, 0,  0,   0, 1056, 4352,  1688,    32;
  0, 0,  0,   0,  432, 9072, 18336,  3584,    32;
  0, 0,  0,   0,  120, 7776, 76488, 87168, 11024,  64;
  ...
The first term is T(2,1) = 2.

Andrew Howroyd, Table of n, a(n) for n = 2..1276
Eric Weisstein's World of Mathematics, Black Bishop Graph
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set

Row sums are A290594.

Cf. A288182, A122749, A274105, A146304.

A290613 Number of maximal independent vertex sets (and minimal vertex covers) in the n X n white bishop graph.

Original entry on oeis.org

2, 2, 8, 22, 88, 296, 1400, 5728, 31456, 150896, 932960, 5115376, 35000320, 214949120, 1609079552, 10909768192, 88532931328, 655461278720, 5721984568832, 45854239383040, 427904524628992, 3685075352873984, 36567439575256064, 336404621367433216

Offset: 2

Eric W. Weisstein, Aug 07 2017

nonn

See A146304 for algorithm and PARI code to produce this sequence. - Andrew Howroyd, Aug 09 2017

Andrew Howroyd, Table of n, a(n) for n = 2..100
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Vertex Cover
Eric Weisstein's World of Mathematics, White Bishop Graph

Row sums of A288182.

Cf. A146304, A290594.

Terms a(12) and beyond from Andrew Howroyd, Aug 09 2017

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A288183 Triangle read by rows: T(n,k) = number of arrangements of k non-attacking bishops on the black squares of an n X n board with every square controlled by at least one bishop.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A290613 Number of maximal independent vertex sets (and minimal vertex covers) in the n X n white bishop graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions