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

Author

Eric W. Weisstein, Aug 07 2017

Keywords

• nonn

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

Crossrefs

Row sums of A290724.

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

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

Programs

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 *)

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

Formula

Conjecture: 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

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

Extensions

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