A216078 - OEIS

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.

%I #69 Oct 03 2022 08:39:22

%S 1,1,3,7,27,87,409,1657,9089,43833,272947,1515903,10515147,65766991,

%T 501178937,3473600465,28773452321,218310229201,1949230218691,

%U 16035686850327,153281759047387,1356791248984295,13806215066685433,130660110400259849,1408621900803060705

%N 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.

%C 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

%C 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

%H R. H. Hardin, <a href="/A216078/b216078.txt">Table of n, a(n) for n = 1..210</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/VertexCover.html">Vertex Cover</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/WhiteBishopGraph.html">White Bishop Graph</a>

%F 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

%F From _Vaclav Kotesovec_, Jul 29 2022: (Start)

%F a(2*k) = A020556(k).

%F a(2*k+1) = A094577(k). (End)

%e Some solutions for n = 5:

%e x 0 x 0 x 0 x 0 x 0 x 0 x 0 x 0 x 0 x 0

%e 1 x 1 x 1 x 1 x 1 x 1 x 1 x 1 x 1 x 1 x

%e x 2 x 0 x 0 x 2 x 0 x 1 x 1 x 2 x 2 x 1

%e 0 x 2 x 1 x 3 x 1 x 0 x 2 x 3 x 0 x 0 x

%e x 3 x 1 x 2 x 2 x 0 x 1 x 1 x 1 x 2 x 0

%e 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

%p a:= n-> (m-> add(binomial(m, k)*combinat[bell](m+k+e)

%p , k=0..m))(iquo(n-1, 2, 'e')):

%p seq(a(n), n=1..26); # _Alois P. Heinz_, Oct 03 2022

%t a[n_] := Module[{m, e}, {m, e} = QuotientRemainder[n - 1, 2];

%t Sum[Binomial[m, k]*BellB[m + k + e], {k, 0, m}]];

%t Table[a[n], {n, 1, 40}] (* _Jean-François Alcover_, Jul 25 2022, after _Francesca Aicardi_ *)

%Y Column 2 of A216084.

%Y Row sums of A274106(n-1).

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

%K nonn

%O 1,3

%A _R. H. Hardin_, Sep 01 2012