A330618 Triangle read by rows: T(n,k) is the number of n-bead necklaces using exactly k colors with no adjacent beads having the same color.

0, 0, 1, 0, 0, 2, 0, 1, 3, 6, 0, 0, 6, 24, 24, 0, 1, 11, 80, 180, 120, 0, 0, 18, 240, 960, 1440, 720, 0, 1, 33, 696, 4410, 11340, 12600, 5040, 0, 0, 58, 1960, 18760, 73920, 137760, 120960, 40320, 0, 1, 105, 5508, 76368, 433944, 1209600, 1753920, 1270080, 362880

Offset: 1

Author

Andrew Howroyd, Dec 20 2019

Keywords

• nonn
• tabl

Comments

In the case of n = 1, the single bead is considered to be cyclically adjacent to itself giving T(1,1) = 0. If compatibility with A208535 is wanted then T(1,1) should be 1.

Examples

			Triangle begins:
  0;
  0, 1;
  0, 0,  2;
  0, 1,  3,    6;
  0, 0,  6,   24,    24;
  0, 1, 11,   80,   180,   120;
  0, 0, 18,  240,   960,  1440,    720;
  0, 1, 33,  696,  4410, 11340,  12600,   5040;
  0, 0, 58, 1960, 18760, 73920, 137760, 120960, 40320;
  ...
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)

Crossrefs

Column 3 is A093367.

Row sums are A330620.

Cf. A087854, A208535, A327396, A330341.

Programs

PARI

\\ here U(n,k) is A208535(n,k) for n > 1.
U(n, k)={sumdiv(n, d, eulerphi(n/d)*(k-1)^d)/n - if(n%2, k-1)}
T(n,k)={sum(j=1, k, (-1)^(k-j)*binomial(k,j)*U(n,j))}

Formula

T(n,k) = Sum_{j=1..k} (-1)^(k-j)*binomial(k,j)*A208535(n,j) for n > 1.

T(n,n) = (n-1)! for n > 1.