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

 

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

License Agreements, Terms of Use, Privacy Policy. .

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