login
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.
14

%I #21 Nov 02 2021 22:11:48

%S 1,-3,2,0,1,-12,63,-190,363,-455,370,-180,40,0,1,-39,732,-8806,76293,

%T -507084,2689452,-11689056,42424338,-130362394,342624075,-776022242,

%U 1522861581,-2598606825,3863562996,-5007519752,5652058863,-5541107684,4697231261

%N 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.

%C 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.

%H Alois P. Heinz, <a href="/A193233/b193233.txt">Rows n = 1..6, flattened</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ChromaticPolynomial.html">Chromatic Polynomial</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HanoiGraph.html">Hanoi Graph</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Chromatic_polynomial">Chromatic Polynomial</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Tower_of_Hanoi">Tower of Hanoi</a>

%e 2 example graphs: o

%e . / \

%e . o---o

%e . / \

%e . o o o

%e . / \ / \ / \

%e . o---o o---o---o---o

%e Graph: H_1 H_2

%e Vertices: 3 9

%e Edges: 3 12

%e The Hanoi graph H_1 equals the cycle graph C_3 with chromatic polynomial

%e q^3 -3*q^2 +2*q => [1, -3, 2, 0].

%e Triangle T(n,k) begins:

%e 1, -3, 2, 0;

%e 1, -12, 63, -190, 363, -455, ...

%e 1, -39, 732, -8806, 76293, -507084, ...

%e 1, -120, 7113, -277654, 8028540, -183411999, ...

%e 1, -363, 65622, -7877020, 706303350, -50461570575, ...

%e 1, -1092, 595443, -216167710, 58779577593, -12769539913071, ...

%e ...

%Y Cf. A000244, A029858.

%Y Cf. A288839 (chromatic polynomials of the n-Hanoi graph).

%Y Cf. A137889 (directed Hamiltonian paths in the n-Hanoi graph).

%Y Cf. A288490 (independent vertex sets in the n-Hanoi graph).

%Y Cf. A286017 (matchings in the n-Hanoi graph).

%Y Cf. A193136 (spanning trees of the n-Hanoi graph).

%Y Cf. A288796 (undirected paths in the n-Hanoi graph).

%K sign,tabf,look,hard

%O 1,2

%A _Alois P. Heinz_, Jul 18 2011