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

3, 18, 3654, 32205621510, 22027184720660994230386220070258, 7047607950011539317413452449625581782178125646326877171638889103186225220299274232740598917544

Offset: 1

Author

Eric W. Weisstein, Nov 01 2018

Keywords

• nonn

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

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).

Programs

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

Extensions

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