login
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.
19

%I #41 Aug 20 2019 04:17:37

%S 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,

%T 0,18,258,1200,2400,2160,720,0,0,30,720,5100,15750,23940,17640,5040,0,

%U 0,56,2016,20720,92680,211680,258720,161280,40320

%N 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.

%C Turning over the necklaces is not allowed.

%C With other words: T(n,k) is the number of normal Lyndon words of length n and maximum k, where a finite sequence is normal if it spans an initial interval of positive integers. - _Gus Wiseman_, Dec 22 2017

%H Alois P. Heinz, <a href="/A254040/b254040.txt">Rows n = 0..140, flattened</a>

%F T(n,k) = Sum_{j=0..k} (-1)^j * C(k,j) * A074650(n,k-j).

%F T(n,k) = Sum_{d|n} mu(d) * A087854(n/d, k) for n >= 1 and 1 <= k <= n. - _Petros Hadjicostas_, Aug 20 2019

%e Triangle T(n,k) begins:

%e 1;

%e 0, 1;

%e 0, 0, 1;

%e 0, 0, 2, 2;

%e 0, 0, 3, 9, 6;

%e 0, 0, 6, 30, 48, 24;

%e 0, 0, 9, 89, 260, 300, 120;

%e 0, 0, 18, 258, 1200, 2400, 2160, 720;

%e 0, 0, 30, 720, 5100, 15750, 23940, 17640, 5040;

%e ...

%e 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

%p with(numtheory):

%p b:= proc(n, k) option remember; `if`(n=0, 1,

%p add(mobius(n/d)*k^d, d=divisors(n))/n)

%p end:

%p T:= (n, k)-> add(b(n, k-j)*binomial(k,j)*(-1)^j, j=0..k):

%p seq(seq(T(n, k), k=0..n), n=0..10);

%t 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_ *)

%t LyndonQ[q_]:=q==={}||Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];

%t 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&]];

%t Table[Length[Select[allnorm[n,k],LyndonQ]],{n,0,7},{k,0,n}] (* _Gus Wiseman_, Dec 22 2017 *)

%Y Columns k=0-10 give: A000007, A063524, A001037 (for n>1), A056288, A056289, A056290, A056291, A254079, A254080, A254081, A254082.

%Y Row sums give A060223.

%Y Main diagonal and lower diagonal give: A000142, A074143.

%Y T(2n,n) gives A254083.

%Y Cf. A074650, A087854.

%Y Cf. A000670, A000740, A008683, A019536, A059966, A185700, A296372, A296373, A296657.

%K nonn,tabl

%O 0,9

%A _Alois P. Heinz_, Jan 23 2015