A327396 Triangle read by rows: T(n,k) is the number of n-bead necklace structures with beads of exactly k colors and no adjacent beads having the same color.

0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 3, 5, 2, 1, 0, 0, 3, 10, 8, 2, 1, 0, 1, 7, 33, 40, 18, 3, 1, 0, 0, 11, 83, 157, 104, 28, 3, 1, 0, 1, 19, 237, 650, 615, 246, 46, 4, 1, 0, 0, 31, 640, 2522, 3318, 1857, 495, 65, 4, 1, 0, 1, 63, 1817, 9888, 17594, 13311, 4911, 944, 97, 5, 1

Offset: 1

Author

Andrew Howroyd, Oct 04 2019

Keywords

• nonn
• tabl

Comments

Permuting the colors does not change the necklace structure.

Equivalently, the number of k-block partitions of an n-set up to rotations where no block contains cyclically adjacent elements of the n-set.

Examples

			Triangle begins:
  0;
  0, 1;
  0, 0,  1;
  0, 1,  1,    1;
  0, 0,  1,    1,    1;
  0, 1,  3,    5,    2,     1;
  0, 0,  3,   10,    8,     2,     1;
  0, 1,  7,   33,   40,    18,     3,    1;
  0, 0, 11,   83,  157,   104,    28,    3,   1;
  0, 1, 19,  237,  650,   615,   246,   46,   4,  1;
  0, 0, 31,  640, 2522,  3318,  1857,  495,  65,  4, 1;
  0, 1, 63, 1817, 9888, 17594, 13311, 4911, 944, 97, 5, 1;
  ...
		

Links

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

Crossrefs

Columns k=3..4 are A327397, A328130.

Partial row sums include A306888, A309673.

Row sums are A328150.

Cf. A152175, A261139, A208535.

Programs

PARI

R(n) = {Mat(Col([Vecrev(p/y, n) | p<-Vec(intformal(sum(m=1, n, eulerphi(m) * subst(serlaplace((y-1)*exp(-x + O(x*x^(n\m))) - y + exp(-x + sumdiv(m, d, y^d*(exp(d*x + O(x*x^(n\m)))-1)/d)) ), x, x^m))/x), -n)]))}
{ my(A=R(12)); for(n=1, #A, print(A[n, 1..n])) } \\ Andrew Howroyd, Oct 09 2019