|
|
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.
|
|
1
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
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
|
|
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).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|