The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A321249 Number of maximal independent vertex sets in the n-Hanoi graph. 3
 3, 18, 3654, 32205621510, 22027184720660994230386220070258, 7047607950011539317413452449625581782178125646326877171638889103186225220299274232740598917544 (list; graph; refs; listen; history; text; internal format)
 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 20 16:58 EDT 2022. Contains 353876 sequences. (Running on oeis4.)