A087854 Triangle read by rows: T(n,k) is the number of n-bead necklaces with exactly k different colored beads.

1, 1, 1, 1, 2, 2, 1, 4, 9, 6, 1, 6, 30, 48, 24, 1, 12, 91, 260, 300, 120, 1, 18, 258, 1200, 2400, 2160, 720, 1, 34, 729, 5106, 15750, 23940, 17640, 5040, 1, 58, 2018, 20720, 92680, 211680, 258720, 161280, 40320, 1, 106, 5613, 81876, 510312, 1643544, 2963520, 3024000, 1632960, 362880

Offset

1,5

Comments

Equivalently, T(n,k) is the number of sequences (words) of length n on an alphabet of k letters where each letter of the alphabet occurs at least once in the sequence. Two sequences are considered equivalent if one can be obtained from the other by a cyclic shift of the letters. Cf. A054631 where the surjective restriction is removed. - Geoffrey Critzer, Jun 18 2013

Robert A. Russell's g.f. for column k >= 1 (in the Formula section below) can be proved by integrating both sides of the formula Sum_{n>=1} S2(n, k)*x^(n-1) = x^(k-1)/((1 - x)* (1 - 2*x) * (1 - 3*x) * ... * (1 - k*x)) w.r.t. x. A variation of this identity (valid for |x| < 1/k) can be found in the Formula section of A008277. - Petros Hadjicostas, Aug 20 2019

Links

Alois P. Heinz, Rows n = 1..141, flattened

Formula

T(n,k) = Sum_{i=0..k-1} (-1)^i * C(k,i) * A075195(n,k-i); A075195 = Jablonski's table.

T(n,k) = (k!/n) * Sum_{d|n} phi(d) * S2(n/d, k), where S2(n,k) = Stirling numbers of 2nd kind A008277.

G.f. for column k: -Sum_{d>0} (phi(d)/d) * Sum_{j = 1..k} (-1)^(k-j) * C(k,j) * log(1 - j * x^d). - Robert A. Russell, Sep 26 2018

T(n,k) = Sum_{d|n} A254040(d, k) for n, k >= 1. - Petros Hadjicostas, Aug 19 2019

Example

The triangle begins with T(1,1):
  1;
  1,   1;
  1,   2,    2;
  1,   4,    9,     6;
  1,   6,   30,    48,     24;
  1,  12,   91,   260,    300,     120;
  1,  18,  258,  1200,   2400,    2160,     720;
  1,  34,  729,  5106,  15750,   23940,   17640,    5040;
  1,  58, 2018, 20720,  92680,  211680,  258720,  161280,   40320;
  1, 106, 5613, 81876, 510312, 1643544, 2963520, 3024000, 1632960, 362880;
  ...
For T(4,2) = 4, the necklaces are AAAB, AABB, ABAB, and ABBB.
For T(4,4) = 6, the necklaces are ABCD, ABDC, ACBD, ACDB, ADBC, and ADCB.

Maple

with(numtheory):
T:= (n, k)-> (k!/n) *add(phi(d) *Stirling2(n/d, k), d=divisors(n)):
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Jun 19 2013

Mathematica

Table[Table[Sum[EulerPhi[d]*StirlingS2[n/d, k]k!, {d, Divisors[n]}]/n, {k, 1, n}], {n, 1, 10}]//Grid (* Geoffrey Critzer, Jun 18 2013 *)

Prog

(PARI) T(n, k) = (k!/n) * sumdiv(n, d, eulerphi(d) * stirling(n/d, k, 2)); \\ Joerg Arndt, Sep 25 2020

Crossrefs

Columns 1-6: A057427, A052823, A056283, A056284, A056285, A056286.

Diagonals: A000142 and A074143.

Row sums: A019536.

Cf. A000010 (Euler totient phi function), A008277 (Stirling2 numbers), A075195 (table of Jablonski).

Cf. A254040, A273891.

Sequence in context: A137399 A158985 A295687 * A185041 A086873 A101560

Adjacent sequences: A087851 A087852 A087853 * A087855 A087856 A087857

Keyword

nonn,tabl,easy

Author

Philippe Deléham

Extensions

Formula section edited by Petros Hadjicostas, Aug 20 2019

Status

approved