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

1, 2, 3, 10, 27, 114, 409, 2066, 9089, 52922, 272947, 1788850, 10515147, 76282138, 501178937, 3974779402, 28773452321, 247083681522, 1949230218691, 17984917069018, 153281759047387, 1510073008031682, 13806215066685433

Offset

1,2

Comments

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

Links

R. H. Hardin, Table of n, a(n) for n = 1..210

Eric Weisstein's World of Mathematics, Black Bishop Graph

Eric Weisstein's World of Mathematics, Independent Vertex Set

Eric Weisstein's World of Mathematics, Vertex Cover

Example

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

Mathematica

Table[Sum[Binomial[Ceiling[n/2], k] BellB[n - k], {k, 0, Ceiling[n/2]}], {n, 0, 20}] (* Eric W. Weisstein, Jun 25 2017 *)

Crossrefs

Column 2 of A216338.

Row sums of A274105(n-1) for n>2.

Cf. A216078, A201862, A286422.

Sequence in context: A264759 A323680 A171190 * A007029 A298083 A099435

Adjacent sequences: A216329 A216330 A216331 * A216333 A216334 A216335

Keyword

nonn

Author

R. H. Hardin, Sep 04 2012

Status

approved