|
|
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.
|
|
6
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
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')):
|
|
MATHEMATICA
|
a[n_] := Module[{m, e}, {m, e} = QuotientRemainder[n - 1, 2];
Sum[Binomial[m, k]*BellB[m + k + e], {k, 0, m}]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|