cp's OEIS Frontend

A288490 Number of independent vertex sets and vertex covers in the n-Hanoi graph.

%I A288490 #46 Feb 16 2025 08:33:47
%S A288490 4,52,108144,967067994163264,
%T A288490 691513106932053164262669026747190128930258944
%N A288490 Number of independent vertex sets and vertex covers in the n-Hanoi graph.
%C A288490 Term a(6) has 135 decimal digits and a(7) has 404 decimal digits. - _Andrew Howroyd_, Jun 19 2017
%H A288490 Andrew Howroyd, <a href="/A288490/b288490.txt">Table of n, a(n) for n = 1..7</a>
%H A288490 Hanlin Chen, Renfang Wu, Guihua Huang, and Hanyuan Deng, <a href="https://doi.org/10.26493/1855-3974.783.9b5">Independent Sets on the Towers of Hanoi Graphs</a>, Ars Mathematica Contemporanea, volume 12, number 2, 2017, pages 247-260.  Section 3, i_n = a(n).
%H A288490 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HanoiGraph.html">Hanoi Graph</a>
%H A288490 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>
%H A288490 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/VertexCover.html">Vertex Cover</a>
%t A288490 {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]
%o A288490 (PARI)
%o A288490 \\ Here h0..h3 is independent sets with 0..3 of the 3 apex vertices occupied.
%o A288490 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]}
%o A288490 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
%o A288490 (Python)
%o A288490 from itertools import islice
%o A288490 def A288490_gen(): # generator of terms
%o A288490     f,g,h,p = 1,1,0,0
%o A288490     while True:
%o A288490         yield f+3*(g+h)+p
%o A288490         a, b = f+(g<<1), g+(h<<1)
%o A288490         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)
%o A288490 A288490_list = list(islice(A288490_gen(),5)) # _Chai Wah Wu_, Jan 11 2024
%Y A288490 Cf. A297536 (maximum independent vertex sets in the n-Hanoi graph).
%Y A288490 Cf. A321249 (maximal independent vertex sets in the n-Hanoi graph).
%Y A288490 Cf. A288839 (chromatic polynomials of the n-Hanoi graph).
%Y A288490 Cf. A193233 (chromatic polynomial with highest coefficients first).
%Y A288490 Cf. A137889 (directed Hamiltonian paths in the n-Hanoi graph).
%Y A288490 Cf. A286017 (matchings in the n-Hanoi graph).
%Y A288490 Cf. A193136 (spanning trees of the n-Hanoi graph).
%Y A288490 Cf. A288796 (undirected paths in the n-Hanoi graph).
%K A288490 nonn
%O A288490 1,1
%A A288490 _Eric W. Weisstein_, Jun 16 2017
%E A288490 a(5) from _Andrew Howroyd_, Jun 19 2017