A321249 Number of maximal independent vertex sets in the n-Hanoi graph.

3, 18, 3654, 32205621510, 22027184720660994230386220070258, 7047607950011539317413452449625581782178125646326877171638889103186225220299274232740598917544

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, Maximal Independent Vertex Set

Prog

(Python)
from itertools import product
from math import prod
from collections import defaultdict
adjacent_ok=lambda u, v: not (u==v==2 or u+v<=1)
apex_config_ok=lambda x: all(adjacent_ok(x[i][(i+1)%3], x[(i+1)%3][i]) for i in range(3))
coeffs=defaultdict(lambda:defaultdict(int)) # Pre-computed coefficients to be used in the recursion for v(n).
for x in product(product(range(3), repeat=3), repeat=3):
  # Each triple x[i] represents "almost maximal" independent sets (an apex node and its neighbors may all be outside the set) of one of the three subtriangles of H_n.
  # The elements of the triples represent the configurations at the apex nodes:
  #   0: the apex node is not in the set, nor any of its neighbors;
  #   1: the apex node is not in the set, but one of its neighbors is;
  #   2: the apex node is in the set.
  if x[0][0]<=x[1][1]<=x[2][2] and apex_config_ok(x):
    xsort=tuple(sorted(tuple(sorted(t)) for t in x))
    coeffs[(x[0][0], x[1][1], x[2][2])][xsort]+=1
def v(n):
  if n==1:
    w={c:0 for c in coeffs}
    w[(0, 0, 0)]=w[(1, 1, 2)]=1
    return w
  v0=v(n-1)
  return {c:sum(coeffs[c][x]*prod(v0[k] for k in x) for x in coeffs[c]) for c in coeffs}
def A321249(n):
  vn=v(n)
  return vn[(1, 1, 1)]+3*vn[(1, 1, 2)]+3*vn[(1, 2, 2)]+vn[(2, 2, 2)] # Pontus von Brömssen, Apr 10 2021

Crossrefs

Cf. A288490 (independent vertex sets in the n-Hanoi graph).

Cf. A297536 (maximum 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: A157556 A214442 A057133 * A001999 A157580 A101293

Adjacent sequences: A321246 A321247 A321248 * A321250 A321251 A321252

Keyword

nonn

Author

Eric W. Weisstein, Nov 01 2018

Extensions

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

Status

approved