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

Author

Jeremy Tan, Oct 15 2016

Keywords

• nonn
• tabl

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.

Examples

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

Links

• 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

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.

Formula

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