|
| |
|
|
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.
|
|
13
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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, ...
...
|
|
|
CROSSREFS
|
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).
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
