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.

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

Author

R. H. Hardin, Sep 01 2012

Keywords

• nonn

Comments

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

Examples

			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
		

Links

• 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

Crossrefs

Column 2 of A216084.

Row sums of A274106(n-1).

Cf. A020556, A094577, A216332, A201862, A286423.

Programs

Maple

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

Mathematica

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

Formula

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)