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

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.

Links

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

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.

Example

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

Prog

(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))}

Crossrefs

Column 3 is A093367.

Row sums are A330620.

Cf. A087854, A208535, A327396, A330341.

Sequence in context: A254281 A295682 A195772 * A062104 A257783 A226874

Adjacent sequences: A330615 A330616 A330617 * A330619 A330620 A330621

Keyword

nonn,tabl

Author

Andrew Howroyd, Dec 20 2019

Status

approved