A297536 -id:A297536 - cp's OEIS frontend

A288490 Number of independent vertex sets and vertex covers in the n-Hanoi graph.

4, 52, 108144, 967067994163264, 691513106932053164262669026747190128930258944

Offset: 1

Eric W. Weisstein, Jun 16 2017

nonn

Term a(6) has 135 decimal digits and a(7) has 404 decimal digits. - Andrew Howroyd, Jun 19 2017

Andrew Howroyd, Table of n, a(n) for n = 1..7
Hanlin Chen, Renfang Wu, Guihua Huang, and Hanyuan Deng, Independent Sets on the Towers of Hanoi Graphs, Ars Mathematica Contemporanea, volume 12, number 2, 2017, pages 247-260. Section 3, i_n = a(n).
Eric Weisstein's World of Mathematics, Hanoi Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Vertex Cover

Cf. A297536 (maximum independent vertex sets in the n-Hanoi graph).
Cf. A321249 (maximal 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).

{1, 3, 3, 1} . # & /@ NestList[Function[{h, i, j, k}, {h^3 + 6 h^2 i + 9 h i^2 + 3 h^2 j + 2 i^3 + 6 h i j, h^2 i + 4 h i^2 + 2 h^2 j + h^2 k + 8 h i j + 3 i^3 + 4 i^2 j + 2 h j^2 + 2 h i k, h i^2 + 4 h i j + 2 i^3 + 7 i^2 j + 2 h i k + 3 h j^2 + 4 i j^2 + 2 i^2 k + 2 h j k, i^3 + 6 i^2 j + 9 i j^2 + 3 i^2 k + 2 j^3 + 6 i j k}] @@ # &, {1, 1, 0, 0}, 4]

\\ Here h0..h3 is independent sets with 0..3 of the 3 apex vertices occupied.
Next(h0,h1,h2,h3) = {[h0^3 + 6*h0^2*h1 + 9*h0*h1^2 + 3*h0^2*h2 + 2*h1^3 + 6*h0*h1*h2, h0^2*h1 + 4*h0*h1^2 + 2*h0^2*h2 + h0^2*h3 + 8*h0*h1*h2 + 3*h1^3 + 4*h1^2*h2 + 2*h0*h2^2 + 2*h0*h1*h3, h0*h1^2 + 4*h0*h1*h2 + 2*h1^3 + 7*h1^2*h2 + 2*h0*h1*h3 + 3*h0*h2^2 + 4*h1*h2^2 + 2*h1^2*h3 + 2*h0*h2*h3, h1^3 + 6*h1^2*h2 + 9*h1*h2^2 + 3*h1^2*h3 + 2*h2^3 + 6*h1*h2*h3]}
a(n) = {my(v);v=[1,1,0,0]; for(i=2,n,v=Next(v[1],v[2],v[3],v[4])); v[1]+v[4]+3*(v[2]+v[3])} \\ Andrew Howroyd, Jun 20 2017

from itertools import islice
def A288490_gen(): # generator of terms
    f,g,h,p = 1,1,0,0
    while True:
        yield f+3*(g+h)+p
        a, b = f+(g<<1), g+(h<<1)
        f,g,h,p = a*(f*(a+(b<<1)-h)+g**2), f*(p*a+b*(a+(g<<1))+2*h**2)+g**2*(g+(b<<1)), f*(g*(b+(h<<1))+3*h**2)+g*(g*((b<<1)+3*h)+(h<<1)**2)+p*(f*b+g*a), b*(g*(3*p+b+(h<<1))+h**2)
A288490_list = list(islice(A288490_gen(),5)) # Chai Wah Wu, Jan 11 2024

a(5) from Andrew Howroyd, Jun 19 2017

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

Original entry on oeis.org

3, 18, 3654, 32205621510, 22027184720660994230386220070258, 7047607950011539317413452449625581782178125646326877171638889103186225220299274232740598917544

Offset: 1

Eric W. Weisstein, Nov 01 2018

nonn

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

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

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

More terms from Pontus von Brömssen, Mar 14 2020

cp's OEIS Frontend

A288490 Number of independent vertex sets and vertex covers in the n-Hanoi graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions