cp's OEIS Frontend

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.

%I A254040 #41 Aug 20 2019 04:17:37
%S A254040 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 A254040 0,18,258,1200,2400,2160,720,0,0,30,720,5100,15750,23940,17640,5040,0,
%U A254040 0,56,2016,20720,92680,211680,258720,161280,40320
%N 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.
%C A254040 Turning over the necklaces is not allowed.
%C A254040 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 A254040 Alois P. Heinz, <a href="/A254040/b254040.txt">Rows n = 0..140, flattened</a>
%F A254040 T(n,k) = Sum_{j=0..k} (-1)^j * C(k,j) * A074650(n,k-j).
%F A254040 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 A254040 Triangle T(n,k) begins:
%e A254040   1;
%e A254040   0, 1;
%e A254040   0, 0,  1;
%e A254040   0, 0,  2,   2;
%e A254040   0, 0,  3,   9,    6;
%e A254040   0, 0,  6,  30,   48,    24;
%e A254040   0, 0,  9,  89,  260,   300,   120;
%e A254040   0, 0, 18, 258, 1200,  2400,  2160,   720;
%e A254040   0, 0, 30, 720, 5100, 15750, 23940, 17640, 5040;
%e A254040   ...
%e A254040 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 A254040 with(numtheory):
%p A254040 b:= proc(n, k) option remember; `if`(n=0, 1,
%p A254040       add(mobius(n/d)*k^d, d=divisors(n))/n)
%p A254040     end:
%p A254040 T:= (n, k)-> add(b(n, k-j)*binomial(k,j)*(-1)^j, j=0..k):
%p A254040 seq(seq(T(n, k), k=0..n), n=0..10);
%t A254040 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 A254040 LyndonQ[q_]:=q==={}||Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
%t A254040 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 A254040 Table[Length[Select[allnorm[n,k],LyndonQ]],{n,0,7},{k,0,n}] (* _Gus Wiseman_, Dec 22 2017 *)
%Y A254040 Columns k=0-10 give: A000007, A063524, A001037 (for n>1), A056288, A056289, A056290, A056291, A254079, A254080, A254081, A254082.
%Y A254040 Row sums give A060223.
%Y A254040 Main diagonal and lower diagonal give: A000142, A074143.
%Y A254040 T(2n,n) gives A254083.
%Y A254040 Cf. A074650, A087854.
%Y A254040 Cf. A000670, A000740, A008683, A019536, A059966, A185700, A296372, A296373, A296657.
%K A254040 nonn,tabl
%O A254040 0,9
%A A254040 _Alois P. Heinz_, Jan 23 2015