A274105 Triangle read by rows: T(n,k) = number of configurations of k nonattacking bishops on the black squares of an n X n chessboard (0 <= k <= n - [n>1]).

1, 1, 1, 1, 2, 1, 5, 4, 1, 8, 14, 4, 1, 13, 46, 46, 8, 1, 18, 98, 184, 100, 8, 1, 25, 206, 674, 836, 308, 16, 1, 32, 356, 1704, 3532, 2816, 632, 16, 1, 41, 612, 4196, 13756, 20476, 11896, 1912, 32, 1, 50, 940, 8480, 38932, 89256, 93800, 37600, 3856, 32, 1, 61, 1440, 16940, 106772, 361780, 629336, 506600, 154256, 11600, 64

Offset

0,5

Comments

Rows give the coefficients of the independence polynomial of the n X n black bishop graph. - Eric W. Weisstein, Jun 26 2017

Links

Table of n, a(n) for n=0..67.

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]

Eder G. Santos, Counting non-attacking chess pieces placements: Bishops and Anassas. arXiv:2411.16492 [math.CO], 2024. (considered as white board).

Eric Weisstein's World of Mathematics, Black Bishop Graph

Eric Weisstein's World of Mathematics, Independence Polynomial

Formula

From Eder G. Santos, Dec 01 2024: (Start)

T(n,k) = Sum_{j=0..k} binomial(ceiling(n/2),j) * Stirling2(n-j,n-k).

T(n,k) = T(n-1,k) + (n-k+A000035(n)) * T(n-1,k-1), T(n,0) = 1, T(0,k) = delta(k,0). (End)

Example

Triangle begins:
  1;
  1,  1;
  1,  2;
  1,  5,   4;
  1,  8,  14,      4;
  1, 13,  46,     46,      8;
  1, 18,  98,    184,    100,      8;
  1, 25,  206,   674,    836,    308,     16;
  1, 32,  356,  1704,   3532,   2816,    632,     16;
  1, 41,  612,  4196,  13756,  20476,  11896,   1912,     32;
  1, 50,  940,  8480,  38932,  89256,  93800,  37600,   3856,    32;
  1, 61, 1440, 16940, 106772, 361780, 629336, 506600, 154256, 11600, 64;
  ...
Corresponding independence polynomials:
  1, (empty graph)
  1+x, (K_1)
  1+2*x, (P_2 = K_2)
  1+5*x+4*x^2, (butterfly graph)
  1+8*x+14*x^2+4*x^3,
  ...

Maple

with(combinat); with(gfun);
T:=n->add(stirling2(n+1, n+1-k)*x^k, k=0..n);
# bishops on black squares
bish:=proc(n) local m, k, i, j, t1, t2; global T;
if n<2 then return [1$(n+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+1, 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:
# Alternative:
T:= (n, k)-> add(binomial(ceil(n/2), j)*Stirling2(n-j, n-k), j=0..k):
seq(seq(T(n, k), k=0..n-`if`(n>1, 1, 0)), n=0..11);  # Alois P. Heinz, Dec 01 2024

Mathematica

CoefficientList[Table[Sum[x^n Binomial[Ceiling[n/2], k] BellB[n - k, 1/x], {k, 0, Ceiling[n/2]}], {n, 10}], x] (* Eric W. Weisstein, Jun 26 2017 *)

Prog

(SageMath) def stirling2_negativek(n, k):
  if k < 0: return 0
  else: return stirling_number2(n, k)
print([sum([binomial(ceil(n/2), l)*stirling2_negativek(n-l, n-k) for l in [0..k]]) for n in [0..10] for k in [0..n-1+kronecker_delta(n, 1)+kronecker_delta(n, 0)]]) # Eder G. Santos, Dec 01 2024

Crossrefs

Alternate rows give A088960.

Row sums are A216332(n+1).

Cf. A274106 (white squares), A288183, A201862, A002465.

Sequence in context: A345454 A271684 A194682 * A366156 A056242 A343960

Adjacent sequences: A274102 A274103 A274104 * A274106 A274107 A274108

Keyword

nonn,tabf

Author

N. J. A. Sloane, Jun 14 2016

Extensions

T(0,0) prepended by Eder G. Santos, Dec 01 2024

Status

approved