A060223 -id:A060223 - cp's OEIS frontend

A296372 Triangle read by rows: T(n,k) is the number of normal sequences of length n whose standard factorization into Lyndon words (aperiodic necklaces) has k factors.

1, 1, 2, 4, 5, 4, 18, 31, 18, 8, 108, 208, 153, 56, 16, 778, 1700, 1397, 616, 160, 32, 6756, 15980, 14668, 7197, 2196, 432, 64, 68220, 172326, 171976, 93293, 31564, 7208, 1120, 128

Offset: 1

Gus Wiseman, Dec 11 2017

A finite sequence is normal if its union is an initial interval of positive integers.

			The T(3,2) = 5 normal sequences are {2,1,2}, {1,2,1}, {2,1,3}, {2,3,1}, {3,1,2}.
Triangle begins:
     1;
     1,     2;
     4,     5,     4;
    18,    31,    18,     8;
   108,   208,   153,    56,    16;
   778,  1700,  1397,   616,   160,    32;
  6756, 15980, 14668,  7197,  2196,   432,    64;

Andrew Howroyd, Rows n = 1..50 of triangle, flattened
Wikipedia, Lyndon word: Standard factorization

Row sums are A000670.
First column is A060223.
Cf. A000740, A001045, A008965, A019536, A059966, A074650, A185700, A228369, A232472, A277427, A281013, A296373.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
aperQ[q_]:=UnsameQ@@Table[RotateRight[q,k],{k,Length[q]}];
qit[q_]:=If[#===Length[q],{q},Prepend[qit[Drop[q,#]],Take[q,#]]]&[Max@@Select[Range[Length[q]],neckQ[Take[q,#]]&&aperQ[Take[q,#]]&]];
allnorm[n_]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Length[Select[Join@@Permutations/@allnorm[n],Length[qit[#]]===k&]],{n,5},{k,n}]

\\ here U(n,k) is A074650(n,k).
EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
U(n,k)={sumdiv(n, d, moebius(n/d) * k^d)/n}
A(n)={[Vecrev(p/y) | p<-sum(k=1, n, EulerMT(vector(n, n, y*U(n,k)))*sum(j=k, n, (-1)^(k-j)*binomial(j,k)))]}
{ my(T=A(10)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Dec 08 2018

Example and program corrected by Gus Wiseman, Dec 08 2018

A329318 List of co-Lyndon words on {1,2} sorted first by length and then lexicographically.

Original entry on oeis.org

1, 2, 21, 211, 221, 2111, 2211, 2221, 21111, 21211, 22111, 22121, 22211, 22221, 211111, 212111, 221111, 221121, 221211, 222111, 222121, 222211, 222221, 2111111, 2112111, 2121111, 2121211, 2211111, 2211121, 2211211, 2212111, 2212121, 2212211, 2221111, 2221121

Offset: 1

Gus Wiseman, Nov 11 2019

nonn

The co-Lyndon product of two or more finite sequences is defined to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (231) and (213) is (212313), the product of (221) and (213) is (212213), and the product of (122) and (2121) is (1212122). A co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product. Equivalently, a co-Lyndon word is a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into co-Lyndon words, and if these factors are arranged in a certain order, their concatenation is equal to their co-Lyndon product. For example, (1001) has sorted co-Lyndon factorization (1)(100).

The non-"co" version is A102659.
Numbers whose binary expansion is co-Lyndon are A275692.
Length of the co-Lyndon factorization of the binary expansion is A329312.
Cf. A000031, A001037, A027375, A059966, A060223, A211100, A328596, A329324.

colynQ[q_]:=Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
Join@@Table[FromDigits/@Select[Tuples[{1,2},n],colynQ],{n,5}]

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.

Original entry on oeis.org

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

Offset: 0

Alois P. Heinz, Jan 23 2015

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

			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

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

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.

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);

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 *)

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

A211097 Number of factors in Lyndon factorization of binary vectors of lengths 1, 2, 3, ...

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 3, 1, 2, 1, 3, 2, 3, 3, 4, 1, 2, 1, 3, 2, 2, 1, 4, 2, 3, 2, 4, 3, 4, 4, 5, 1, 2, 1, 3, 1, 2, 1, 4, 2, 3, 1, 3, 2, 2, 1, 5, 2, 3, 2, 4, 3, 3, 2, 5, 3, 4, 3, 5, 4, 5, 5, 6, 1, 2, 1, 3, 1, 2, 1, 4, 2, 2, 1, 3, 1, 2, 1, 5, 2, 3, 2, 4, 3, 2, 1, 4, 2, 3, 2, 3, 2, 2, 1, 6, 2, 3, 2, 4, 2, 3, 2, 5, 3, 4, 2, 4, 3, 3, 2, 6, 3, 4, 3, 5, 4, 4, 3, 6, 4, 5

Offset: 1

N. J. A. Sloane, Apr 01 2012

nonn

Any binary word has a unique factorization as a product of nonincreasing Lyndon words (see Lothaire). Here we look at the Lyndon factorizations of the binary vectors 0,1, 00,01,10,11, 000,001,010,011,100,101,110,111, 0000,...
For the largest (or leftmost) factor see A211098, A211099.
The smallest (or rightmost) factors are given by A211095 and A211096, offset by 2.

			Here are the Lyndon factorizations of the first few binary vectors:
.0.
.1.
.0.0.
.01.
.1.0.
.1.1.
.0.0.0.
.001.
.01.0. <- this means that the factorization is (01)(0), for example
.011.
.1.0.0.
.1.01.
.1.1.0.
.1.1.1.
.0.0.0.0.
...

M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983. See Theorem 5.1.5, p. 67.
G. Melançon, Factorizing infinite words using Maple, MapleTech Journal, vol. 4, no. 1, 1997, pp. 34-42

N. J. A. Sloane, Table of n, a(n) for n = 1..10000
N. J. A. Sloane, Maple programs for A211097 etc.

A211098 and A211099 give information about the largest (or leftmost) factor.
Cf. A211095, A211096.
Row-lengths of A329325.
The "co" version is A329400.
Retaining the first digit gives A211100.
Binary Lyndon words are counted by A001037 and constructed by A102659.
Numbers whose reversed binary expansion is Lyndon are A328596.
Cf. A059966, A060223, A275692, A329312, A329313, A329314, A329326.

lynQ[q_]:=Array[Union[{q,RotateRight[q,#]}]=={q,RotateRight[q,#]}&,Length[q]-1,1,And];
lynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[lynfac[Drop[q,i]],Take[q,i]]][Last[Select[Range[Length[q]],lynQ[Take[q,#]]&]]]];
Table[Length[lynfac[Rest[IntegerDigits[n,2]]]],{n,2,50}] (* Gus Wiseman, Nov 14 2019 *)

A000939 Number of inequivalent n-gons.

Original entry on oeis.org

1, 1, 1, 2, 4, 14, 54, 332, 2246, 18264, 164950, 1664354, 18423144, 222406776, 2905943328, 40865005494, 615376173184, 9880209206458, 168483518571798, 3041127561315224, 57926238289970076, 1161157777643184900, 24434798429947993054, 538583682082245127336

Offset: 1

N. J. A. Sloane

Here two n-gons are said to be equivalent if they differ in starting point, orientation, or by a rotation (but not by a reflection - for that see A000940).

Number of cycle necklaces on n vertices, defined as equivalence classes of (labeled, undirected) Hamiltonian cycles under rotation of the vertices. The path version is A275527. - Gus Wiseman, Mar 02 2019

			Possibilities for n-gons without distinguished vertex can be encoded as permutation classes of vertices, two permutations being equivalent if they can be obtained from each other by circular rotation, translation mod n or complement to n+1.
n=3: 123.
n=4: 1234, 1243.
n=5: 12345, 12354, 12453, 13524.
n=6: 123456, 123465, 123564, 123645, 123654, 124365, 124635, 124653, 125364, 125463, 125634, 126435, 126453, 135264.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Georg Fischer, Table of n, a(n) for n = 1..450 (first 100 terms by T. D. Noe)
S. W. Golomb and L. R. Welch, On the enumeration of polygons, Amer. Math. Monthly, 67 (1960), 349-353.
S. W. Golomb and L. R. Welch, On the enumeration of polygons, Amer. Math. Monthly, 67 (1960), 349-353. [Annotated scanned copy]
Samuel Herman and Eirini Poimenidou, Orbits of Hamiltonian Paths and Cycles in Complete Graphs, arXiv:1905.04785 [math.CO], 2019.
A. Stoimenow, Enumeration of chord diagrams and an upper bound for Vassiliev invariants, J. Knot Theory Ramifications, 7 (1998), no. 1, 93-114.
Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
Wikipedia, Hamiltonian path.
Wikipedia, Polygon.
Gus Wiseman, Inequivalent representatives of the a(6) = 14 cycle necklaces.
Gus Wiseman, Inequivalent representatives of the a(7) = 54 n-gons.

Cf. A000940. Bisections give A094154, A094155.
For star polygons see A231091.
Cf. A000031, A002619, A002866, A006125, A008965, A059966, A060223, A192332, A275527, A323858, A323870, A324461.

with(numtheory):
# for n odd:
Ed:= proc(n) local t1, d; t1:=0; for d from 1 to n do
       if n mod d = 0 then t1:= t1+phi(n/d)^2*d!*(n/d)^d fi od:
       t1/(2*n^2)
     end:
# for n even:
Ee:= proc(n) local t1, d; t1:= 2^(n/2)*(n/2)*(n/2)!; for d
       from 1 to n do if n mod d = 0 then t1:= t1+
       phi(n/d)^2*d!*(n/d)^d; fi od: t1/(2*n^2)
     end:
A000939:= n-> if n mod 2 = 0 then ceil(Ee(n)) else ceil(Ed(n)); fi:
seq(A000939(n), n=1..25);

a[n_] := (t = If[OddQ[n], 0, 2^(n/2)*(n/2)*(n/2)!]; Do[If[Mod[n, d]==0, t = t+EulerPhi[n/d]^2*d!*(n/d)^d], {d, 1, n}]; t/(2*n^2)); a[1] := 1; a[2] := 1; Print[a /@ Range[1, 450]] (* Jean-François Alcover, May 19 2011, after Maple prog. *)
rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
Table[Length[Select[Union[Sort[Sort/@Partition[#,2,1,1]]&/@Permutations[Range[n]]],#==First[Sort[Table[Nest[rotgra[#,n]&,#,j],{j,n}]]]&]],{n,8}] (* Gus Wiseman, Mar 02 2019 *)

a(n)={if(n<3, n>=0, (if(n%2, 0, (n/2-1)!*2^(n/2-2)) + sumdiv(n, d, eulerphi(n/d)^2 * d! * (n/d)^d)/n^2)/2)} \\ Andrew Howroyd, Aug 17 2019

For formula see Maple lines.
a(2*n + 1) =  A002619(2*n + 1)/2 for n > 0; a(2*n) = (A002619(2*n) + A002866(n-1))/2 for n > 1. - Andrew Howroyd, Aug 17 2019
a(n) ~ sqrt(2*Pi)/2 * n^(n-3/2) / e^n. - Ludovic Schwob, Nov 03 2022

More terms from Pab Ter (pabrlos(AT)yahoo.com), May 05 2004

Added a(1) = 1 and a(2) = 1 by Gus Wiseman, Mar 02 2019

A329395 Numbers whose binary expansion without the most significant (first) digit has Lyndon and co-Lyndon factorizations of equal lengths.

Original entry on oeis.org

1, 2, 3, 4, 7, 8, 10, 13, 15, 16, 22, 25, 31, 32, 36, 42, 46, 49, 53, 59, 63, 64, 76, 82, 94, 97, 109, 115, 127, 128, 136, 148, 156, 162, 166, 169, 170, 172, 181, 182, 190, 193, 201, 202, 211, 213, 214, 217, 221, 227, 235, 247, 255, 256, 280, 292, 306, 308

Offset: 1

Gus Wiseman, Nov 13 2019

nonn

We define the Lyndon product of two or more finite sequences to be the lexicographically maximal sequence obtainable by shuffling the sequences together. For example, the Lyndon product of (231) with (213) is (232131), the product of (221) with (213) is (222131), and the product of (122) with (2121) is (2122121). A Lyndon word is a finite sequence that is prime with respect to the Lyndon product. Equivalently, a Lyndon word is a finite sequence that is lexicographically strictly less than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into Lyndon words, and if these factors are arranged in lexicographically decreasing order, their concatenation is equal to their Lyndon product. For example, (1001) has sorted Lyndon factorization (001)(1).
Similarly, the co-Lyndon product is the lexicographically minimal sequence obtainable by shuffling the sequences together, and a co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product, or, equivalently, a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. For example, (1001) has sorted co-Lyndon factorization (1)(100).
Conjecture: also numbers k such that the k-th composition in standard order (A066099) is a palindrome, cf. A025065, A242414, A317085, A317086, A317087, A335373. - Gus Wiseman, Jun 06 2020

			The sequence of terms together with their trimmed binary expansions and their co-Lyndon and Lyndon factorizations begins:
   1:      () =               0 = 0
   2:     (0) =             (0) = (0)
   3:     (1) =             (1) = (1)
   4:    (00) =          (0)(0) = (0)(0)
   7:    (11) =          (1)(1) = (1)(1)
   8:   (000) =       (0)(0)(0) = (0)(0)(0)
  10:   (010) =         (0)(10) = (01)(0)
  13:   (101) =         (10)(1) = (1)(01)
  15:   (111) =       (1)(1)(1) = (1)(1)(1)
  16:  (0000) =    (0)(0)(0)(0) = (0)(0)(0)(0)
  22:  (0110) =        (0)(110) = (011)(0)
  25:  (1001) =        (100)(1) = (1)(001)
  31:  (1111) =    (1)(1)(1)(1) = (1)(1)(1)(1)
  32: (00000) = (0)(0)(0)(0)(0) = (0)(0)(0)(0)(0)
  36: (00100) =     (0)(0)(100) = (001)(0)(0)
  42: (01010) =     (0)(10)(10) = (01)(01)(0)
  46: (01110) =       (0)(1110) = (0111)(0)
  49: (10001) =       (1000)(1) = (1)(0001)
  53: (10101) =     (10)(10)(1) = (1)(01)(01)
  59: (11011) =     (110)(1)(1) = (1)(1)(011)
  63: (11111) = (1)(1)(1)(1)(1) = (1)(1)(1)(1)(1)

Lyndon and co-Lyndon compositions are (both) counted by A059966.
Numbers whose reversed binary expansion is Lyndon are A328596.
Numbers whose binary expansion is co-Lyndon are A275692.
Cf. A001037, A060223, A102659, A211100, A329131, A329312, A329313, A329318, A329326, A329394, A329398.
Cf. A329358, A329399, A329400, A329401.

lynQ[q_]:=Array[Union[{q, RotateRight[q, #]}]=={q, RotateRight[q, #]}&, Length[q]-1, 1, And];
lynfac[q_]:=If[Length[q]==0, {}, Function[i, Prepend[lynfac[Drop[q, i]], Take[q, i]]][Last[Select[Range[Length[q]], lynQ[Take[q, #]]&]]]];
colynQ[q_]:=Array[Union[{RotateRight[q, #], q}]=={RotateRight[q, #], q}&, Length[q]-1, 1, And];
colynfac[q_]:=If[Length[q]==0, {}, Function[i, Prepend[colynfac[Drop[q, i]], Take[q, i]]]@Last[Select[Range[Length[q]], colynQ[Take[q, #]]&]]];
Select[Range[100],Length[lynfac[Rest[IntegerDigits[#,2]]]]==Length[colynfac[Rest[IntegerDigits[#,2]]]]&]

A061417 Number of permutations up to cyclic rotations; permutation siteswap necklaces.

Original entry on oeis.org

1, 2, 4, 10, 28, 136, 726, 5100, 40362, 363288, 3628810, 39921044, 479001612, 6227066928, 87178295296, 1307675013928, 20922789888016, 355687438476444, 6402373705728018, 121645100594641896, 2432902008177690360, 51090942175425331320, 1124000727777607680022

Offset: 1

Antti Karttunen, May 02 2001

If permutations are converted to (i,p(i)) permutation arrays, then this automorphism is obtained by their "SW-NE diagonal toroidal shifts" (see Matthias Engelhardt's Java program in A006841), while the Maple procedure below converts each permutation to a siteswap pattern (used in juggling), rotates it by one digit and converts the resulting new (or same) siteswap pattern back to a permutation.
When the subset of permutations listed by A064640 are subjected to the same automorphism one gets A002995.
The number of conjugacy classes of the symmetric group of degree n when conjugating only with the cyclic permutation group of degree n. - Attila Egri-Nagy, Aug 15 2014
Also the number of equivalence classes of permutations of {1...n} under the action of rotation of vertices in the cycle decomposition. The corresponding action on words applies m -> m + 1 for m < n and n -> 1, and rotates once to the right. For example, (24531) first becomes (35142) under the application of cyclic rotation, and then is rotated right to give (23514). - Gus Wiseman, Mar 04 2019

			If I have a five-element permutation like 25431, in cycle notation (1 2 5)(3 4), I mark the numbers 1-5 clockwise onto a circle and draw directed edges from 1 to 2, from 2 to 5, from 5 to 1 and a double-way edge between 3 and 4. All the 5-element permutations that produce some rotation (discarding the labels of the nodes) of that chord diagram belong to the same equivalence class with 25431. The sequence gives the count of such equivalence classes.

Cf. A006841, A060495. For other Maple procedures, see A060501 (Perm2SiteSwap2), A057502 (CountCycles), A057509 (rotateL), A060125 (PermRank3R and permul).
A061417[p] = A061860[p] = (p-1)!+(p-1) for all prime p's.
A064636 (derangements-the same automorphism).
A061417[n] = A064649[n]/n.
Cf. A000031, A000939, A002995, A008965, A060223, A064640, A086675 (digraphical necklaces), A179043, A192332, A275527 (path necklaces), A323858, A323859, A323870, A324513, A324514 (aperiodic permutations).

List([1..10],n->Size( OrbitsDomain( CyclicGroup(IsPermGroup,n), SymmetricGroup( IsPermGroup,n),\^))); # Attila Egri-Nagy, Aug 15 2014

a061417 = sum . a047917_row  -- Reinhard Zumkeller, Mar 19 2014

Algebraic formula: with(numtheory); SSRPCC := proc(n) local d,s; s := 0; for d in divisors(n) do s := s + phi(n/d)*((n/d)^d)*(d!); od; RETURN(s/n); end;
Empirically: with(group); SiteSwapRotationPermutationCycleCounts := proc(upto_n) local b,u,n,a,r; a := []; for n from 1 to upto_n do b := []; u := n!; for r from 0 to u-1 do b := [op(b),1+PermRank3R(SiteSwap2Perm1(rotateL(Perm2SiteSwap2(PermUnrank3Rfix(n,r)))))]; od; a := [op(a),CountCycles(b)]; od; RETURN(a); end;
PermUnrank3Rfixaux := proc(n,r,p) local s; if(0 = n) then RETURN(p); else s := floor(r/((n-1)!)); RETURN(PermUnrank3Rfixaux(n-1, r-(s*((n-1)!)), permul(p,[[n,n-s]]))); fi; end;
PermUnrank3Rfix := (n,r) -> convert(PermUnrank3Rfixaux(n,r,[]),'permlist',n);
SiteSwap2Perm1 := proc(s) local e,n,i,a; n := nops(s); a := []; for i from 1 to n do e := ((i+s[i]) mod n); if(0 = e) then e := n; fi; a := [op(a),e]; od; RETURN(convert(invperm(convert(a,'disjcyc')),'permlist',n)); end;

a[n_] := (1/n)*Sum[ EulerPhi[n/d]*(n/d)^d*d!, {d, Divisors[n]}]; Table[a[n], {n, 1, 21}] (* Jean-François Alcover, Oct 09 2012, from formula *)
Table[Length[Select[Permutations[Range[n]],#==First[Sort[NestList[RotateRight[#/.k_Integer:>If[k==n,1,k+1]]&,#,n-1]]]&]],{n,8}] (* Gus Wiseman, Mar 04 2019 *)

a(n) = (1/n)*sumdiv(n, d, eulerphi(n/d)*(n/d)^d*d!); \\ Indranil Ghosh, Apr 10 2017

from sympy import divisors, factorial, totient
def a(n):
    return sum(totient(n//d)*(n//d)**d*factorial(d) for d in divisors(n))//n
print([a(n) for n in range(1, 22)]) # Indranil Ghosh, Apr 10 2017

a(n) = (1/n)*Sum_{d|n} phi(n/d)*((n/d)^d)*(d!).

A192332 For n >= 3, draw a regular n-sided polygon and its n(n-3)/2 diagonals, so there are n(n-1)/2 lines; a(n) is the number of ways to choose a subset of these lines (subsets differing by a rotation are regarded as identical). a(1)=1, a(2)=2 by convention.

Original entry on oeis.org

1, 2, 4, 22, 208, 5560, 299600, 33562696, 7635498336, 3518440564544, 3275345183542208, 6148914696963883712, 23248573454127484129024, 176848577040808821410837120, 2704321280486889389864215362560, 83076749736557243209409446411255936, 5124252113632955685095523500148980125696, 634332307869315502692705867068871886072665600

Offset: 1

N. J. A. Sloane, Jun 28 2011

nonn

Suggested by A192314.

Also the number of graphical necklaces with n vertices. We define a graphical necklace to be a simple graph that is minimal among all n rotations of the vertices. Alternatively, it is an equivalence class of simple graphs under rotation of the vertices. These are a kind of partially labeled graphs. - Gus Wiseman, Mar 04 2019

			From _Gus Wiseman_, Mar 04 2019: (Start)
Inequivalent representatives of the a(1) = 1 through a(4) = 22 graphical necklace edge-sets:
  {}  {}      {}              {}
      {{12}}  {{12}}          {{12}}
              {{12}{13}}      {{13}}
              {{12}{13}{23}}  {{12}{13}}
                              {{12}{14}}
                              {{12}{24}}
                              {{12}{34}}
                              {{13}{24}}
                              {{12}{13}{14}}
                              {{12}{13}{23}}
                              {{12}{13}{24}}
                              {{12}{13}{34}}
                              {{12}{14}{23}}
                              {{12}{24}{34}}
                              {{12}{13}{14}{23}}
                              {{12}{13}{14}{24}}
                              {{12}{13}{14}{34}}
                              {{12}{13}{24}{34}}
                              {{12}{14}{23}{34}}
                              {{12}{13}{14}{23}{24}}
                              {{12}{13}{14}{23}{34}}
                              {{12}{13}{14}{23}{24}{34}}
(End)

Vincenzo Librandi, Table of n, a(n) for n = 1..80
Gus Wiseman, Inequivalent representatives of the a(5) = 22 graphical necklaces.
Gus Wiseman, Inequivalent representatives of the a(5) = 208 graphical necklaces.

Cf. A192314, A191563 (orbits under dihedral group).

Cf. A000031, A000939 (cycle necklaces), A008965, A059966, A060223, A061417, A086675 (digraph version), A184271, A275527, A323858, A324461, A324463, A324464.

with(numtheory);
f:=proc(n) local t0, t1, d; t0:=0; t1:=divisors(n);
for d in t1 do
if d mod 2 = 0 then t0:=t0+phi(d)*2^(n^2/(2*d))
else t0:=t0+phi(d)*2^(n*(n-1)/(2*d)); fi; od; t0/n; end;
[seq(f(n), n=1..30)];

Table[ 1/n* Plus @@ Map[Function[d, EulerPhi[d]*2^((n*(n - Mod[d, 2])/2)/d)], Divisors[n]], {n, 1, 20}]  (* Olivier Gérard, Aug 27 2011 *)
rotgra[g_,m_]:=Sort[Sort/@(g/.k_Integer:>If[k==m,1,k+1])];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],#=={}||#==First[Sort[Table[Nest[rotgra[#,n]&,#,j],{j,n}]]]&]],{n,0,5}] (* Gus Wiseman, Mar 04 2019 *)

a(n) = sumdiv(n, d, if (d%2, eulerphi(d)*2^(n*(n-1)/(2*d)), eulerphi(d)*2^(n^2/(2*d))))/n; \\ Michel Marcus, Mar 08 2019

a(n) = (1/n)*(Sum_{d|n, d odd} phi(d)*2^(n*(n-1)/(2*d)) + Sum_{d|n, d even} phi(d)*2^(n^2/(2*d))).

A281013 Tetrangle T(n,k,i) = i-th part of k-th prime composition of n.

Original entry on oeis.org

1, 2, 2, 1, 3, 2, 1, 1, 3, 1, 4, 2, 1, 1, 1, 2, 2, 1, 3, 1, 1, 3, 2, 4, 1, 5, 2, 1, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 1, 3, 1, 2, 3, 2, 1, 4, 1, 1, 4, 2, 5, 1, 6, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 1, 3, 1, 1, 1, 1, 3, 1, 1, 2, 3, 1, 2, 1, 3, 2, 1, 1, 3, 2, 2, 3, 3, 1, 4, 1, 1, 1, 4, 1, 2, 4, 2, 1, 4, 3, 5, 1, 1, 5, 2, 6, 1, 7

Offset: 1

Gus Wiseman, Jan 12 2017

The *-product of two or more finite sequences is defined to be the lexicographically minimal sequence obtainable by shuffling them together. Every finite positive integer sequence has a unique *-factorization using prime compositions P = {(1), (2), (21), (3), (211), ...}. See A060223 and A228369 for details.

These are co-Lyndon compositions, ordered first by sum and then lexicographically. - Gus Wiseman, Nov 15 2019

			The prime factorization of (1, 1, 4, 2, 3, 1, 5, 5) is: (11423155) = (1)*(1)*(5)*(5)*(4231). The prime factorizations of the initial terms of A000002 are:
             (1) = (1)
            (12) = (1)*(2)
           (122) = (1)*(2)*(2)
          (1221) = (1)*(221)
         (12211) = (1)*(2211)
        (122112) = (1)*(2)*(2211)
       (1221121) = (1)*(221121)
      (12211212) = (1)*(2)*(221121)
     (122112122) = (1)*(2)*(2)*(221121)
    (1221121221) = (1)*(221)*(221121)
   (12211212212) = (1)*(2)*(221)*(221121)
  (122112122122) = (1)*(2)*(2)*(221)*(221121).
Read as a sequence:
(1), (2), (21), (3), (211), (31), (4), (2111), (221), (311), (32), (41), (5).
Read as a triangle:
(1)
(2)
(21), (3)
(211), (31), (4)
(2111), (221), (311), (32), (41), (5).
Read as a sequence of triangles:
1    2    2 1    2 1 1    2 1 1 1    2 1 1 1 1    2 1 1 1 1 1
          3      3 1      2 2 1      2 2 1 1      2 1 2 1 1
                 4        3 1 1      3 1 1 1      2 2 1 1 1
                          3 2        3 1 2        2 2 2 1
                          4 1        3 2 1        3 1 1 1 1
                          5          4 1 1        3 1 1 2
                                     4 2          3 1 2 1
                                     5 1          3 2 1 1
                                     6            3 2 2
                                                  3 3 1
                                                  4 1 1 1
                                                  4 1 2
                                                  4 2 1
                                                  4 3
                                                  5 1 1
                                                  5 2
                                                  6 1
                                                  7.

Cf. A000740, A215474, A228369, A277427.
The binary version is A329318.
The binary non-"co" version is A102659.
A sequence listing all Lyndon compositions is A294859.
Numbers whose binary expansion is co-Lyndon are A328596.
Numbers whose binary expansion is co-Lyndon are A275692.
Binary Lyndon words are A001037.
Lyndon compositions are A059966.
Normal Lyndon words are A060223.
Cf. A211097, A211100, A296372, A296373, A298941, A329131, A329312, A329313, A329314, A329324, A329326.

colynQ[q_]:=Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
lexsort[f_,c_]:=OrderedQ[PadRight[{f,c}]];
Table[Sort[Select[Join@@Permutations/@IntegerPartitions[n],colynQ],lexsort],{n,5}] (* Gus Wiseman, Nov 15 2019 *)

Row lengths are A059966(n) = number of prime compositions of n.

A296373 Triangle T(n,k) = number of compositions of n whose factorization into Lyndon words (aperiodic necklaces) is of length k.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 6, 5, 3, 1, 1, 9, 12, 6, 3, 1, 1, 18, 21, 14, 6, 3, 1, 1, 30, 45, 27, 15, 6, 3, 1, 1, 56, 84, 61, 29, 15, 6, 3, 1, 1, 99, 170, 120, 67, 30, 15, 6, 3, 1, 1, 186, 323, 254, 136, 69, 30, 15, 6, 3, 1, 1, 335, 640, 510, 295, 142, 70, 30, 15, 6, 3, 1, 1

Offset: 1

Gus Wiseman, Dec 11 2017

			Triangle begins:
    1;
    1,   1;
    2,   1,   1;
    3,   3,   1,   1;
    6,   5,   3,   1,   1;
    9,  12,   6,   3,   1,   1;
   18,  21,  14,   6,   3,   1,   1;
   30,  45,  27,  15,   6,   3,   1,   1;
   56,  84,  61,  29,  15,   6,   3,   1,   1;
   99, 170, 120,  67,  30,  15,   6,   3,   1,   1;
  186, 323, 254, 136,  69,  30,  15,   6,   3,   1,   1;
  335, 640, 510, 295, 142,  70,  30,  15,   6,   3,   1,   1;

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Wikipedia, Lyndon word: Standard factorization

Cf. A000740, A001045, A008965, A019536, A059966, A060223, A185700, A228369, A232472, A277427, A281013, A296302, A296372.

neckQ[q_]:=Array[OrderedQ[{RotateRight[q,#],q}]&,Length[q]-1,1,And];
aperQ[q_]:=UnsameQ@@Table[RotateRight[q,k],{k,Length[q]}];
qit[q_]:=If[#===Length[q],{q},Prepend[qit[Drop[q,#]],Take[q,#]]]&[Max@@Select[Range[Length[q]],neckQ[Take[q,#]]&&aperQ[Take[q,#]]&]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[qit[#]]===k&]],{n,12},{k,n}]

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
A(n)=[Vecrev(p/y) | p<-EulerMT(y*vector(n, n, sumdiv(n, d, moebius(n/d) * (2^d-1))/n))]
{ my(T=A(12)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Dec 01 2018

First column is A059966.

cp's OEIS Frontend

A296372 Triangle read by rows: T(n,k) is the number of normal sequences of length n whose standard factorization into Lyndon words (aperiodic necklaces) has k factors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A329318 List of co-Lyndon words on {1,2} sorted first by length and then lexicographically.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A211097 Number of factors in Lyndon factorization of binary vectors of lengths 1, 2, 3, ...

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A000939 Number of inequivalent n-gons.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A329395 Numbers whose binary expansion without the most significant (first) digit has Lyndon and co-Lyndon factorizations of equal lengths.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A061417 Number of permutations up to cyclic rotations; permutation siteswap necklaces.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Haskell

Maple