A060223 -id:A060223 - cp's OEIS frontend

A334269 Number of compositions of n that are both a reversed Lyndon word and a co-Lyndon word.

1, 1, 2, 3, 6, 8, 16, 23, 40, 62, 110, 169, 302, 492, 856, 1454, 2572, 4428, 7914, 13935, 25036, 44842, 81298, 147149, 268952, 491746, 904594, 1667091, 3085950, 5723367, 10652544, 19865887, 37150314, 69608939, 130723184, 245935633, 463590444, 875306913, 1655451592, 3135613649, 5948011978, 11298215516

Offset: 1

Gus Wiseman, Apr 24 2020

nonn

Also the number of compositions of n that are both a Lyndon word and a reversed co-Lyndon word.
A composition of n is a finite sequence of positive integers summing to n.
A Lyndon word is a finite sequence of positive integers that is lexicographically strictly less than all of its cyclic rotations. Co-Lyndon is defined similarly, except with strictly greater instead of strictly less.

			The a(1) = 1 through a(7) = 16 compositions:
  (1)  (2)  (3)   (4)    (5)     (6)      (7)
            (21)  (31)   (32)    (42)     (43)
                  (211)  (41)    (51)     (52)
                         (221)   (321)    (61)
                         (311)   (411)    (322)
                         (2111)  (2211)   (331)
                                 (3111)   (421)
                                 (21111)  (511)
                                          (2221)
                                          (3121)
                                          (3211)
                                          (4111)
                                          (21211)
                                          (22111)
                                          (31111)
                                          (211111)

The version for binary expansion is A334267.
Compositions of this type are ranked by A334266.
Normal sequences of this type are counted by A334270.
Necklace compositions of this type are counted by A334271.
Aperiodic compositions are counted by A000740.
Binary Lyndon words are counted by A001037.
Necklace compositions are counted by A008965.
Normal Lyndon words are counted by A060223.
Lyndon compositions are counted by A059966.
All of the following pertain to compositions in standard order (A066099):
- Lyndon words are A275692.
- Co-Lyndon words are A326774.
- Reversed Lyndon words are A334265.
- Reversed co-Lyndon words are A328596.
- Length of Lyndon factorization is A329312.
- Length of co-Lyndon factorization is A334029.
- Length of Lyndon factorization of reverse is A334297.
- Length of co-Lyndon factorization of reverse is A329313.
- Lyndon factorizations are counted by A333940.
- Co-Lyndon factorizations are counted by A333765.
- Aperiodic compositions are A328594.
- Distinct rotations are counted by A333632.
Cf. A034691, A065609, A275692, A328596, A329141, A329324, A329326, A334266, A334272, A334273, A334274.

lynQ[q_]:=Length[q]==0||Array[Union[{q,RotateRight[q,#1]}]=={q,RotateRight[q,#1]}&,Length[q]-1,1,And];
colynQ[q_]:=Length[q]==0||Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],lynQ[Reverse[#]]&&colynQ[#]&]],{n,0,15}]

Offset corrected and a(21)-a(42) from Bert Dobbelaere, Apr 26 2020

A334271 Number of compositions of n that are both a reversed necklace and a co-necklace.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 12, 17, 28, 43, 70, 111, 184, 303, 510, 865, 1482, 2573, 4480, 7915, 14008

Offset: 0

Gus Wiseman, Apr 25 2020

Also the number of compositions of n that are both a necklace and a reversed co-necklace.

A necklace is a finite sequence of positive integers that is lexicographically less than or equal to any cyclic rotation. Co-necklace is defined similarly, except with greater instead of less.

			The a(1) = 1 through a(6) = 12 compositions:
  (1)  (2)   (3)    (4)     (5)      (6)
       (11)  (21)   (22)    (32)     (33)
             (111)  (31)    (41)     (42)
                    (211)   (221)    (51)
                    (1111)  (311)    (222)
                            (2111)   (321)
                            (11111)  (411)
                                     (2121)
                                     (2211)
                                     (3111)
                                     (21111)
                                     (111111)

Normal sequences of this type are counted by A334272.
The aperiodic case is A334269.
These compositions are ranked by A334273.
Binary (or reversed binary) necklaces are counted by A000031.
Normal sequences are counted by A000670.
Necklace compositions are counted by A008965.
Lyndon compositions are counted by A059966.
Normal Lyndon words are counted by A060223.
Normal necklaces are counted by A019536.
Normal aperiodic words are counted by A296975.
All of the following pertain to compositions in standard order (A066099):
- Necklaces are A065609.
- Reversed necklaces are A333943.
- Co-necklaces are A333764.
- Reversed co-necklaces are A328595.
- Lyndon words are A275692.
- Co-Lyndon words are A326774.
- Reversed Lyndon words are A334265.
- Reversed co-Lyndon words are A328596.
- Aperiodic compositions are A328594.
Cf. A000740, A001037, A034691, A329138, A329324, A334266, A334267, A334274.

neckQ[q_]:=Length[q]==0||Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
coneckQ[q_]:=Length[q]==0||Array[OrderedQ[{RotateRight[q,#],q}]&,Length[q]-1,1,And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[Reverse[#]]&&coneckQ[#]&]],{n,0,15}]

A334272 Number of sequences of length n that cover an initial interval of positive integers and are both a reversed necklace and a co-necklace.

Original entry on oeis.org

1, 1, 2, 4, 12, 43, 229, 1506, 12392, 120443

Offset: 0

Gus Wiseman, Apr 25 2020

A necklace is a finite sequence of positive integers that is lexicographically strictly less than or equal to any cyclic rotation. Co-necklace is defined similarly, except with strictly greater instead of strictly less.

			The a(1) = 1 through a(4) = 12 normal sequences:
  (1)  (1,1)  (1,1,1)  (1,1,1,1)
       (2,1)  (2,1,1)  (2,1,1,1)
              (2,2,1)  (2,1,2,1)
              (3,2,1)  (2,2,1,1)
                       (2,2,2,1)
                       (3,1,2,1)
                       (3,2,1,1)
                       (3,2,2,1)
                       (3,2,3,1)
                       (3,3,2,1)
                       (4,2,3,1)
                       (4,3,2,1)

Dominates A334270 (the aperiodic case).
Compositions of this type are counted by A334271.
These compositions are ranked by A334273 (standard) and A334274 (binary).
Binary (or reversed binary) necklaces are counted by A000031.
Normal sequences are counted by A000670.
Necklace compositions are counted by A008965.
Normal Lyndon words are counted by A060223.
Normal necklaces are counted by A019536.
All of the following pertain to compositions in standard order (A066099):
- Necklaces are A065609.
- Reversed necklaces are A333943.
- Co-necklaces are A333764.
- Reversed co-necklaces are A328595.
- Lyndon words are A275692.
- Co-Lyndon words are A326774.
- Reversed Lyndon words are A334265.
- Reversed co-Lyndon words are A328596.
- Reversed Lyndon co-Lyndon compositions are A334266.
- Aperiodic compositions are A328594.
Cf. A034691, A059966, A296372, A296975, A329138, A334269.

neckQ[q_]:=Length[q]==0||Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
coneckQ[q_]:=Length[q]==0||Array[OrderedQ[{RotateRight[q,#],q}]&,Length[q]-1,1,And];
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n],neckQ[Reverse[#]]&&coneckQ[#]&]],{n,0,8}]

A337564 Number of sequences of length 2*n covering an initial interval of positive integers and splitting into n maximal runs.

Original entry on oeis.org

1, 1, 6, 80, 1540, 38808, 1206744, 44595408, 1908389340, 92780281880, 5050066185736, 304196411024688, 20087958167374552, 1442953024024996400, 112007566256683719600, 9342904053303870936480, 833388624898522799682780, 79159669418651567937733080

Offset: 0

Gus Wiseman, Sep 03 2020

nonn

Sequences covering an initial interval of positive integers are counted by A000670 and ranked by A333217.

			The a(0) = 1 through a(2) = 6 sequences:
  ()  (1,1)  (1,1,1,2)
             (1,1,2,2)
             (1,2,2,2)
             (2,1,1,1)
             (2,2,1,1)
             (2,2,2,1)
The a(3) = 80 sequences:
  212222  111121  122233  333112  211133
  221222  111211  133222  333211  233111
  222122  112111  222133  112233  331112
  222212  121111  222331  113322  332111
  122221  123333  331222  221133  111223
  211222  133332  332221  223311  111322
  221122  213333  122223  331122  221113
  222112  233331  132222  332211  223111
  112221  333312  222213  112223  311122
  122211  333321  222231  113222  322111
  211122  122333  312222  222113  111123
  221112  133322  322221  222311  111132
  111221  221333  112333  311222  211113
  112211  223331  113332  322211  231111
  122111  333122  211333  111233  311112
  211112  333221  233311  111332  321111

Andrew Howroyd, Table of n, a(n) for n = 0..200

A335461 has this as main diagonal n = 2*k.
A336108 is the version for compositions.
A337504 is the version for compositions and anti-runs.
A337505 is the version for anti-runs.
A000670 counts sequences covering an initial interval.
A005649 counts anti-runs covering an initial interval.
A124767 counts maximal runs in standard compositions.
A333769 gives run lengths in standard compositions.
A337504 counts compositions of 2*n with n maximal anti-runs.
A337565 gives anti-run lengths in standard compositions.
Cf. A001700, A003242, A052841, A060223, A106351, A106356, A269134, A325535, A333489, A333627, A333755, A335838.

allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[2*n],Length[Split[#]]==n&]],{n,0,3}]

\\ here b(n) is A005649.
b(n) = {sum(k=0, n, stirling(n,k,2)*(k + 1)!)}
a(n) = {if(n==0, 1, b(n-1)*binomial(2*n-1,n-1))} \\ Andrew Howroyd, Dec 31 2020

a(n) = A005649(n-1)*binomial(2*n-1,n-1) = A005649(n-1)*A001700(n-1) for n > 0. - Andrew Howroyd, Dec 31 2020

Terms a(5) and beyond from Andrew Howroyd, Dec 31 2020

A296656 Triangle whose n-th row is the concatenated sequence of all Lyndon compositions of n in reverse-lexicographic order.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Dec 18 2017

			Triangle of Lyndon compositions begins:
(1),
(2),
(3),(12),
(4),(13),(112),
(5),(23),(14),(122),(113),(1112),
(6),(24),(15),(132),(123),(114),(1122),(1113),(11112),
(7),(34),(25),(223),(16),(142),(133),(124),(1222),(1213),(115),(1132),(1123),(11212),(1114),(11122),(11113),(111112).

Cf. A000740, A001037, A001045, A008965, A059966, A060223, A066099, A101211, A102659, A124734, A185700, A228369, A281013, A294859, A296302, A296373.

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Sort[Select[Join@@Permutations/@IntegerPartitions[n],LyndonQ],OrderedQ[PadRight[{#2,#1}]]&],{n,7}]

Row n is a concatenation of A059966(n) Lyndon words with total length A000740(n).

A329327 Numbers whose binary expansion has Lyndon factorization of length 2 (the minimum for n > 1).

Original entry on oeis.org

2, 3, 5, 9, 11, 17, 19, 23, 33, 35, 37, 39, 43, 47, 65, 67, 69, 71, 75, 77, 79, 87, 95, 129, 131, 133, 135, 137, 139, 141, 143, 147, 149, 151, 155, 157, 159, 171, 175, 183, 191, 257, 259, 261, 263, 265, 267, 269, 271, 275, 277, 279, 281, 283, 285, 287, 293

Offset: 1

Gus Wiseman, Nov 12 2019

nonn

First differs from A329357 in having 77 and lacking 83.

Also numbers whose decapitated binary expansion is a Lyndon word (see also A329401).

			The binary expansion of each term together with its Lyndon factorization begins:
   2:      (10) = (1)(0)
   3:      (11) = (1)(1)
   5:     (101) = (1)(01)
   9:    (1001) = (1)(001)
  11:    (1011) = (1)(011)
  17:   (10001) = (1)(0001)
  19:   (10011) = (1)(0011)
  23:   (10111) = (1)(0111)
  33:  (100001) = (1)(00001)
  35:  (100011) = (1)(00011)
  37:  (100101) = (1)(00101)
  39:  (100111) = (1)(00111)
  43:  (101011) = (1)(01011)
  47:  (101111) = (1)(01111)
  65: (1000001) = (1)(000001)
  67: (1000011) = (1)(000011)
  69: (1000101) = (1)(000101)
  71: (1000111) = (1)(000111)
  75: (1001011) = (1)(001011)
  77: (1001101) = (1)(001101)

Positions of 2's in A211100.
Positions of rows of length 2 in A329314.
The "co-" and reversed version is A329357.
Binary Lyndon words are counted by A001037 and ranked by A102659.
Length of the co-Lyndon factorization of the binary expansion is A329312.
Cf. A059966, A060223, A211097, A275692, A328594, A328595, A328596, A329131, A329313, A329325, A329326, A339608.

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,#1]]&]]]];
Select[Range[100],Length[lynfac[IntegerDigits[#,2]]]==2&]

a(n) = A339608(n) + 1. - Harald Korneliussen, Mar 12 2020

A334270 Number of sequences of length n that cover an initial interval of positive integers and are both a reversed Lyndon word and a co-Lyndon word.

Original entry on oeis.org

1, 1, 1, 3, 10, 42, 224, 1505, 12380, 120439

Offset: 0

Gus Wiseman, Apr 24 2020

Also the number of sequences of length n that cover an initial interval of positive integers and are both a Lyndon word and a reversed co-Lyndon word.

A Lyndon word is a finite sequence of positive integers that is lexicographically strictly less than all of its cyclic rotations. Co-Lyndon is defined similarly, except with strictly greater instead of strictly less.

			The a(1) = 1 through a(4) = 10 normal sequences:
  (1)  (2,1)  (2,1,1)  (2,1,1,1)
              (2,2,1)  (2,2,1,1)
              (3,2,1)  (2,2,2,1)
                       (3,1,2,1)
                       (3,2,1,1)
                       (3,2,2,1)
                       (3,2,3,1)
                       (3,3,2,1)
                       (4,2,3,1)
                       (4,3,2,1)

These compositions are ranked by A334266 (standard) and A334267 (binary).
Compositions of this type are counted by A334269.
Necklace compositions of this type are counted by A334271.
Dominated by A334272 (the necklace version).
Normal sequences are counted by A000670.
Binary (or reversed binary) Lyndon words are counted by A001037.
Lyndon compositions are counted by A059966.
Normal Lyndon words are counted by A060223.
Normal sequences by length and Lyndon factorization length are A296372.
All of the following pertain to compositions in standard order (A066099):
- Lyndon words are A275692.
- Co-Lyndon words are A326774.
- Reversed Lyndon words are A334265.
- Reversed co-Lyndon words are A328596.
- Length of Lyndon factorization is A329312.
- Length of co-Lyndon factorization is A334029.
- Length of Lyndon factorization of reverse is A334297.
- Length of co-Lyndon factorization of reverse is A329313.
Cf. A008965, A034691, A329324, A329398, A334273.

lynQ[q_]:=Length[q]==0||Array[Union[{q,RotateRight[q,#1]}]=={q,RotateRight[q,#1]}&,Length[q]-1,1,And];
colynQ[q_]:=Length[q]==0||Array[Union[{RotateRight[q,#],q}]=={RotateRight[q,#],q}&,Length[q]-1,1,And];
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Length[Select[Join@@Permutations/@allnorm[n],lynQ[Reverse[#]]&&colynQ[#]&]],{n,0,6}]

A277427 Prime permutations, ordered lexicographically.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Oct 14 2016

A permutation of {1..n} is prime (in the sense of A215474) iff it is of the form (n, q_1, q_2, ..., q_{n-1}).

Row n in the triangle consists of all permutations consisting of n followed by a permutation of 1..n-1, in lexicographic order.

			The sequence of prime permutations begins:
1,
21,
312, 321,
4123, 4132, 4213, 4231, 4312, 4321,
...

Gus Wiseman, Table of n, a(n) for n = 1..5912

Cf. A215474, A254040, A060223, A005117.

seq(op(map(t -> (n,op(t)), combinat:-permute(n-1))), n=1..6); # Robert Israel, Nov 07 2016

row[n_] := Join[{n}, #]& /@ Permutations[Range[n-1]];
Array[row, 5] // Flatten (* Jean-François Alcover, Apr 10 2019 *)

A298971 Number of compositions of n that are proper powers of Lyndon words.

Original entry on oeis.org

0, 1, 1, 2, 1, 4, 1, 5, 3, 8, 1, 16, 1, 20, 9, 35, 1, 69, 1, 110, 21, 188, 1, 381, 7, 632, 59, 1184, 1, 2300, 1, 4115, 189, 7712, 25, 14939, 1, 27596, 633, 52517, 1, 101050, 1, 190748, 2247, 364724, 1, 703331, 19, 1342283, 7713, 2581430, 1, 4985609, 193

Offset: 1

Gus Wiseman, Jan 30 2018

nonn

a(n) is the number of compositions of n that are not Lyndon words but are of the form p * p * ... * p where * is concatenation and p is a Lyndon word.

			The a(12) = 16 compositions: 111111111111, 1111211112, 11131113, 112112112, 11221122, 114114, 12121212, 123123, 131313, 132132, 1515, 222222, 2424, 3333, 444, 66.

Cf. A000005, A000031, A000740, A000961, A001045, A008965, A019536, A034691, A051953, A052823, A059966, A060223, A178472, A185700, A296302, A296373.

Table[Sum[DivisorSum[d,MoebiusMu[d/#]*(2^#-1)&]/d,{d,Most@Divisors[n]}],{n,100}]

a(n) = sumdiv(n, d, (2^d-1)*(eulerphi(n/d)-moebius(n/d))/n); \\ Michel Marcus, Jan 31 2018

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

a(n) = A008965(n) - A059966(n).

A306669 Number of aperiodic permutation necklaces of weight n.

Original entry on oeis.org

1, 0, 1, 4, 23, 110, 719, 4992, 40302, 362492, 3628799, 39912804, 479001599, 6226974714, 87178289207, 1307673722880, 20922789887999, 355687417744992, 6402373705727999, 121645100223036700, 2432902008176115023, 51090942167993548790, 1124000727777607679999

Offset: 1

Gus Wiseman, Mar 04 2019

nonn

A permutation is aperiodic if every rotation of {1...n} acts on the vertices of the cycle decomposition to produce a different digraph. A permutation necklace is an equivalence class of permutations 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).

Andrew Howroyd, Table of n, a(n) for n = 1..200
Gus Wiseman, Inequivalent representatives of the a(5) = 23 aperiodic necklace permutations.

Cf. A000031, A000740, A000939, A001037, A059966, A060223, A061417, A086675, A323861, A323865, A323866, A323871.

Cf. A324461, A324512, A324513, A324514.

Table[Length[Select[Permutations[Range[n]],UnsameQ@@NestList[RotateRight[#/.k_Integer:>If[k==n,1,k+1]]&,#,n-1]&]]/n,{n,6}]

a(n) = (1/n)*sumdiv(n, d, moebius(n/d)*(n/d)^d*d!); \\ Andrew Howroyd, Aug 19 2019

a(n) = A324514(n)/n.

a(n) = (1/n)*Sum_{d|n} mu(n/d)*(n/d)^d*d!. - Andrew Howroyd, Aug 19 2019

Terms a(10) and beyond from Andrew Howroyd, Aug 19 2019

cp's OEIS Frontend

A334269 Number of compositions of n that are both a reversed Lyndon word and a co-Lyndon word.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A334271 Number of compositions of n that are both a reversed necklace and a co-necklace.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A334272 Number of sequences of length n that cover an initial interval of positive integers and are both a reversed necklace and a co-necklace.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A337564 Number of sequences of length 2*n covering an initial interval of positive integers and splitting into n maximal runs.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A296656 Triangle whose n-th row is the concatenated sequence of all Lyndon compositions of n in reverse-lexicographic order.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A329327 Numbers whose binary expansion has Lyndon factorization of length 2 (the minimum for n > 1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A334270 Number of sequences of length n that cover an initial interval of positive integers and are both a reversed Lyndon word and a co-Lyndon word.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A277427 Prime permutations, ordered lexicographically.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple