[go: up one dir, main page]

login
Search: a290613 -id:a290613
     Sort: relevance | references | number | modified | created      Format: long | short | data
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.
+10
8
1, 4, 10, 64, 660, 7744, 111888, 1960000, 40829184, 989479936, 27559645440, 870414361600, 30942459270912, 1225022400102400, 53716785891102720, 2589137004664520704, 136573353235553058816, 7838079929528363843584, 487668908919708442951680, 32741107405951528945844224
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
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(2) = 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
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
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<n).
+10
5
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,1
COMMENTS
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.
LINKS
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, White Bishop Graph
EXAMPLE
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;
...
CROSSREFS
Row sums are A290613.
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Jun 06 2017
STATUS
approved
Number of maximal independent vertex sets (and minimal vertex covers) in the n X n black bishop graph.
+10
4
1, 2, 5, 8, 30, 88, 378, 1400, 7128, 31456, 182640, 932960, 6048912, 35000320, 249904656, 1609079552, 12518446848, 88532931328, 744008722944, 5721984568832, 51576606895104, 427904524628992, 4112973567496704, 36567439575256064, 372971541998834688
OFFSET
1,2
COMMENTS
See A146304 for algorithm and PARI code to produce this sequence. - Andrew Howroyd, Aug 07 2017
LINKS
Eric Weisstein's World of Mathematics, Black Bishop Graph
Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set
Eric Weisstein's World of Mathematics, Minimal Vertex Cover
CROSSREFS
Row sums of A288183.
KEYWORD
nonn
AUTHOR
Eric W. Weisstein, Aug 07 2017
EXTENSIONS
Terms a(12) and beyond from Andrew Howroyd, Aug 07 2017
STATUS
approved

Search completed in 0.008 seconds