A254040 Number T(n,k) of primitive (= aperiodic) n-bead necklaces with colored beads of exactly k different colors; triangle T(n,k), n >= 0, 0 <= k <= n, read by rows.
1, 0, 1, 0, 0, 1, 0, 0, 2, 2, 0, 0, 3, 9, 6, 0, 0, 6, 30, 48, 24, 0, 0, 9, 89, 260, 300, 120, 0, 0, 18, 258, 1200, 2400, 2160, 720, 0, 0, 30, 720, 5100, 15750, 23940, 17640, 5040, 0, 0, 56, 2016, 20720, 92680, 211680, 258720, 161280, 40320
Offset: 0
Examples
Triangle T(n,k) begins: 1; 0, 1; 0, 0, 1; 0, 0, 2, 2; 0, 0, 3, 9, 6; 0, 0, 6, 30, 48, 24; 0, 0, 9, 89, 260, 300, 120; 0, 0, 18, 258, 1200, 2400, 2160, 720; 0, 0, 30, 720, 5100, 15750, 23940, 17640, 5040; ... The T(4,3) = 9 normal Lyndon words of length 4 with maximum 3 are: 1233, 1323, 1332, 1223, 1232, 1322, 1123, 1132, 1213. - _Gus Wiseman_, Dec 22 2017
Links
- Alois P. Heinz, Rows n = 0..140, flattened
Crossrefs
Programs
-
Maple
with(numtheory): b:= proc(n, k) option remember; `if`(n=0, 1, add(mobius(n/d)*k^d, d=divisors(n))/n) end: T:= (n, k)-> add(b(n, k-j)*binomial(k,j)*(-1)^j, j=0..k): seq(seq(T(n, k), k=0..n), n=0..10); -
Mathematica
b[n_, k_] := b[n, k] = If[n == 0, 1, Sum[MoebiusMu[n/d]*k^d, {d, Divisors[n]}]/n]; T[n_, k_] := Sum[b[n, k-j]*Binomial[k, j]*(-1)^j, {j, 0, k}]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 10}] // Flatten (* Jean-François Alcover, Jan 27 2015, after Alois P. Heinz *) LyndonQ[q_]:=q==={}||Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ]; allnorm[n_,k_]:=If[k===0,If[n===0,{{}}, {}],Join@@Permutations/@Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Select[Subsets[Range[n-1]+1],Length[#]===k-1&]]; Table[Length[Select[allnorm[n,k],LyndonQ]],{n,0,7},{k,0,n}] (* Gus Wiseman, Dec 22 2017 *)
Formula
T(n,k) = Sum_{j=0..k} (-1)^j * C(k,j) * A074650(n,k-j).
T(n,k) = Sum_{d|n} mu(d) * A087854(n/d, k) for n >= 1 and 1 <= k <= n. - Petros Hadjicostas, Aug 20 2019
Comments