login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 18
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).

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, 2-10 give: A000007, 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, A019536, A059966, A185700, A296372, A296373, A296657.

Sequence in context: A228250 A101164 A229079 * A062275 A138270 A317643

Adjacent sequences:  A254037 A254038 A254039 * A254041 A254042 A254043

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Jan 23 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 17 06:35 EST 2018. Contains 317275 sequences. (Running on oeis4.)