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
For n=2, the a(2) = 4 solutions are to place two bishops on the same row (two solutions) or column (two solutions).
-
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
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
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.
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
A274106
Triangle read by rows: T(n,k) = total number of configurations of k nonattacking bishops on the white squares of an n X n chessboard (0 <= k <= n-1+[n=0]).
Original entry on oeis.org
1, 1, 1, 2, 1, 4, 2, 1, 8, 14, 4, 1, 12, 38, 32, 4, 1, 18, 98, 184, 100, 8, 1, 24, 188, 576, 652, 208, 8, 1, 32, 356, 1704, 3532, 2816, 632, 16, 1, 40, 580, 3840, 12052, 16944, 9080, 1280, 16, 1, 50, 940, 8480, 38932, 89256, 93800, 37600, 3856, 32, 1, 60, 1390, 16000, 98292, 322848, 540080, 412800, 116656, 7744, 32
Offset: 0
Triangle begins:
1;
1;
1, 2;
1, 4, 2;
1, 8, 14, 4;
1, 12, 38, 32, 4;
1, 18, 98, 184, 100, 8;
1, 24, 188, 576, 652, 208, 8;
1, 32, 356, 1704, 3532, 2816, 632, 16;
1, 40, 580, 3840, 12052, 16944, 9080, 1280, 16;
1, 50, 940, 8480, 38932, 89256, 93800, 37600, 3856, 32;
1, 60, 1390, 16000, 98292, 322848, 540080, 412800, 116656, 7744, 32;
...
From _Eder G. Santos_, Dec 16 2024: (Start)
For example, for n = 3, k = 2, the T(3,2) = 2 nonattacking configurations are:
+---+---+---+ +---+---+---+
| | B | | | | | |
+---+---+---+ +---+---+---+
| | | | , | B | | B |
+---+---+---+ +---+---+---+
| | B | | | | | |
+---+---+---+ +---+---+---+
(End)
- Irving Kaplansky and John Riordan, The problem of the rooks and its applications, Duke Mathematical Journal 13.2 (1946): 259-268. See Section 9.
- Irving Kaplansky and John Riordan, The problem of the rooks and its applications, in Combinatorics, Duke Mathematical Journal, 13.2 (1946): 259-268. See Section 9. [Annotated scanned copy]
- J. Perott, Sur le problème des fous, Bulletin de la S. M. F., tome 11 (1883), pp. 173-186.
- Eder G. Santos, Counting non-attacking chess pieces placements: Bishops and Anassas. arXiv:2411.16492 [math.CO], 2024. (considered as black board).
- Eric Weisstein's World of Mathematics, White Bishop Graph.
-
with(combinat): with(gfun):
T := n -> add(stirling2(n+1,n+1-k)*x^k, k=0..n):
# bishops on white squares
bish := proc(n) local m,k,i,j,t1,t2; global T;
if n=0 then return [1] fi;
if (n mod 2) = 0 then m:=n/2;
t1:=add(binomial(m,k)*T(2*m-1-k)*x^k, k=0..m);
else
m:=(n-1)/2;
t1:=add(binomial(m,k)*T(2*m-k)*x^k, k=0..m+1);
fi;
seriestolist(series(t1,x,2*n+1));
end:
for n from 0 to 12 do lprint(bish(n)); od:
-
T[n_] := Sum[StirlingS2[n+1, n+1-k]*x^k, {k, 0, n}];
bish[n_] := Module[{m, t1, t2}, If[Mod[n, 2] == 0,
m = n/2; t1 = Sum[Binomial[m, k]*T[2*m-1-k]*x^k, {k, 0, m}],
m = (n-1)/2; t1 = Sum[Binomial[m, k]*T[2*m - k]*x^k, {k, 0, m+1}]];
CoefficientList[t1 + O[x]^(2*n+1), x]];
Table[bish[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Jul 25 2022, after Maple code *)
-
def stirling2_negativek(n, k):
if k < 0: return 0
else: return stirling_number2(n, k)
print([sum([binomial(floor(n/2), j)*stirling2_negativek(n-j, n-k) for j in [0..k]]) for n in [0..10] for k in [0..n-1+kronecker_delta(n,0)]]) # Eder G. Santos, Dec 01 2024
Showing 1-4 of 4 results.
Comments