A290615 Number of maximal independent vertex sets (and minimal vertex covers) in the n-triangular honeycomb bishop graph.

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

Offset

1,2

Comments

From Andrew Howroyd, Aug 09 2017: (Start)

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 non-attacking rooks on an n X n right triangular board with every square controlled by at least one rook. (End)

Links

Andrew Howroyd, Table of n, a(n) for n = 1..150

Max Alekseyev, Subsequences of odd powers, answer to question on Mathoverflow.

Max Alekseyev, Generating function for partial sums of the sequence, answer to question on Mathoverflow.

Peter Taylor, Subsequence of the cubes, answer to question on Mathoverflow.

Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set

Eric Weisstein's World of Mathematics, Minimal Vertex Cover

Formula

a(n) = Sum_{k=0..2^(n-1) - 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 [verification needed]

a(n) = Sum_{m=0..n} Sum_{k=0..min(m,n-m)} k! * S(m,k) * S(n+1-m,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/(1-x) + sum(k=2, n\2+1, prod(j=2, k, q^(j-1)+p*sum(r=0, j-2, q^r))*x^(2*(k-1))*(1-(q^(k-1)+p*sum(s=0, k-2, q^s)-1)*x)/((1-x)*prod(i=2, k, (1-(q^(i-1)+p*sum(t=0, i-2, q^t))*x)^2))) + x*O(x^n), n); }
  a(n)=sum(k=0, n-1, 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 [verification needed]
(PARI) { A290615(n) = sum(m=0, n, sum(k=0, min(m, n-m), k! * stirling(m, k, 2) * stirling(n+1-m, k+1, 2) )); } \\ Max Alekseyev, Oct 14 2021

Crossrefs

Row sums of A290724.

Cf. A000110 (independent vertex sets), A007814, A146304.

Similar recurrences: A124758, A243499, A284005, A329369, A341392.

Sequence in context: A081444 A268004 A119429 * A347420 A174300 A059216

Adjacent sequences: A290612 A290613 A290614 * A290616 A290617 A290618

Keyword

nonn,changed

Author

Eric W. Weisstein, Aug 07 2017

Extensions

Terms a(10) and beyond from Andrew Howroyd, Aug 09 2017

Status

approved