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