A274106 -id:A274106 - cp's OEIS frontend

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

N. J. A. Sloane, Jun 14 2016

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

			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,
  ...

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

Alternate rows give A088960.
Row sums are A216332(n+1).
Cf. A274106 (white squares), A288183, A201862, A002465.

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:
# second Maple program:
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

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

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

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)

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

A216078 Number of horizontal and antidiagonal neighbor colorings of the odd squares of an n X 2 array with new integer colors introduced in row major order.

Original entry on oeis.org

1, 1, 3, 7, 27, 87, 409, 1657, 9089, 43833, 272947, 1515903, 10515147, 65766991, 501178937, 3473600465, 28773452321, 218310229201, 1949230218691, 16035686850327, 153281759047387, 1356791248984295, 13806215066685433, 130660110400259849, 1408621900803060705

Offset: 1

R. H. Hardin, Sep 01 2012

nonn

Number of vertex covers and independent vertex sets of the n-1 X n-1 white bishops graph. Equivalently, the number of ways to place any number of non-attacking bishops on the white squares of an n-1 X n-1 board. - Andrew Howroyd, May 08 2017

Number of pairs of partitions (A<=B) of [n-1] such that the nontrivial blocks of A are of type {k,n-1-k} if n is even, and of type {k,n-k} if n is odd. - Francesca Aicardi, May 28 2022

			Some solutions for n = 5:
  x 0   x 0   x 0   x 0   x 0   x 0   x 0   x 0   x 0   x 0
  1 x   1 x   1 x   1 x   1 x   1 x   1 x   1 x   1 x   1 x
  x 2   x 0   x 0   x 2   x 0   x 1   x 1   x 2   x 2   x 1
  0 x   2 x   1 x   3 x   1 x   0 x   2 x   3 x   0 x   0 x
  x 3   x 1   x 2   x 2   x 0   x 1   x 1   x 1   x 2   x 0
There are 4 white squares on a 3 X 3 board. There is 1 way to place no non-attacking bishops, 4 ways to place 1 and 2 ways to place 2 so a(4) = 1 + 4 + 2 = 7. - _Andrew Howroyd_, Jun 06 2017

R. H. Hardin, Table of n, a(n) for n = 1..210
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Vertex Cover
Eric Weisstein's World of Mathematics, White Bishop Graph

Column 2 of A216084.
Row sums of A274106(n-1).
Cf. A020556, A094577, A216332, A201862, A286423.

a:= n-> (m-> add(binomial(m, k)*combinat[bell](m+k+e)
           , k=0..m))(iquo(n-1, 2, 'e')):
seq(a(n), n=1..26);  # Alois P. Heinz, Oct 03 2022

a[n_] := Module[{m, e}, {m, e} = QuotientRemainder[n - 1, 2];
   Sum[Binomial[m, k]*BellB[m + k + e], {k, 0, m}]];
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Jul 25 2022, after Francesca Aicardi *)

a(n) = Sum_{k=0..m} binomial(m, k)*Bell(m+k+e), with m = floor((n-1)/2), e = (n+1) mod 2 and where Bell(n) is the Bell exponential number A000110(n). - Francesca Aicardi, May 28 2022
From Vaclav Kotesovec, Jul 29 2022: (Start)
a(2*k) = A020556(k).
a(2*k+1) = A094577(k). (End)

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.

cp's OEIS Frontend

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]).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

Formula

Extensions

A216078 Number of horizontal and antidiagonal neighbor colorings of the odd squares of an n X 2 array with new integer colors introduced in row major order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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