A375256
Number of pairs of antipodal vertices in the level n Hanoi graph.
Original entry on oeis.org
3, 12, 39, 129, 453, 1677, 6429, 25149, 99453, 395517, 1577469, 6300669, 25184253, 100700157, 402726909, 1610760189, 6442745853, 25770393597, 103080394749, 412319219709, 1649272160253, 6597079203837, 26388297940989, 105553154015229, 422212540563453, 1688850011258877, 6755399743045629
Offset: 1
2 example graphs:
o
/ \
o---o
/ \
o o o
/ \ / \ / \
o---o o---o---o---o
Graph: H_1 H_2
Since the level 1 Hanoi graph is a triangle, a(1) = 3.
- Paolo Xausa, Table of n, a(n) for n = 1..1000
- Allan Bickle, Properties of Sierpinski Triangle Graphs, Springer PROMS 448 (2021) 295-303.
- A. Hinz, S. Klavzar, and S. Zemljic, A survey and classification of Sierpinski-type graphs, Discrete Applied Mathematics 217 3 (2017), 565-600.
- Eric Weisstein's World of Mathematics, Hanoi Graph
- Index entries for linear recurrences with constant coefficients, signature (7,-14,8).
Cf.
A370933 (antipodal pairs in Sierpiński triangle graphs).
-
A375256[n_] := 3*(2^(2*n - 3) + 3*2^(n - 2) - 1);
Array[A375256, 30] (* or *)
LinearRecurrence[{7, -14, 8}, {3, 12, 39}, 30] (* Paolo Xausa, Sep 23 2024 *)
-
a(n) = 3*(2^(2*n-3)+3*2^(n-2)-1); \\ Michel Marcus, Aug 08 2024
A297536
Number of maximum independent vertex sets in the n-Hanoi graph.
Original entry on oeis.org
3, 18, 2925, 11216538648, 627285206516110230354416268831, 109715796815760578436090875708748277077073796614051376195149103817368827024587948919162326
Offset: 1
Cf.
A288490 (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).
-
(* Except for one of the initial values, this program is identical to the program for A288490. *)
{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}] @@ # &, {0, 1, 0, 0}, 4] (* Pontus von Brömssen, Mar 14 2020 *)
-
\\ Except for one of the initial values, this program is identical to the program by Andrew Howroyd for A288490.
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=[0, 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])} \\ Pontus von Brömssen, Mar 14 2020
-
from itertools import islice
def A297536_gen(): # generator of terms
f,g,h,p = 0,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)
A297536_list = list(islice(A297536_gen(),6)) # Chai Wah Wu, Jan 11 2024
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
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
A381320
Number of minimum vertex colorings in the n-Hanoi graph.
Original entry on oeis.org
6, 66, 85200, 183250434809856, 1823313150135576711941779566275453880631296, 1796015231442383417566549899388909415521140128662444489798112174969514654167314109511319978572879992886003172220405085684891648
Offset: 1
Cf.
A193233 (coefficients of chromatic polynomial).
Cf.
A288839 (coefficients of chromatic polynomial, highest powers first).
Comments