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).
KEYWORD
nonn
AUTHOR
Eric W. Weisstein, Nov 01 2018
EXTENSIONS
More terms from Pontus von Brömssen, Mar 14 2020
STATUS
approved