A216332 -id:A216332 - 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

A201862 Number of ways to place k nonattacking bishops on an n X n board, sum over all k>=0.

Original entry on oeis.org

1, 2, 9, 70, 729, 9918, 167281, 3423362, 82609921, 2319730026, 74500064809, 2711723081550, 110568316431609, 5016846683306758, 251180326892449969, 13806795579059621930, 827911558468860287041, 53940895144894708523922, 3799498445458163685753481, 288400498147873552894868886

Offset: 0

Vaclav Kotesovec, Dec 06 2011

nonn

Also the number of vertex covers and independent vertex sets of the n X n bishop graph.

Vaclav Kotesovec, Table of n, a(n) for n = 0..320
Vaclav Kotesovec, Non-attacking chess pieces
Eric Weisstein's World of Mathematics, Bishop Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Vertex Cover

Cf. A010790, A172123, A172124, A172127, A172129, A176886, A187239 - A187242, A002465, A216078, A216332.

Row sums of A378590.

knbishops[k_,n_]:=(If[n==1,If[k==1,1,0],(-1)^k/(2n-k)!
*Sum[Binomial[2n-k,n-k+i]*Sum[(-1)^m*Binomial[n-i,m]*m^Floor[n/2]*(m+1)^Floor[(n+1)/2],{m,1,n-i}]
*Sum[(-1)^m*Binomial[n-k+i,m]*m^Floor[(n+1)/2]*(m+1)^Floor[n/2],{m,1,n+i-k}],{i,Max[0,k-n],Min[k,n]}]]);
Table[1+Sum[knbishops[k,n],{k,1,2n-1}],{n,1,25}]

a(n) = A216078(n+1) * A216332(n+1). - Andrew Howroyd, May 08 2017

a(0)=1 prepended by Alois P. Heinz, 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)

A286423 Number of matchings in the n X n white bishop graph.

Original entry on oeis.org

2, 7, 130, 4207, 1166928, 541240697, 2907639077764, 25886034363696809, 3341096345926174809912, 713738790204487208874991935, 2645105778378736719464340469683304, 16238808907214611705432043192158547965751

Offset: 2

Andrew Howroyd, May 08 2017

nonn

Matchings are not necessarily perfect matchings.

C# software that can be used to compute this sequence can be found in A270228.

Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, White Bishop Graph

Cf. A286422, A287248, A270228, A216332 (independent vertex sets), A234630 (cycles).

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

A201862 Number of ways to place k nonattacking bishops on an n X n board, sum over all k>=0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

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

A286423 Number of matchings in the n X n white bishop graph.

Views

Author

Keywords

Comments

Links

Crossrefs