A059966 -id:A059966 - 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.

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

A333943 Numbers k such that the k-th composition in standard order is a reversed necklace.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 15, 16, 17, 18, 19, 21, 23, 31, 32, 33, 34, 35, 36, 37, 39, 41, 42, 43, 45, 47, 63, 64, 65, 66, 67, 68, 69, 71, 73, 74, 75, 77, 79, 81, 83, 85, 87, 91, 95, 127, 128, 129, 130, 131, 132, 133, 135, 136, 137, 138, 139, 141, 143

Offset: 1

Gus Wiseman, Apr 14 2020

nonn

A necklace is a finite sequence that is lexicographically minimal among all of its cyclic rotations. Reversed necklaces are different from co-necklaces (A333764).

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The sequence together with the corresponding reversed necklaces begins:
    1: (1)             32: (6)               69: (4,2,1)
    2: (2)             33: (5,1)             71: (4,1,1,1)
    3: (1,1)           34: (4,2)             73: (3,3,1)
    4: (3)             35: (4,1,1)           74: (3,2,2)
    5: (2,1)           36: (3,3)             75: (3,2,1,1)
    7: (1,1,1)         37: (3,2,1)           77: (3,1,2,1)
    8: (4)             39: (3,1,1,1)         79: (3,1,1,1,1)
    9: (3,1)           41: (2,3,1)           81: (2,4,1)
   10: (2,2)           42: (2,2,2)           83: (2,3,1,1)
   11: (2,1,1)         43: (2,2,1,1)         85: (2,2,2,1)
   15: (1,1,1,1)       45: (2,1,2,1)         87: (2,2,1,1,1)
   16: (5)             47: (2,1,1,1,1)       91: (2,1,2,1,1)
   17: (4,1)           63: (1,1,1,1,1,1)     95: (2,1,1,1,1,1)
   18: (3,2)           64: (7)              127: (1,1,1,1,1,1,1)
   19: (3,1,1)         65: (6,1)            128: (8)
   21: (2,2,1)         66: (5,2)            129: (7,1)
   23: (2,1,1,1)       67: (5,1,1)          130: (6,2)
   31: (1,1,1,1,1)     68: (4,3)            131: (6,1,1)

The non-reversed version is A065609.
The dual version is A328595.
Binary necklaces are A000031.
Necklace compositions are A008965.
Necklaces covering an initial interval are A019536.
Numbers whose prime signature is a necklace are A329138.
Length of co-Lyndon factorization of binary expansion is A329312.
Length of Lyndon factorization of reversed binary expansion is A329313.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Sum is A070939.
- Runs are counted by A124767.
- Rotational symmetries are counted by A138904.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon compositions are A275692.
- Co-Lyndon compositions are A326774.
- Aperiodic compositions are A328594.
- Length of Lyndon factorization is A329312.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Length of co-Lyndon factorization is A334029.
Cf. A000740, A001037, A027375, A059966, A211100, A302291, A328596, A329142, A333765, A333939, A333941.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#1]}]&,Length[q]-1,1,And];
Select[Range[100],neckQ[Reverse[stc[#]]]&]

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

A342527 Number of compositions of n with alternating parts equal.

Original entry on oeis.org

1, 1, 2, 4, 6, 8, 11, 12, 16, 17, 21, 20, 29, 24, 31, 32, 38, 32, 46, 36, 51, 46, 51, 44, 69, 51, 61, 60, 73, 56, 87, 60, 84, 74, 81, 76, 110, 72, 91, 88, 115, 80, 123, 84, 117, 112, 111, 92, 153, 101, 132, 116, 139, 104, 159, 120, 161, 130, 141, 116, 205, 120, 151, 156, 178, 142, 195, 132, 183, 158

Offset: 0

Gus Wiseman, Mar 24 2021

nonn

These are finite sequences q of positive integers summing to n such that q(i) = q(i+2) for all possible i.

			The a(1) = 1 through a(8) = 16 compositions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (12)   (13)    (14)     (15)      (16)       (17)
             (21)   (22)    (23)     (24)      (25)       (26)
             (111)  (31)    (32)     (33)      (34)       (35)
                    (121)   (41)     (42)      (43)       (44)
                    (1111)  (131)    (51)      (52)       (53)
                            (212)    (141)     (61)       (62)
                            (11111)  (222)     (151)      (71)
                                     (1212)    (232)      (161)
                                     (2121)    (313)      (242)
                                     (111111)  (12121)    (323)
                                               (1111111)  (1313)
                                                          (2222)
                                                          (3131)
                                                          (21212)
                                                          (11111111)

Gus Wiseman, Sequences counting and ranking partitions and compositions by their differences and quotients.

The odd-length case is A062968.
The even-length case is A065608.
The version with alternating parts unequal is A224958 (unordered: A000726).
The version with alternating parts weakly decreasing is A342528.
A000005 counts constant compositions.
A000041 counts weakly increasing (or weakly decreasing) compositions.
A000203 adds up divisors.
A002843 counts compositions with all adjacent parts x <= 2y.
A003242 counts anti-run compositions.
A175342 counts compositions with constant differences.
A342495 counts compositions with constant first quotients.
A342496 counts partitions with constant first quotients (strict: A342515, ranking: A342522).
Cf. A001522, A008965, A048004, A059966, A064410, A064428, A069916, A114921, A167606, A325545, A325557.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],SameQ@@Plus@@@Reverse/@Partition[#,2,1]&]],{n,0,15}]

a(n) = 1 + n + A000203(n) - 2*A000005(n).

a(n) = A065608(n) + A062968(n).

A351204 Number of integer partitions of n such that every permutation has all distinct runs.

Original entry on oeis.org

1, 1, 2, 3, 4, 5, 8, 9, 11, 14, 18, 20, 25, 28, 34, 41, 47, 53, 64, 72, 84, 98, 113, 128, 148, 169, 194, 223, 255, 289, 333, 377, 428, 488, 554, 629, 715, 807, 913, 1033, 1166, 1313, 1483, 1667, 1875, 2111, 2369, 2655, 2977, 3332, 3729, 4170, 4657, 5195, 5797, 6459

Offset: 0

Gus Wiseman, Feb 15 2022

nonn

Partitions enumerated by this sequence include those in which all parts are either the same or distinct as well as partitions with an even number of parts all of which except one are the same. - Andrew Howroyd, Feb 15 2022

			The a(1) = 1 through a(8) = 11 partitions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
       (11)  (21)   (22)    (32)     (33)      (43)       (44)
             (111)  (31)    (41)     (42)      (52)       (53)
                    (1111)  (2111)   (51)      (61)       (62)
                            (11111)  (222)     (421)      (71)
                                     (321)     (2221)     (431)
                                     (3111)    (4111)     (521)
                                     (111111)  (211111)   (2222)
                                               (1111111)  (5111)
                                                          (311111)
                                                          (11111111)

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Mathematics Stack Exchange, What is a sequence run? (answered 2011-12-01)

The version for run-lengths instead of runs is A000005.
The version for normal multisets is 2^(n-1) - A283353(n-3).
The complement is counted by A351203, ranked by A351201.
A005811 counts runs in binary expansion.
A044813 lists numbers whose binary expansion has distinct run-lengths.
A059966 counts Lyndon compositions, necklaces A008965, aperiodic A000740.
A098859 counts partitions with distinct multiplicities, ordered A242882.
A238130 and A238279 count compositions by number of runs.
A297770 counts distinct runs in binary expansion.
A003242 counts anti-run compositions.
Counting words with all distinct runs:
- A351013 = compositions, for run-lengths A329739, ranked by A351290.
- A351016 = binary words, for run-lengths A351017.
- A351018 = binary expansions, for run-lengths A032020, ranked by A175413.
- A351200 = patterns, for run-lengths A351292.
- A351202 = permutations of prime factors.
Cf. A000041, A035363, A047993, A116608, A144300, A329746, A351291.

Table[Length[Select[IntegerPartitions[n],Select[Permutations[#],!UnsameQ@@Split[#]&]=={}&]],{n,0,15}]

\\ here Q(n) is A000009.
Q(n)={polcoef(prod(k=1, n, 1 + x^k + O(x*x^n)), n)}
a(n)={Q(n) + if(n, numdiv(n) - 1) + sum(k=1, (n-1)\3, sum(j=3, (n-1)\k, j%2==1 && n-k*j<>k))} \\ Andrew Howroyd, Feb 15 2022

Terms a(26) and beyond from Andrew Howroyd, Feb 15 2022

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]]]]&]

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

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

A333943 Numbers k such that the k-th composition in standard order is a reversed necklace.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

A342527 Number of compositions of n with alternating parts equal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A351204 Number of integer partitions of n such that every permutation has all distinct runs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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