A106512 Array read by antidiagonals: a(n,k) = number of k-colorings of a circle of n nodes (n >= 1, k >= 1).

0, 0, 0, 0, 2, 0, 0, 6, 0, 0, 0, 12, 6, 2, 0, 0, 20, 24, 18, 0, 0, 0, 30, 60, 84, 30, 2, 0, 0, 42, 120, 260, 240, 66, 0, 0, 0, 56, 210, 630, 1020, 732, 126, 2, 0, 0, 72, 336, 1302, 3120, 4100, 2184, 258, 0, 0, 0, 90, 504, 2408, 7770, 15630, 16380, 6564, 510, 2, 0, 0, 110

Offset: 1

Author

Joshua Zucker, May 29 2005

Keywords

• nonn
• tabl

Comments

Note that we keep one edge in the circular graph even when there's only one node (so there are 0 colorings of one node with k colors).

Number of closed walks of length n on the complete graph K_{k}. - Andrew Howroyd, Mar 12 2017

Examples

			From _Andrew Howroyd_, Mar 12 2017: (Start)
Table begins:
  0 0   0     0      0       0        0        0         0 ...
  0 2   6    12     20      30       42       56        72 ...
  0 0   6    24     60     120      210      336       504 ...
  0 2  18    84    260     630     1302     2408      4104 ...
  0 0  30   240   1020    3120     7770    16800     32760 ...
  0 2  66   732   4100   15630    46662   117656    262152 ...
  0 0 126  2184  16380   78120   279930   823536   2097144 ...
  0 2 258  6564  65540  390630  1679622  5764808  16777224 ...
  0 0 510 19680 262140 1953120 10077690 40353600 134217720 ...
(End)
a(4,3) = 18 because there are three choices for the first node's color (call it 1) and then two choices for the second node's color (call it 2) and then the remaining two nodes can be 12, 13, or 32. So in total there are 3*2*3 = 18 ways. a(3,4) = 4*3*2 = 24 because the three nodes must be three distinct colors.
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1274

Crossrefs

Columns include A092297, A226493. Main diagonal is A118537.

Rows 2-7 are A002378, A007531, A091940, A061167, A131472, A133499.

Cf. A090860, A208535.

Formula

a(n, k) = (k-1)^n + (-1)^n * (k-1).

Extensions

a(67) corrected by Andrew Howroyd, Mar 12 2017