A122749 -id:A122749 - cp's OEIS frontend

A005635 Number of ways of placing n non-attacking bishops on an n X n board so that every square is attacked (or occupied).

1, 1, 1, 1, 3, 8, 36, 110, 666, 3250, 23436, 125198, 1037520, 7241272, 66360960, 500827928, 5080370400, 45926666984, 508032504000, 4919789029480, 59256857923200, 656763542278304, 8532986822438400, 100525959568386848, 1405335514253932800, 18431883489984091552

Offset: 0

N. J. A. Sloane

From Vaclav Kotesovec, Apr 26 2012: (Start)
This sequence gives (according to the article by Robinson) the number of inequivalent solutions.
For the total number of all arrangements of n non-attacking bishops such that every square of the board is controlled by at least one bishop, see A122749.
For the total number of all arrangements of n bishops (in any position) such that every square of the board is controlled by at least one bishop, see A182333.
(End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 0..250
Jean-François Alcover, Mathematica program.
R. W. Robinson, Counting arrangements of bishops, pp. 198-214 of Combinatorial Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976).
R. W. Robinson, Counting arrangements of bishops, pp. 198-214 of Combinatorial Mathematics IV (Adelaide 1975), Lect. Notes Math., 560 (1976). (Annotated scanned copy)

Cf. A005631, A005632, A005633, A005634, A122749, A123071, A123072, A182333.

E:=proc(n) local k; if n mod 2 = 0 then k := n/2; if k mod 2 = 0 then RETURN( (k!*(k+2)/2)^2 ); else RETURN( ((k-1)!*(k+1)^2/2)^2 ); fi; else k := (n-1)/2; if k mod 2 = 0 then RETURN( ((k!)^2/12)*(3*k^3+16*k^2+18*k+8) ); else RETURN( ((k-1)!*(k+1)!/12)*(3*k^3+13*k^2-k-3) ); fi; fi; end; # Gives A122749
unprotect(D); D:=proc(n) option remember; if n <= 1 then 1 else D(n-1)+(n-1)*D(n-2); fi; end; # Gives A000085
C:=proc(n) local k; if n mod 2 = 0 then RETURN(0); fi; k:=(n-1)/2; if k mod 2 = 0 then RETURN( k*2^(k-1)*((k/2)!)^2 ); else RETURN( 2^k*(((k+1)/2)!)^2 ); fi; end; # Gives A122693
Q:=proc(n) local m; if n mod 8 <> 1 then RETURN(0); fi; m:=(n-1)/8; ((2*m)!)^2/(m!)^2; end; # Gives A122747
M:=proc(n) local k; if n mod 2 = 0 then k:=n/2; if k mod 2 = 0 then RETURN( k!*(k+2)/2 ); else RETURN( (k-1)!*(k+1)^2/2 ); fi; else k:=(n-1)/2; RETURN(D(k)*D(k+1)); fi; end; # Gives A122748
a:=n-> if n <= 1 then RETURN(1) else E(n)/8 + C(n)/8 + Q(n)/4 + M(n)/4; fi; # Gives A005635
# The following additional Maple programs produce A123071, A005631, A123072, A005633, A005632, A005634
S:=proc(n) local k; if n mod 2 = 0 then RETURN(0) else k:=(n-1)/2; RETURN(B(k)*B(k+1)); fi; end; # Gives A123071
psi:=n->S(n)/2; # Gives A005631
zeta:=n->Q(n)/2; # Gives A123072
mu:=n->(M(n)-S(n))/2; # Gives A005633
chi:=n->(C(n)-S(n)-Q(n))/4; # Gives A005632
eps:=n->E(n)/8-C(n)/8+S(n)/4-M(n)/4; # Gives A005634

Entry revised by N. J. A. Sloane, Sep 25 2006

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.

Original entry on oeis.org

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

A182333 Number of arrangements of n bishops such that every square of the board is controlled by at least one bishop.

Original entry on oeis.org

1, 4, 6, 25, 104, 484, 2136, 11664, 71136, 451584, 3006720, 21902400, 176774400, 1456185600, 12758860800, 117456998400, 1181072793600, 12023694950400, 130072449024000, 1451792885760000, 17487355576320000, 212389727477760000, 2729844680048640000

Offset: 1

Vaclav Kotesovec, Apr 25 2012

nonn

Number of minimum dominating sets in the n X n bishop graph. - Eric W. Weisstein, Jun 04 2017

A. M. Yaglom and I. M. Yaglom, Challenging Mathematical Problems with Elementary Solutions, vol.1, 1987, p.11 and p.83-88.

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Bishop Graph
Eric Weisstein's World of Mathematics, Dominating Set

Cf. A005635, A122749, A323500, A323501.

Table[If[n==1,1,((2*Floor[n/4])!)^2/128*(n^5+3*n^4+n^3+35*n^2+38*n+2-(n^5-n^4-7*n^3-n^2-10*n-30)*(-1)^n-4*(n^3+2*n^2+n-4)*n*Cos[Pi*n/2]-2*(n^5+n^4-11*n^3-7*n^2-2*n+2)*Sin[Pi*n/2])],{n,1,25}]

a(n)={if(n==1, 1, (n\4*2)!^2*if(n%4<2, if(n%2==0, (n+1)^2, (n^3 + 3*n^2 + 2*n - 2)/2), if(n%2==0, (n^2+n+2)^2/4, (n+1)*(n-1)*(n^3 + n^2 - 6*n + 6)/8))/4)} \\ Andrew Howroyd, Sep 09 2019

a(n) = (((2*floor(n/4))!)^2/128)*(n^5 + 3*n^4 + n^3 + 35*n^2 + 38*n + 2 - (n^5 - n^4 - 7*n^3 - n^2 - 10*n - 30)*(-1)^n -4*(n^3 + 2*n^2 + n - 4)*n*cos(Pi*n/2) - 2*(n^5 + n^4 - 11*n^3 - 7*n^2 - 2*n + 2)*sin(Pi*n/2)), for n > 1.

a(n) = A323500(n) * A323501(n) for n > 1. - Andrew Howroyd, Sep 08 2019

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

Original entry on oeis.org

2, 0, 2, 0, 4, 4, 0, 2, 16, 4, 0, 0, 16, 64, 8, 0, 0, 0, 128, 160, 8, 0, 0, 0, 72, 784, 528, 16, 0, 0, 0, 24, 864, 3672, 1152, 16, 0, 0, 0, 0, 432, 9072, 18336, 3584, 32, 0, 0, 0, 0, 0, 8304, 65664, 69472, 7424, 32, 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 white bishop graph.
The product of the first nonzero term in each row of this sequence and that of A288183 give A122749.

			Triangle starts (first term is n=2, k=1):
  2;
  0, 2;
  0, 4,  4;
  0, 2, 16,   4;
  0, 0, 16,  64,   8;
  0, 0,  0, 128, 160,    8;
  0, 0,  0,  72, 784,  528,    16;
  0, 0,  0,  24, 864, 3672,  1152,    16;
  0, 0,  0,   0, 432, 9072, 18336,  3584,   32;
  0, 0,  0,   0,   0, 8304, 65664, 69472, 7424, 32;
  ...

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

Row sums are A290613.

Cf. A288183, A122749, A274106, A146304.

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.

A002568 Number of different ways one can attack all squares on an n X n chessboard with the smallest number of non-attacking queens needed.

Original entry on oeis.org

1, 4, 1, 16, 16, 120, 8, 728, 92, 8, 2, 840, 24, 436, 10188, 128, 12, 224, 8424, 312, 72, 192, 8784, 368, 56, 224, 14500, 280, 10880, 240

Offset: 1

N. J. A. Sloane

For same problem, but with queens in general position (without condition "non-attacking"), see A002564. - Vaclav Kotesovec, Sep 07 2012

			a(5) = 16 because it is impossible to attack all squares with 2 queens but with 3 queens you can do it in 16 different ways (with mirroring and rotation).

W. Ahrens, Mathematische Unterhaltungen und Spiele, second edition (1910), Vol. 1, p. 301.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Mia Müßig, Julia code to compute the sequence
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 49.
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1923, 64 pages. See p. 49. [Incomplete annotated scan of title page and pages 18-51]

See A002567 for the number of non-isomorphic solutions.

Cf. A002564, A122749, A103315.

a(9)-a(12) from Johan Särnbratt, Mar 28 2008
Name of the sequence corrected by Vaclav Kotesovec, Sep 07 2012
a(13)-a(15) from Andrew Howroyd, Dec 07 2021
a(16)-a(30) from Mia Muessig, Oct 04 2024

cp's OEIS Frontend

A005635 Number of ways of placing n non-attacking bishops on an n X n board so that every square is attacked (or occupied).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Extensions

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

A182333 Number of arrangements of n bishops such that every square of the board is controlled by at least one bishop.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A002568 Number of different ways one can attack all squares on an n X n chessboard with the smallest number of non-attacking queens needed.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions