OFFSET
1,3
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
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
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)
EXAMPLE
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
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
R. H. Hardin, Sep 01 2012
STATUS
approved