cp's OEIS Frontend

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

%I A321249 #20 Feb 16 2025 08:33:57
%S A321249 3,18,3654,32205621510,22027184720660994230386220070258,
%T A321249 7047607950011539317413452449625581782178125646326877171638889103186225220299274232740598917544
%N A321249 Number of maximal independent vertex sets in the n-Hanoi graph.
%H A321249 Pontus von Brömssen, <a href="/A321249/b321249.txt">Table of n, a(n) for n = 1..8</a>
%H A321249 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/HanoiGraph.html">Hanoi Graph</a>
%H A321249 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MaximalIndependentVertexSet.html">Maximal Independent Vertex Set</a>
%o A321249 (Python)
%o A321249 from itertools import product
%o A321249 from math import prod
%o A321249 from collections import defaultdict
%o A321249 adjacent_ok=lambda u,v: not (u==v==2 or u+v<=1)
%o A321249 apex_config_ok=lambda x: all(adjacent_ok(x[i][(i+1)%3],x[(i+1)%3][i]) for i in range(3))
%o A321249 coeffs=defaultdict(lambda:defaultdict(int)) # Pre-computed coefficients to be used in the recursion for v(n).
%o A321249 for x in product(product(range(3),repeat=3),repeat=3):
%o A321249   # 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.
%o A321249   # The elements of the triples represent the configurations at the apex nodes:
%o A321249   #   0: the apex node is not in the set, nor any of its neighbors;
%o A321249   #   1: the apex node is not in the set, but one of its neighbors is;
%o A321249   #   2: the apex node is in the set.
%o A321249   if x[0][0]<=x[1][1]<=x[2][2] and apex_config_ok(x):
%o A321249     xsort=tuple(sorted(tuple(sorted(t)) for t in x))
%o A321249     coeffs[(x[0][0],x[1][1],x[2][2])][xsort]+=1
%o A321249 def v(n):
%o A321249   if n==1:
%o A321249     w={c:0 for c in coeffs}
%o A321249     w[(0,0,0)]=w[(1,1,2)]=1
%o A321249     return w
%o A321249   v0=v(n-1)
%o A321249   return {c:sum(coeffs[c][x]*prod(v0[k] for k in x) for x in coeffs[c]) for c in coeffs}
%o A321249 def A321249(n):
%o A321249   vn=v(n)
%o A321249   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
%Y A321249 Cf. A288490 (independent vertex sets in the n-Hanoi graph).
%Y A321249 Cf. A297536 (maximum independent vertex sets in the n-Hanoi graph).
%Y A321249 Cf. A288839 (chromatic polynomials of the n-Hanoi graph).
%Y A321249 Cf. A193233 (chromatic polynomial with highest coefficients first).
%Y A321249 Cf. A137889 (directed Hamiltonian paths in the n-Hanoi graph).
%Y A321249 Cf. A286017 (matchings in the n-Hanoi graph).
%Y A321249 Cf. A193136 (spanning trees of the n-Hanoi graph).
%Y A321249 Cf. A288796 (undirected paths in the n-Hanoi graph).
%K A321249 nonn
%O A321249 1,1
%A A321249 _Eric W. Weisstein_, Nov 01 2018
%E A321249 More terms from _Pontus von Brömssen_, Mar 14 2020