A277443 Square array A(n,k) (n>=1, k>=1) read by antidiagonals: A(n,k) is the number of n-colorings of the prism graph Y_k on 2k vertices.

0, 0, 0, 0, 2, 0, 0, 0, 18, 0, 0, 2, 12, 84, 0, 0, 0, 114, 264, 260, 0, 0, 2, 180, 2652, 1920, 630, 0, 0, 0, 858, 16080, 29660, 8520, 1302, 0, 0, 2, 1932, 119844, 367080, 198030, 28140, 2408, 0, 0, 0, 7074, 816984, 4843460, 4067280, 932862, 76272, 4104, 0, 0, 2, 18660, 5784492, 62682480, 85847910, 28576380, 3440024, 179424, 6570, 0

Offset

1,5

Comments

Y_1 contains a loop, so has no colorings with any number of colors. Y_2 is the cycle graph C_4 with two double edges; these two graphs are therefore equivalent with respect to number of colorings.

Links

Table of n, a(n) for n=1..66.

N. L. Biggs, R. M. Damerell and D. A. Sands, Recursive families of graphs, Journal of Combinatorial Theory Series B Volume 12 (1972), 123-131. MR0294172

Eric Weisstein's World of Mathematics, Prism Graph

Wikipedia, Chromatic polynomial

Formula

A(n,k) = (n^2-3n+3)^k+(n-1)((3-n)^k+(1-n)^k)+n^2-3n+1.

Example

Square array A(n,k) begins:
  0,   0,    0,      0,       0,        0,          0, ...
  0,   2,    0,      2,       0,        2,          0, ...
  0,  18,   12,    114,     180,      858,       1932, ...
  0,  84,  264,   2652,   16080,   119844,     816984, ...
  0, 260, 1920,  29660,  367080,  4843460,   62682480, ...
  0, 630, 8520, 198030, 4067280, 85847910, 1800687000, ...

Crossrefs

Cf. A277444 (colorings of Möbius ladders), A182406 (square grid graphs).

Columns k=1,2 are A000004 and A091940.

Rows n=1,2 are A000004 and A010673.

Sequence in context: A136615 A283950 A342376 * A209401 A029696 A118887

Adjacent sequences: A277440 A277441 A277442 * A277444 A277445 A277446

Keyword

nonn,tabl

Author

Jeremy Tan, Oct 15 2016

Status

approved