A137889 -id:A137889 - cp's OEIS frontend

A193233 Triangle T(n,k), n>=1, 0<=k<=3^n, read by rows: row n gives the coefficients of the chromatic polynomial of the Hanoi graph H_n, highest powers first.

1, -3, 2, 0, 1, -12, 63, -190, 363, -455, 370, -180, 40, 0, 1, -39, 732, -8806, 76293, -507084, 2689452, -11689056, 42424338, -130362394, 342624075, -776022242, 1522861581, -2598606825, 3863562996, -5007519752, 5652058863, -5541107684, 4697231261

Offset: 1

Alois P. Heinz, Jul 18 2011

The Hanoi graph H_n has 3^n vertices and 3*(3^n-1)/2 edges. It represents the states and allowed moves in the Towers of Hanoi problem with n disks. The chromatic polynomial of H_n has 3^n+1 coefficients.

			2 example graphs:          o
.                         / \
.                        o---o
.                       /     \
.             o        o       o
.            / \      / \     / \
.           o---o    o---o---o---o
Graph:       H_1          H_2
Vertices:     3            9
Edges:        3           12
The Hanoi graph H_1 equals the cycle graph C_3 with chromatic polynomial
   q^3 -3*q^2 +2*q => [1, -3, 2, 0].
Triangle T(n,k) begins:
  1,    -3,      2,          0;
  1,   -12,     63,       -190,         363,            -455,  ...
  1,   -39,    732,      -8806,       76293,         -507084,  ...
  1,  -120,   7113,    -277654,     8028540,      -183411999,  ...
  1,  -363,  65622,   -7877020,   706303350,    -50461570575,  ...
  1, -1092, 595443, -216167710, 58779577593, -12769539913071,  ...
  ...

Alois P. Heinz, Rows n = 1..6, flattened
Eric Weisstein's World of Mathematics, Chromatic Polynomial
Eric Weisstein's World of Mathematics, Hanoi Graph
Wikipedia, Chromatic Polynomial
Wikipedia, Tower of Hanoi

Cf. A000244, A029858.
Cf. A288839 (chromatic polynomials of the n-Hanoi graph).
Cf. A137889 (directed Hamiltonian paths in the n-Hanoi graph).
Cf. A288490 (independent vertex sets 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).

A286017 Number of matchings in the n-Hanoi graph.

Original entry on oeis.org

4, 125, 4007754, 132460031222098852477, 4782311037918647241715144272946478084784910628903006412891408

Offset: 1

Eric W. Weisstein, Jun 16 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..7
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, 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. A288490 (independent vertex sets in the n-Hanoi graph).
Cf. A193136 (spanning trees of the n-Hanoi graph).
Cf. A288796 (undirected paths in the n-Hanoi graph).

next[{h0_, h1_, h2_, h3_}] := {h0^3 + 3*h0*h1^2 + 3*h1^2*h2 + h2^3, h0^2*h1 + 2*h0*h1*h2 + h1^3 + 2*h1*h2^2 + h1^2*h3 + h2^2*h3, h0*h1^2 + 2*h1^2*h2 + h0*h2^2 + 2*h1*h2*h3 + h2^3 + h2*h3^2, h1^3 + 3*h1*h2^2 + 3*h2^2*h3 + h3^3};
a[n_] := Module[{v = {1, 1, 0, 0}}, For[i = 1, i <= n, i++, v = next[v]]; v[[1]]];
Array[a, 5] (* Jean-François Alcover, Oct 02 2017, translated from Andrew Howroyd's PARI code *)
Rest @ NestList[Function[{h, i, j, k}, {h^3 + 3 h i^2 + 3 i^2 j + j^3, h^2 i + 2 h i j + i^3 + 2 i j^2 + i^2 k + j^2 k, h i^2 + 2 i^2 j + h j^2 + 2 i j k + j^3 + j k^2, i^3 + 3 i j^2 + 3 j^2 k + k^3}] @@ # &, {1, 1, 0, 0}, 5][[All, 1]] (* Eric W. Weisstein, Oct 02 2017 *)

\\ here h0..h3 are number of matchings in Hanoi graph less 0..3 apex vertices.
Next(h0, h1, h2, h3)={[ h0^3 + 3*h0*h1^2 + 3*h1^2*h2 + h2^3, h0^2*h1 + 2*h0*h1*h2 + h1^3 + 2*h1*h2^2 + h1^2*h3 + h2^2*h3, h0*h1^2 + 2*h1^2*h2 + h0*h2^2 + 2*h1*h2*h3 + h2^3 + h2*h3^2, h1^3 + 3*h1*h2^2 + 3*h2^2*h3 + h3^3]}
a(n) = {my(v); v=[1, 1, 0, 0]; for(i=1, n, v=Next(v[1], v[2], v[3], v[4])); v[1]} \\ Andrew Howroyd, Jun 17 2017

a(5) from Andrew Howroyd, Jun 17 2017

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

Original entry on oeis.org

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

A288796 Number of (undirected) paths in the n-Hanoi graph.

Original entry on oeis.org

6, 279, 305868, 10210452146391, 5764678901089651494212581315486920, 7007522073643519244177937570089174585653471798870178330313274704558499562496773948518048745883

Offset: 1

Eric W. Weisstein, Jun 16 2017

nonn

Terms up to about a(10) can be computed using a transfer matrix method. - Andrew Howroyd, Jun 18 2017

Andrew Howroyd, Table of n, a(n) for n = 1..7
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, 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. A288490 (independent vertex sets in the n-Hanoi graph).
Cf. A286017 (matchings in the n-Hanoi graph).
Cf. A193136 (spanning trees of the n-Hanoi graph).

a(4)-a(6) from Andrew Howroyd, Jun 18 2017

A288839 Triangle read by rows: coefficients of the chromatic polynomial of the n-Hanoi graph.

Original entry on oeis.org

0, 2, -3, 1, 0, 40, -180, 370, -455, 363, -190, 63, -12, 1, 0, 608000, -6960000, 40524800, -158999200, 468979200, -1099617480, 2117585600, -3419826630, 4697231261, -5541107684, 5652058863, -5007519752, 3863562996, -2598606825, 1522861581, -776022242, 342624075, -130362394, 42424338, -11689056, 2689452, -507084, 76293, -8806, 732, -39, 1

Offset: 1

Eric W. Weisstein, Jun 17 2017

Equal to A193233 with ordering of row elements reversed.

			Polynomials:
(x-2)*(x-1)*x
(x-2)^3*(x-1)*x*(5-10*x+10*x^2-5*x^3+x^4)
(x-2)^6*(x-1)*x*(-9500+70750*x+...+x^19)
Coefficients:
0, 2, -3, 1;
0, 40, -180, 370, -455, 363, -190, 63, -12, 1;
0, 608000, -6960000, 40524800, -158999200, ..., -39, 1;

Eric Weisstein's World of Mathematics, Chromatic Polynomial
Eric Weisstein's World of Mathematics, Hanoi Graph

Cf. A193233 (chromatic polynomial with highest coefficients first).
Cf. A137889 (directed Hamiltonian paths in the n-Hanoi graph).
Cf. A288490 (independent vertex sets 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).

A193136 Numbers of spanning trees of the Hanoi graphs.

Original entry on oeis.org

3, 135, 20503125, 119709242282867431640625, 39709946214287663263304759568121660162631769708241336047649383544921875

Offset: 1

Eric W. Weisstein, Jul 16 2011

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..6
Eric Weisstein's World of Mathematics, Hanoi Graph
Eric Weisstein's World of Mathematics, Spanning Tree

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. A288490 (independent vertex sets in the n-Hanoi graph).
Cf. A286017 (matchings in the n-Hanoi graph).
Cf. A288796 (undirected paths in the n-Hanoi graph).

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

Eric W. Weisstein, Dec 31 2017

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, Maximum Independent Vertex Set

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

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

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

A308134 Number of (undirected) Hamiltonian paths in the n-Hanoi graph.

Original entry on oeis.org

3, 18, 192, 2730, 42408, 673698, 10760592, 172097370, 2753276088, 44051309778, 704816584992, 11277048051210, 180432700116168, 2886922928640258, 46190765770153392, 739052247984440250, 11824835950442034648, 189197375137965657138, 3027158001931410345792

Offset: 1

Eric W. Weisstein, May 14 2019

Colin Barker, Table of n, a(n) for n = 1..800
Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, Hanoi Graph
Index entries for linear recurrences with constant coefficients, signature (24,-147,316,-192).

Cf. A137889.

Vec(3*x*(1 - 18*x + 67*x^2 - 60*x^3) / ((1 - x)*(1 - 3*x)*(1 - 4*x)*(1 - 16*x)) + O(x^20)) \\ Colin Barker, Jul 19 2019

a(n) = A137889(n)/2.
From Colin Barker, Jul 19 2019: (Start)
G.f.: 3*x*(1 - 18*x + 67*x^2 - 60*x^3) / ((1 - x)*(1 - 3*x)*(1 - 4*x)*(1 - 16*x)).
a(n) = 24*a(n-1) - 147*a(n-2) + 316*a(n-3) - 192*a(n-4) for n>4.
a(n) = (208 + 16*3^(2+n) + 13*4^(2+n) + 25*16^n) / 624.
(End)

cp's OEIS Frontend

A193233 Triangle T(n,k), n>=1, 0<=k<=3^n, read by rows: row n gives the coefficients of the chromatic polynomial of the Hanoi graph H_n, highest powers first.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A286017 Number of matchings in the n-Hanoi graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

A288796 Number of (undirected) paths in the n-Hanoi graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A288839 Triangle read by rows: coefficients of the chromatic polynomial of the n-Hanoi graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A193136 Numbers of spanning trees of the Hanoi graphs.

Views

Author

Keywords

Links

Crossrefs

A297536 Number of maximum independent vertex sets in the n-Hanoi graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Extensions

A308134 Number of (undirected) Hamiltonian paths in the n-Hanoi graph.

Views

Author

Keywords

Links

Crossrefs

Programs