A297536 Number of maximum independent vertex sets in the n-Hanoi graph.

3, 18, 2925, 11216538648, 627285206516110230354416268831, 109715796815760578436090875708748277077073796614051376195149103817368827024587948919162326

Offset

1,1

Links

Pontus von Brömssen, Table of n, a(n) for n = 1..8

Eric Weisstein's World of Mathematics, Hanoi Graph

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

Mathematica

(* Except for one of the initial values, this program is identical to the program for 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}] @@ # &, {0, 1, 0, 0}, 4] (* Pontus von Brömssen, Mar 14 2020 *)

Prog

(PARI)
\\ Except for one of the initial values, this program is identical to the program by Andrew Howroyd for 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]}
a(n) = {my(v); v=[0, 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])} \\ Pontus von Brömssen, Mar 14 2020
(Python)
from itertools import islice
def A297536_gen(): # generator of terms
    f, g, h, p = 0, 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)
A297536_list = list(islice(A297536_gen(), 6)) # Chai Wah Wu, Jan 11 2024

Crossrefs

Cf. A288490 (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: A316369 A291078 A335181 * A157556 A214442 A057133

Adjacent sequences: A297533 A297534 A297535 * A297537 A297538 A297539

Keyword

nonn

Author

Eric W. Weisstein, Dec 31 2017

Extensions

More terms from Pontus von Brömssen, Mar 14 2020

Status

approved