A329395 -id:A329395 - cp's OEIS frontend

A357181 Last run-length of the n-th composition in standard order.

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

Offset: 0

Gus Wiseman, Sep 24 2022

nonn

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (graded reverse-lexicographic, 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.

			Composition 87 in standard order is (2,2,1,1,1), so a(87) = 3.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

See link for sequences related to standard compositions.
For parts instead of run-lengths we have A001511, first A065120.
For Heinz numbers of partitions we have A071178, first A067029.
This is the last part of row n of A333769.
For maximal instead of last we have A357137, minimal A357138.
The first instead of last run-length is A357180.
A051903 gives maximal part of prime signature.
A061395 gives maximal prime index.
A124767 counts runs in standard compositions.
A286470 gives maximal difference of prime indices.
A333766 gives maximal part of standard composition, minimal A333768.
A353847 ranks run-sums of standard compositions.
Cf. A000120, A003754, A029931, A070939, A329395, A356841, A356844, A357134, A357135, A357136.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[If[n==0,0,Last[Length/@Split[stc[n]]]],{n,0,100}]

A329358 Numbers whose binary expansion has Lyndon and co-Lyndon factorizations of equal lengths.

Original entry on oeis.org

1, 3, 5, 7, 9, 15, 17, 21, 27, 31, 33, 45, 51, 63, 65, 73, 74, 83, 85, 86, 89, 93, 99, 107, 119, 127, 129, 138, 150, 153, 163, 165, 174, 177, 185, 189, 195, 203, 205, 219, 231, 255, 257, 266, 273, 274, 278, 291, 294, 297, 302, 305, 310, 313, 323, 325, 333, 341

Offset: 1

Gus Wiseman, Nov 15 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).

			The binary expansions of the initial terms together with their Lyndon and co-Lyndon factorizations:
   1:       (1) =                (1) = (1)
   3:      (11) =             (1)(1) = (1)(1)
   5:     (101) =            (1)(01) = (10)(1)
   7:     (111) =          (1)(1)(1) = (1)(1)(1)
   9:    (1001) =           (1)(001) = (100)(1)
  15:    (1111) =       (1)(1)(1)(1) = (1)(1)(1)(1)
  17:   (10001) =          (1)(0001) = (1000)(1)
  21:   (10101) =        (1)(01)(01) = (10)(10)(1)
  27:   (11011) =        (1)(1)(011) = (110)(1)(1)
  31:   (11111) =    (1)(1)(1)(1)(1) = (1)(1)(1)(1)(1)
  33:  (100001) =         (1)(00001) = (10000)(1)
  45:  (101101) =       (1)(011)(01) = (10)(110)(1)
  51:  (110011) =       (1)(1)(0011) = (1100)(1)(1)
  63:  (111111) = (1)(1)(1)(1)(1)(1) = (1)(1)(1)(1)(1)(1)
  65: (1000001) =        (1)(000001) = (100000)(1)
  73: (1001001) =      (1)(001)(001) = (100)(100)(1)
  74: (1001010) =      (1)(00101)(0) = (100)(10)(10)
  83: (1010011) =      (1)(01)(0011) = (10100)(1)(1)

The version counting compositions is A329394.
The version ignoring the most significant digit is A329395.
Binary Lyndon/co-Lyndon words are counted by A001037.
Lyndon/co-Lyndon compositions are counted by A059966.
Lyndon compositions whose reverse is not co-Lyndon are A329324.
Binary Lyndon/co-Lyndon words are constructed by A102659 and A329318.
Cf. A060223, A211100, A275692, A328596, A329312, A329313, A329326, A329398.

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[IntegerDigits[#,2]]]==Length[colynfac[IntegerDigits[#,2]]]&]

A211100(a(n)) = A329312(a(n)).

A329394 Number of compositions of n whose Lyndon and co-Lyndon factorizations both have the same length.

Original entry on oeis.org

1, 2, 2, 4, 4, 10, 13, 28, 46, 99, 175, 359, 672, 1358, 2627, 5238, 10262, 20438, 40320, 80137

Offset: 1

Gus Wiseman, Nov 13 2019

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

			The a(1) = 1 through a(7) = 13 compositions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)
       (11)  (111)  (22)    (131)    (33)      (151)
                    (121)   (212)    (141)     (214)
                    (1111)  (11111)  (213)     (232)
                                     (222)     (241)
                                     (231)     (313)
                                     (1221)    (1312)
                                     (2112)    (1321)
                                     (11211)   (2113)
                                     (111111)  (11311)
                                               (12121)
                                               (21112)
                                               (1111111)

Lyndon and co-Lyndon compositions are (both) counted by A059966.
Lyndon compositions that are not weakly increasing are A329141.
Lyndon compositions of n whose reverse is not co-Lyndon are A329324.
Cf. A000740, A001037, A008965, A060223, A102659, A211100, A275692, A328596, A329312, A329318, A329395, A329398.

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,#]]&]]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[lynfac[#]]==Length[colynfac[#]]&]],{n,10}]

A329397 Number of compositions of n whose Lyndon factorization is uniform.

Original entry on oeis.org

1, 2, 4, 7, 12, 20, 33, 55, 92, 156, 267, 466, 822, 1473, 2668, 4886, 9021, 16786, 31413, 59101, 111654, 211722, 402697, 768025, 1468170, 2812471, 5397602, 10376418, 19978238, 38519537, 74365161, 143742338, 278156642, 538831403, 1044830113, 2027879831

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

A sequence of words is uniform if they all have the same length.

			The a(1) = 1 through a(6) = 20 Lyndon factorizations:
  (1)  (2)     (3)        (4)           (5)              (6)
       (1)(1)  (12)       (13)          (14)             (15)
               (2)(1)     (112)         (23)             (24)
               (1)(1)(1)  (2)(2)        (113)            (114)
                          (3)(1)        (122)            (123)
                          (2)(1)(1)     (1112)           (132)
                          (1)(1)(1)(1)  (3)(2)           (1113)
                                        (4)(1)           (1122)
                                        (2)(2)(1)        (3)(3)
                                        (3)(1)(1)        (4)(2)
                                        (2)(1)(1)(1)     (5)(1)
                                        (1)(1)(1)(1)(1)  (11112)
                                                         (12)(12)
                                                         (2)(2)(2)
                                                         (3)(2)(1)
                                                         (4)(1)(1)
                                                         (2)(2)(1)(1)
                                                         (3)(1)(1)(1)
                                                         (2)(1)(1)(1)(1)
                                                         (1)(1)(1)(1)(1)(1)

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Lyndon and co-Lyndon compositions are (both) counted by A059966.
Lyndon compositions that are not weakly increasing are A329141.
Lyndon compositions whose reverse is not co-Lyndon are A329324.
Cf. A000740, A001037, A008965, A060223, A102659, A211100, A275692, A328596, A329312, A329318, A329395, A329396, A329398, A329399.

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[Select[Join@@Permutations/@IntegerPartitions[n],SameQ@@Length/@lynfac[#]&]],{n,10}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
B(n,k) = {sumdiv(n, d, moebius(d)/(1-x^d)^(n/d) + O(x*x^k))/n}
seq(n) = {sum(d=1, n-1, my(v=Vec(B(d,n-d),-n)); EulerT(v))} \\ Andrew Howroyd, Feb 03 2022

G.f.: Sum_{r>=1} (exp(Sum_{k>=1} B(r, x^k)/k) - 1) where B(r, x) = (Sum_{d|r} mu(d)/(1 - x^d)^(r/d))*x^r/r. - Andrew Howroyd, Feb 03 2022

a(19)-a(25) from Robert Price, Jun 20 2021

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

A357708 Numbers k such that the k-th composition in standard order has sum equal to twice its maximum part.

Original entry on oeis.org

3, 10, 11, 13, 14, 36, 37, 38, 39, 41, 44, 50, 51, 52, 57, 60, 136, 137, 138, 139, 140, 141, 142, 143, 145, 152, 162, 163, 168, 177, 184, 196, 197, 198, 199, 200, 209, 216, 226, 227, 232, 241, 248, 528, 529, 530, 531, 532, 533, 534, 535, 536, 537, 538, 539

Offset: 1

Gus Wiseman, Oct 14 2022

nonn

The k-th composition in standard order (graded reverse-lexicographic, 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 terms and corresponding compositions begin:
    3: (1,1)
   10: (2,2)
   11: (2,1,1)
   13: (1,2,1)
   14: (1,1,2)
   36: (3,3)
   37: (3,2,1)
   38: (3,1,2)
   39: (3,1,1,1)
   41: (2,3,1)
   44: (2,1,3)
   50: (1,3,2)
   51: (1,3,1,1)

Gus Wiseman, Statistics, classes, and transformations of standard compositions

See link for sequences related to standard compositions.
A066311 lists gapless numbers.
A124767 counts runs in standard compositions.
A333766 gives maximal part of standard compositions, minimal A333768.
A356844 ranks compositions with at least one 1.
Cf. A000120, A001511, A003754, A029931, A329395.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,1000],Max@@stc[#]==Total[stc[#]]/2&]

A358138 Difference between maximum and minimum part in the n-th composition in standard order.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Oct 31 2022

nonn

The k-th composition in standard order (graded reverse-lexicographic, 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.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

See link for sequences related to standard compositions.
The first and last parts are A065120 and A001511, difference A358135.
This is the maximum minus minimum part in row n of A066099.
The version for Heinz numbers of partitions is A243055.
The maximum and minimum parts are A333766 and A333768.
The partial sums of standard compositions are A358134, adjusted A242628.
A011782 counts compositions.
A351014 counts distinct runs in standard compositions.
Cf. A000120, A029837, A029931, A048896, A058891, A070939, A133494, A329395, A357187, A358133.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Max[stc[n]]-Min[stc[n]],{n,1,100}]

a(n) = A333766(n) - A333768(n).

A358525 Number of distinct permutations of the n-th composition in standard order.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Nov 21 2022

nonn

The k-th composition in standard order (graded reverse-lexicographic, 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 a(45) = 6 permutations are: (2121), (2112), (2211), (1221), (1212), (1122).

Gus Wiseman, Statistics, classes, and transformations of standard compositions

See link for sequences related to standard compositions.
Positions of 1's are A272919.
Cf. A000120, A048896, A070939, A329395, A333766, A358371, A358372, A358379, A358505, A358507, A358508.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
Table[Length[Permutations[stc[n]]],{n,0,100}]

cp's OEIS Frontend

A357181 Last run-length of the n-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A329358 Numbers whose binary expansion has Lyndon and co-Lyndon factorizations of equal lengths.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A329394 Number of compositions of n whose Lyndon and co-Lyndon factorizations both have the same length.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329397 Number of compositions of n whose Lyndon factorization is uniform.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A357708 Numbers k such that the k-th composition in standard order has sum equal to twice its maximum part.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A358138 Difference between maximum and minimum part in the n-th composition in standard order.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A358525 Number of distinct permutations of the n-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica