A254040 - OEIS

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

(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

Alois P. Heinz, Rows n = 0..140, flattened

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

EXAMPLE

Triangle T(n,k) begins:

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.

Row sums give A060223.

Main diagonal and lower diagonal give: A000142, A074143.

T(2n,n) gives A254083.

Cf. A074650, A087854.

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

Sequence in context: A329331 A370049 A355664 * A376725 A062275 A138270

Adjacent sequences: A254037 A254038 A254039 * A254041 A254042 A254043

KEYWORD

nonn,tabl

AUTHOR

_Alois P. Heinz_, Jan 23 2015

STATUS

approved