A211100 -id:A211100 - cp's OEIS frontend

A333765 Number of co-Lyndon factorizations of the k-th composition in standard order.

1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 2, 2, 4, 5, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 4, 2, 4, 4, 7, 7, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 3, 1, 2, 2, 2, 1, 2, 2, 2, 2, 5, 2, 5, 2, 4, 4, 9, 4, 7, 7, 12, 11, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 2, 4, 1

Offset: 0

Gus Wiseman, Apr 13 2020

nonn

We define the co-Lyndon product of two or more finite sequences to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (2,3,1) with (2,1,3) is (2,1,2,3,1,3), the product of (2,2,1) with (2,1,3) is (2,1,2,2,1,3), and the product of (1,2,2) with (2,1,2,1) is (1,2,1,2,1,2,2). A co-Lyndon factorization of a composition c is a multiset of compositions whose co-Lyndon product is c.
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.
Also the number of multiset partitions of the co-Lyndon-word factorization of the n-th composition in standard order.

			The a(54) = 5, a(61) = 7, and a(237) = 9 factorizations:
  ((1,2,1,2))      ((1,1,1,2,1))        ((1,1,2,1,2,1))
  ((1),(2,1,2))    ((1),(1,1,2,1))      ((1),(1,2,1,2,1))
  ((1,2),(2,1))    ((1,1),(1,2,1))      ((1,1),(2,1,2,1))
  ((2),(1,2,1))    ((2,1),(1,1,1))      ((1,2,1),(1,2,1))
  ((1),(2),(2,1))  ((1),(1),(1,2,1))    ((2,1),(1,1,2,1))
                   ((1),(1,1),(2,1))    ((1),(1),(2,1,2,1))
                   ((1),(1),(1),(2,1))  ((1,1),(2,1),(2,1))
                                        ((1),(2,1),(1,2,1))
                                        ((1),(1),(2,1),(2,1))

The dual version is A333940.
Binary necklaces are counted by A000031.
Necklace compositions are counted by A008965.
Necklaces covering an initial interval are counted by A019536.
Lyndon compositions are counted by A059966.
Numbers whose reversed binary expansion is a necklace are A328595.
Numbers whose prime signature is a necklace are A329138.
Length of Lyndon factorization of binary expansion is A211100.
Length of co-Lyndon factorization of binary expansion is A329312.
Length of co-Lyndon factorization of reversed binary expansion is A329326.
Length of Lyndon factorization of reversed binary expansion is A329313.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- 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.
- Reversed co-necklaces are A328595.
- Length of Lyndon factorization is A329312.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Dealings are counted by A333939.
- Reversed necklaces are A333943.
- Length of co-Lyndon factorization is A334029.
- Combinatory separations are A334030.
Cf. A000740, A001037, A034691, A060223, A211100, A269134, A292884, A328596.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
colynprod[]:={};colynprod[{},b_List]:=b;colynprod[a_List,{}]:=a;colynprod[a_List]:=a;
colynprod[{x_,a___},{y_,b___}]:=Switch[Ordering[If[x=!=y,{x,y},{colynprod[{a},{x,b}],colynprod[{x,a},{b}]}]],{1,2},Prepend[colynprod[{a},{y,b}],x],{2,1},Prepend[colynprod[{x,a},{b}],y]];
colynprod[a_List,b_List,c__List]:=colynprod[a,colynprod[b,c]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
dealings[q_]:=Union[Function[ptn,Sort[q[[#]]&/@ptn]]/@sps[Range[Length[q]]]];
Table[Length[Select[dealings[stc[n]],colynprod@@#==stc[n]&]],{n,0,100}]

For n > 0, Sum_{k = 2^(n-1)..2^n-1} a(k) = A034691(n).

A329317 Length of the Lyndon factorization of the reversed first n terms of A000002.

Original entry on oeis.org

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

Offset: 1

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

			The sequence of Lyndon factorizations of the reversed initial terms of A000002 begins:
   1: (1)
   2: (2)(1)
   3: (2)(2)(1)
   4: (122)(1)
   5: (1122)(1)
   6: (2)(1122)(1)
   7: (12)(1122)(1)
   8: (2)(12)(1122)(1)
   9: (2)(2)(12)(1122)(1)
  10: (122)(12)(1122)(1)
  11: (2)(122)(12)(1122)(1)
  12: (2)(2)(122)(12)(1122)(1)
  13: (122)(122)(12)(1122)(1)
  14: (112212212)(1122)(1)
  15: (2)(112212212)(1122)(1)
  16: (12)(112212212)(1122)(1)
  17: (1121122122121122)(1)
  18: (2)(1121122122121122)(1)
  19: (2)(2)(1121122122121122)(1)
  20: (122)(1121122122121122)(1)
For example, the reversed first 13 terms of A000002 are (1221221211221), with Lyndon factorization (122)(122)(12)(1122)(1), so a(13) = 5.

Row-lengths of A329316.
The non-reversed version is A329315.
Cf. A000002, A000031, A001037, A027375, A059966, A060223, A088568, A102659, A211100, A288605, A296372, A296658, A329314, A329325.

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,#]]&]]]];
kolagrow[q_]:=If[Length[q]<2,Take[{1,2},Length[q]+1],Append[q,Switch[{q[[Length[Split[q]]]],q[[-2]],Last[q]},{1,1,1},0,{1,1,2},1,{1,2,1},2,{1,2,2},0,{2,1,1},2,{2,1,2},2,{2,2,1},1,{2,2,2},1]]]
kol[n_Integer]:=Nest[kolagrow,{1},n-1];
Table[Length[lynfac[Reverse[kol[n]]]],{n,100}]

A334029 Length of the co-Lyndon factorization of the k-th composition in standard order.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Apr 14 2020

nonn

We define the co-Lyndon product of two or more finite sequences to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (2,3,1) with (2,1,3) is (2,1,2,3,1,3), the product of (2,2,1) with (2,1,3) is (2,1,2,2,1,3), and the product of (1,2,2) with (2,1,2,1) is (1,2,1,2,1,2,2). 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, (1,0,0,1) has co-Lyndon factorization {(1),(1,0,0)}.

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 441st composition in standard order is (1,2,1,1,3,1), with co-Lyndon factorization {(1),(3,1),(2,1,1)}, so a(441) = 3.

The dual version is A329312.
The version for binary expansion is (also) A329312.
The version for reversed binary expansion is A329326.
Binary Lyndon/co-Lyndon words are counted by A001037.
Necklaces covering an initial interval are A019536.
Lyndon/co-Lyndon compositions are counted by A059966
Length of Lyndon factorization of binomial expansion is A211100.
Numbers whose prime signature is a necklace are A329138.
Length of Lyndon factorization of reversed binary expansion is A329313.
A list of all binary co-Lyndon words is A329318.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- 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.
- Reversed co-necklaces are A328595.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Co-Lyndon factorizations are counted by A333765.
- Lyndon factorizations are counted by A333940.
- Reversed necklaces are A333943.
- Co-necklaces are A334028.
Cf. A034691, A060223, A102659, A211097, A292884, A296372, A328596, A329358, A329359, A329362, A329400, A329401, A333939.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
colynQ[q_]:=Length[q]==0||Array[Union[{RotateRight[q,#1],q}]=={RotateRight[q,#1],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,#1]]&]]]]
Table[Length[colynfac[stc[n]]],{n,0,100}]

A329316 Irregular triangle read by rows where row n gives the sequence of lengths of components of the Lyndon factorization of the reversed first n terms of A000002.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 4, 1, 1, 4, 1, 2, 4, 1, 1, 2, 4, 1, 1, 1, 2, 4, 1, 3, 2, 4, 1, 1, 3, 2, 4, 1, 1, 1, 3, 2, 4, 1, 3, 3, 2, 4, 1, 9, 4, 1, 1, 9, 4, 1, 2, 9, 4, 1, 16, 1, 1, 16, 1, 1, 1, 16, 1, 3, 16, 1, 1, 3, 16, 1, 5, 16, 1, 6, 16, 1, 1, 6, 16, 1, 2, 6

Offset: 0

Gus Wiseman, Nov 11 2019

There are no repeated rows, as row n has sum n.
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).
It appears that some numbers (such as 10) never appear in the sequence.

			Triangle begins:
   1: (1)
   2: (1,1)
   3: (1,1,1)
   4: (3,1)
   5: (4,1)
   6: (1,4,1)
   7: (2,4,1)
   8: (1,2,4,1)
   9: (1,1,2,4,1)
  10: (3,2,4,1)
  11: (1,3,2,4,1)
  12: (1,1,3,2,4,1)
  13: (3,3,2,4,1)
  14: (9,4,1)
  15: (1,9,4,1)
  16: (2,9,4,1)
  17: (16,1)
  18: (1,16,1)
  19: (1,1,16,1)
  20: (3,16,1)
For example, the reversed first 13 terms of A000002 are (1221221211221), with Lyndon factorization (122)(122)(12)(1122)(1), so row 13 is (3,3,2,4,1).

Row lengths are A329317.
The non-reversed version is A329315.
Cf. A000002, A000031, A001037, A027375, A059966, A060223, A088568, A102659, A211100, A288605, A296372, A296658, A329314, A329325.

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,#]]&]]]];
kolagrow[q_]:=If[Length[q]<2,Take[{1,2},Length[q]+1],Append[q,Switch[{q[[Length[Split[q]]]],q[[-2]],Last[q]},{1,1,1},0,{1,1,2},1,{1,2,1},2,{1,2,2},0,{2,1,1},2,{2,1,2},2,{2,2,1},1,{2,2,2},1]]]
kol[n_Integer]:=Nest[kolagrow,{1},n-1];
Table[Length/@lynfac[Reverse[kol[n]]],{n,100}]

A334265 Numbers k such that the k-th composition in standard order is a reversed Lyndon word.

Original entry on oeis.org

0, 1, 2, 4, 5, 8, 9, 11, 16, 17, 18, 19, 21, 23, 32, 33, 34, 35, 37, 39, 41, 43, 47, 64, 65, 66, 67, 68, 69, 71, 73, 74, 75, 77, 79, 81, 83, 85, 87, 91, 95, 128, 129, 130, 131, 132, 133, 135, 137, 138, 139, 141, 143, 145, 146, 147, 149, 151, 155, 159, 161, 163

Offset: 1

Gus Wiseman, Apr 22 2020

nonn

Reversed Lyndon words are different from co-Lyndon words (A326774).
A Lyndon word is a finite sequence of positive integers that is lexicographically strictly less than all of its cyclic rotations.
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 sequence of all reversed Lyndon words begins:
    0: ()            37: (3,2,1)         83: (2,3,1,1)
    1: (1)           39: (3,1,1,1)       85: (2,2,2,1)
    2: (2)           41: (2,3,1)         87: (2,2,1,1,1)
    4: (3)           43: (2,2,1,1)       91: (2,1,2,1,1)
    5: (2,1)         47: (2,1,1,1,1)     95: (2,1,1,1,1,1)
    8: (4)           64: (7)            128: (8)
    9: (3,1)         65: (6,1)          129: (7,1)
   11: (2,1,1)       66: (5,2)          130: (6,2)
   16: (5)           67: (5,1,1)        131: (6,1,1)
   17: (4,1)         68: (4,3)          132: (5,3)
   18: (3,2)         69: (4,2,1)        133: (5,2,1)
   19: (3,1,1)       71: (4,1,1,1)      135: (5,1,1,1)
   21: (2,2,1)       73: (3,3,1)        137: (4,3,1)
   23: (2,1,1,1)     74: (3,2,2)        138: (4,2,2)
   32: (6)           75: (3,2,1,1)      139: (4,2,1,1)
   33: (5,1)         77: (3,1,2,1)      141: (4,1,2,1)
   34: (4,2)         79: (3,1,1,1,1)    143: (4,1,1,1,1)
   35: (4,1,1)       81: (2,4,1)        145: (3,4,1)

The non-reversed version is A275692.
The generalization to necklaces is A333943.
The dual version (reversed co-Lyndon words) is A328596.
The case that is also co-Lyndon is A334266.
Binary Lyndon words are counted by A001037.
Lyndon compositions are counted by A059966.
Normal Lyndon words are counted by A060223.
Numbers whose prime signature is a reversed Lyndon word are A334298.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Reverse is A228351 (triangle).
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon words are A275692.
- Reversed Lyndon words are A334265 (this sequence).
- Co-Lyndon words are A326774.
- Reversed co-Lyndon words are A328596.
- Length of Lyndon factorization is A329312.
- Distinct rotations are counted by A333632.
- Lyndon factorizations are counted by A333940.
- Length of Lyndon factorization of reverse is A334297.
Cf. A000031, A027375, A138904, A211100, A328595, A329131, A329313, A333764, A334028, A334267.

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

A302291 a(n) is the period of the binary expansion of n.

Original entry on oeis.org

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

Offset: 0

Rémy Sigrist, Apr 04 2018

Zero is assumed to be represented as 0; otherwise, leading zeros are ignored.

See A302295 for the variant where leading zeros are allowed.

			The first terms, alongside the binary expansion of n with periodic part in parentheses, are:
  n  a(n)    bin(n)
  -- ----    ------
   0    1    (0)
   1    1    (1)
   2    2    (10)
   3    1    (1)(1)
   4    3    (100)
   5    3    (101)
   6    3    (110)
   7    1    (1)(1)(1)
   8    4    (1000)
   9    4    (1001)
  10    2    (10)(10)
  11    4    (1011)
  12    4    (1100)
  13    4    (1101)
  14    4    (1110)
  15    1    (1)(1)(1)(1)
  16    5    (10000)
  17    5    (10001)
  18    5    (10010)
  19    5    (10011)
  20    5    (10100)

Rémy Sigrist, Table of n, a(n) for n = 0..10000
Index entries for sequences related to binary expansion of n

Aperiodic compositions are counted by A000740.
Aperiodic binary words are counted by A027375.
The orderless period of prime indices is A052409.
Numbers whose binary expansion is periodic are A121016.
Periodic compositions are counted by A178472.
Numbers whose prime signature is aperiodic are A329139.
Compositions by number of distinct rotations are A333941.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- 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.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Reversed necklaces are A333943.
Cf. A000031, A001037, A008965, A019536, A020330, A211100, A302295, A328595, A328596, A329312, A329313, A329326.

Table[If[n==0,1,Length[Union[Array[RotateRight[IntegerDigits[n,2],#]&,IntegerLength[n,2]]]]],{n,0,50}] (* Gus Wiseman, Apr 19 2020 *)

a(n) = my (l=max(1, #binary(n))); fordiv (l, w, if (#Set(digits(n, 2^w))<=1, return (w)))

a(n) = A070939(n) / A138904(n).
a(2^n) = n + 1 for any n >= 0.
a(2^n - 1) = 1 for any n >= 0.
a(A020330(n)) = a(n) for any n > 0.

A333939 Number of multisets of compositions that can be shuffled together to obtain the k-th composition in standard order.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 4, 2, 5, 4, 5, 1, 2, 2, 4, 2, 4, 5, 7, 2, 5, 4, 10, 4, 10, 7, 7, 1, 2, 2, 4, 2, 5, 5, 7, 2, 5, 3, 9, 5, 13, 11, 12, 2, 5, 5, 10, 5, 11, 13, 18, 4, 10, 9, 20, 7, 18, 12, 11, 1, 2, 2, 4, 2, 5, 5, 7, 2, 4, 4, 11, 5, 14, 11, 12, 2

Offset: 0

Gus Wiseman, Apr 15 2020

nonn

Number of ways to deal out the k-th composition in standard order to form a multiset of hands.

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 dealings for n = 1, 3, 7, 11, 13, 23, 43:
  (1)  (11)    (111)      (211)      (121)      (2111)        (2211)
       (1)(1)  (1)(11)    (1)(21)    (1)(12)    (11)(21)      (11)(22)
               (1)(1)(1)  (2)(11)    (1)(21)    (1)(211)      (1)(221)
                          (1)(1)(2)  (2)(11)    (2)(111)      (21)(21)
                                     (1)(1)(2)  (1)(1)(21)    (2)(211)
                                                (1)(2)(11)    (1)(1)(22)
                                                (1)(1)(1)(2)  (1)(2)(21)
                                                              (2)(2)(11)
                                                              (1)(1)(2)(2)

Multisets of compositions are counted by A034691.
Combinatory separations of normal multisets are counted by A269134.
Dealings with total sum n are counted by A292884.
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.
- Necklaces are A065609.
- Sum is A070939.
- Runs are counted by A124767.
- Rotational symmetries are counted by A138904.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon words are A275692.
- Co-Lyndon words are A326774.
- Aperiodic compositions are A328594.
- Length of Lyndon factorization is A329312.
- Distinct rotations are counted by A333632.
- Co-Lyndon factorizations are counted by A333765.
- Lyndon factorizations are counted by A333940.
- Length of co-Lyndon factorization is A334029.
- Combinatory separations are A334030.
Cf. A000031, A000740, A001037, A008965, A027375, A059966, A060223, A211100, A328595, A328596, A333764, A333943.

nn=100;
comps[0]:={{}};comps[n_]:=Join@@Table[Prepend[#,i]&/@comps[n-i],{i,n}];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
dealings[q_]:=Union[Function[ptn,Sort[q[[#]]&/@ptn]]/@sps[Range[Length[q]]]];
Table[Length[dealings[stc[n]]],{n,0,nn}]

For n > 0, Sum_{k = 2^(n-1)..2^n-1} a(k) = A292884(n).

A211095 Length of the smallest (i.e., rightmost) Lyndon word in the Lyndon factorization of the binary representation of n.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, Mar 31 2012

nonn

See A211100 for more details.

The length of the largest (or leftmost) Lyndon word in the factorization is always 1.

			n=25 has binary expansion 11001, which has Lyndon factorization (1)(1)(001) with three factors. The rightmost factor, 001, has length 3, so a(25)=3.

N. J. A. Sloane, Maple programs

Cf. A211100, A211096-A211099.

a(2k) = 1 always (the only Lyndon word ending in 0 is 0 itself).

A211099 Largest (i.e., leftmost) Lyndon word in Lyndon factorization of binary vectors of lengths 1, 2, 3, ... (written using 1's and 2's rather than 0's and 1's, since numbers > 0 in the OEIS cannot begin with 0).

Original entry on oeis.org

1, 2, 1, 12, 2, 2, 1, 112, 12, 122, 2, 2, 2, 2, 1, 1112, 112, 1122, 12, 12, 122, 1222, 2, 2, 2, 2, 2, 2, 2, 2, 1, 11112, 1112, 11122, 112, 11212, 1122, 11222, 12, 12, 12, 12122, 122, 122, 1222, 12222, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 111112, 11112, 111122, 1112, 111212, 11122, 111222, 112, 112, 11212, 112122, 1122, 112212, 11222, 112222, 12

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,...
See A211097, A211099, A211100 for further information, including Maple code.
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.
.011.
.1.0.0.
.1.01.
.1.1.0.
.1.1.1.
.0.0.0.0.
...
The real sequence (written with 0's and 1's rather than 1's and 2's) is:
0, 1, 0, 01, 1, 1, 0, 001, 01, 011, 1, 1, 1, 1, 0, 0001, 001, 0011, 01, 01, 011, 0111, 1, 1, 1, 1, 1, 1, 1, 1, 0, 00001, 0001, 00011, 001, 00101, 0011, 00111, 01, 01, 01, 01011, 011, 011, 0111, 01111, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 000001, 00001, ...

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, Maple programs for A211097 etc.

Cf. A001037 (number of Lyndon words of length m); A102659 (list thereof), A211100.

Cf. A211095-A211099.

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

cp's OEIS Frontend

A333765 Number of co-Lyndon factorizations of the k-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A329317 Length of the Lyndon factorization of the reversed first n terms of A000002.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A334029 Length of the co-Lyndon factorization of the k-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329316 Irregular triangle read by rows where row n gives the sequence of lengths of components of the Lyndon factorization of the reversed first n terms of A000002.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A334265 Numbers k such that the k-th composition in standard order is a reversed Lyndon word.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A302291 a(n) is the period of the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A333939 Number of multisets of compositions that can be shuffled together to obtain the k-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A211095 Length of the smallest (i.e., rightmost) Lyndon word in the Lyndon factorization of the binary representation of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A211099 Largest (i.e., leftmost) Lyndon word in Lyndon factorization of binary vectors of lengths 1, 2, 3, ... (written using 1's and 2's rather than 0's and 1's, since numbers > 0 in the OEIS cannot begin with 0).

Views