|
|
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.
|
|
19
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,9
|
|
COMMENTS
|
Turning over the necklaces is not allowed.
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
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = Sum_{j=0..k} (-1)^j * C(k,j) * A074650(n,k-j).
|
|
EXAMPLE
|
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
|
|
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 *)
|
|
CROSSREFS
|
Columns k=0-10 give: A000007, A063524, A001037 (for n>1), A056288, A056289, A056290, A056291, A254079, A254080, A254081, A254082.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|