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

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.

Links

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

Example

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

Prog

(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

Crossrefs

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

Partial row sums include A306888, A309673.

Row sums are A328150.

Cf. A152175, A261139, A208535.

Sequence in context: A327693 A240752 A342277 * A021288 A140735 A183206

Adjacent sequences: A327393 A327394 A327395 * A327397 A327398 A327399

Keyword

nonn,tabl

Author

Andrew Howroyd, Oct 04 2019

Status

approved