

A290615


Number of maximal independent vertex sets (and minimal vertex covers) in the ntriangular honeycomb bishop graph.


6



1, 2, 5, 14, 45, 164, 661, 2906, 13829, 70736, 386397, 2242118, 13759933, 88975628, 604202693, 4296191090, 31904681877, 246886692680, 1986631886029, 16592212576862, 143589971363981, 1285605080403332, 11891649654471285, 113491862722958474, 1116236691139398565
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

See A146304 for algorithm and PARI code to produce this sequence.
The total number of independent vertex sets is given by Bell(n+1) where Bell=A000110.
A bishop can move along two axes in the triangular honeycomb grid.
Equivalently, the number of arrangements of nonattacking rooks on an n X n right triangular board with every square controlled by at least one rook. (End)


LINKS



FORMULA

a(n) = Sum_{k=0..2^(n1)  1} b(k) for n > 0 where b(2n+1) = b(n  2^f(n)), b(2n) = b(n) + b(2n  2^f(n)) for n > 0 with b(0) = b(1) = 1 and where f(n) = A007814(n). Also b((4^n  1)/3) = (floor((n+1)/2)!)^3.  Mikhail Kurkov, Sep 18 2021
a(n) = Sum_{m=0..n} Sum_{k=0..min(m,nm)} k! * S(m,k) * S(n+1m,k+1), where S(,) are Stirling numbers of second kind.  Max Alekseyev, Oct 14 2021


MATHEMATICA

Table[Sum[k! StirlingS2[m, k] StirlingS2[n + 1  m, k + 1], {m, 0, n}, {k, 0, Min[m, n  m]}], {n, 20}] (* Eric W. Weisstein, Feb 01 2024 *)


PROG

(PARI) { f(n, p, q)=polcoeff(1/(1x) + sum(k=2, n\2+1, prod(j=2, k, q^(j1)+p*sum(r=0, j2, q^r))*x^(2*(k1))*(1(q^(k1)+p*sum(s=0, k2, q^s)1)*x)/((1x)*prod(i=2, k, (1(q^(i1)+p*sum(t=0, i2, q^t))*x)^2))) + x*O(x^n), n); }
a(n)=sum(k=0, n1, f(k, 1, 1)); \\ if we change b(2n) from the formula section to p*b(n) + q*b(2n  2^f(n)), then prog works for any p, q \\ Mikhail Kurkov, Sep 25 2021
(PARI) { A290615(n) = sum(m=0, n, sum(k=0, min(m, nm), k! * stirling(m, k, 2) * stirling(n+1m, k+1, 2) )); } \\ Max Alekseyev, Oct 14 2021


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



