login
A288490
Number of independent vertex sets and vertex covers in the n-Hanoi graph.
10
4, 52, 108144, 967067994163264, 691513106932053164262669026747190128930258944
OFFSET
1,1
COMMENTS
Term a(6) has 135 decimal digits and a(7) has 404 decimal digits. - Andrew Howroyd, Jun 19 2017
LINKS
Hanlin Chen, Renfang Wu, Guihua Huang, and Hanyuan Deng, Independent Sets on the Towers of Hanoi Graphs, Ars Mathematica Contemporanea, volume 12, number 2, 2017, pages 247-260. Section 3, i_n = a(n).
Eric Weisstein's World of Mathematics, Hanoi Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Vertex Cover
MATHEMATICA
{1, 3, 3, 1} . # & /@ NestList[Function[{h, i, j, k}, {h^3 + 6 h^2 i + 9 h i^2 + 3 h^2 j + 2 i^3 + 6 h i j, h^2 i + 4 h i^2 + 2 h^2 j + h^2 k + 8 h i j + 3 i^3 + 4 i^2 j + 2 h j^2 + 2 h i k, h i^2 + 4 h i j + 2 i^3 + 7 i^2 j + 2 h i k + 3 h j^2 + 4 i j^2 + 2 i^2 k + 2 h j k, i^3 + 6 i^2 j + 9 i j^2 + 3 i^2 k + 2 j^3 + 6 i j k}] @@ # &, {1, 1, 0, 0}, 4]
PROG
(PARI)
\\ Here h0..h3 is independent sets with 0..3 of the 3 apex vertices occupied.
Next(h0, h1, h2, h3) = {[h0^3 + 6*h0^2*h1 + 9*h0*h1^2 + 3*h0^2*h2 + 2*h1^3 + 6*h0*h1*h2, h0^2*h1 + 4*h0*h1^2 + 2*h0^2*h2 + h0^2*h3 + 8*h0*h1*h2 + 3*h1^3 + 4*h1^2*h2 + 2*h0*h2^2 + 2*h0*h1*h3, h0*h1^2 + 4*h0*h1*h2 + 2*h1^3 + 7*h1^2*h2 + 2*h0*h1*h3 + 3*h0*h2^2 + 4*h1*h2^2 + 2*h1^2*h3 + 2*h0*h2*h3, h1^3 + 6*h1^2*h2 + 9*h1*h2^2 + 3*h1^2*h3 + 2*h2^3 + 6*h1*h2*h3]}
a(n) = {my(v); v=[1, 1, 0, 0]; for(i=2, n, v=Next(v[1], v[2], v[3], v[4])); v[1]+v[4]+3*(v[2]+v[3])} \\ Andrew Howroyd, Jun 20 2017
(Python)
from itertools import islice
def A288490_gen(): # generator of terms
f, g, h, p = 1, 1, 0, 0
while True:
yield f+3*(g+h)+p
a, b = f+(g<<1), g+(h<<1)
f, g, h, p = a*(f*(a+(b<<1)-h)+g**2), f*(p*a+b*(a+(g<<1))+2*h**2)+g**2*(g+(b<<1)), f*(g*(b+(h<<1))+3*h**2)+g*(g*((b<<1)+3*h)+(h<<1)**2)+p*(f*b+g*a), b*(g*(3*p+b+(h<<1))+h**2)
A288490_list = list(islice(A288490_gen(), 5)) # Chai Wah Wu, Jan 11 2024
CROSSREFS
Cf. A297536 (maximum independent vertex sets in the n-Hanoi graph).
Cf. A321249 (maximal independent vertex sets in the n-Hanoi graph).
Cf. A288839 (chromatic polynomials of the n-Hanoi graph).
Cf. A193233 (chromatic polynomial with highest coefficients first).
Cf. A137889 (directed Hamiltonian paths in the n-Hanoi graph).
Cf. A286017 (matchings in the n-Hanoi graph).
Cf. A193136 (spanning trees of the n-Hanoi graph).
Cf. A288796 (undirected paths in the n-Hanoi graph).
Sequence in context: A327234 A327373 A193914 * A219160 A111034 A214367
KEYWORD
nonn
AUTHOR
Eric W. Weisstein, Jun 16 2017
EXTENSIONS
a(5) from Andrew Howroyd, Jun 19 2017
STATUS
approved