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,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

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

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

Sequence in context: A171224 A270741 A212220 * A145878 A195662 A340860

Adjacent sequences: A193230 A193231 A193232 * A193234 A193235 A193236

Keyword

sign,tabf,look,hard

Author

Alois P. Heinz, Jul 18 2011

Status

approved