login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A290615 Number of maximal independent vertex sets (and minimal vertex covers) in the n-triangular 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
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
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
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
(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
KEYWORD
nonn
AUTHOR
Eric W. Weisstein, Aug 07 2017
EXTENSIONS
Terms a(10) and beyond from Andrew Howroyd, Aug 09 2017
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 26 05:55 EST 2024. Contains 370335 sequences. (Running on oeis4.)