A275692 -id:A275692 - cp's OEIS frontend

A334030 Number of combinatory separations of a multiset whose multiplicities are the parts of the n-th composition in standard order.

1, 1, 2, 2, 3, 4, 4, 3, 5, 7, 8, 8, 7, 9, 8, 5, 7, 12, 15, 14, 15, 17, 18, 13, 12, 17, 17, 16, 14, 16, 13, 7, 11, 19, 27, 26, 27, 37, 37, 25, 27, 37, 33, 34, 37, 40, 36, 22, 19, 32, 37, 33, 37, 38, 40, 28, 26, 33, 34, 30, 25, 28, 22, 11, 15, 30, 44, 42, 51, 68

Offset: 0

Gus Wiseman, Apr 16 2020

nonn

A multiset is normal if it covers an initial interval of positive integers. The type of a multiset of integers is the unique normal multiset that has the same sequence of multiplicities when its entries are taken in increasing order. For example the type of (3,3,5,5,5,6) is (1,1,2,2,2,3).

A pair h<={g_1,...,g_k} is a combinatory separation iff there exists a multiset partition of h whose multiset of block-types is {g_1,...,g_k}. For example, the (headless) combinatory separations of the multiset (1122) are (1122), (1)(112), (1)(122), (11)(11), (12)(12), (1)(1)(11), (1)(1)(12), (1)(1)(1)(1). This list excludes (12)(11), because one cannot partition (1122) into two blocks where one block has two distinct elements and the other has two equal elements.

			The combinatory separations for n = 1, 3, 5, 9, 10, 13 (heads not shown):
  (1)  (12)    (112)      (1112)        (1122)        (1223)
       (1)(1)  (1)(11)    (1)(111)      (11)(11)      (1)(112)
               (1)(12)    (1)(112)      (1)(112)      (11)(12)
               (1)(1)(1)  (11)(12)      (1)(122)      (1)(122)
                          (1)(1)(11)    (12)(12)      (1)(123)
                          (1)(1)(12)    (1)(1)(11)    (12)(12)
                          (1)(1)(1)(1)  (1)(1)(12)    (1)(1)(11)
                                        (1)(1)(1)(1)  (1)(1)(12)
                                                      (1)(1)(1)(1)

Multisets of compositions are A034691.
The described multiset is a row of A095684.
Combinatory separations of normal multisets are A269134.
Shuffles of compositions are counted by A292884.
Combinatory separations of prime indices are A318559.
The version for prime indices is A318560.
Combinatory separations of strongly normal multisets are A318563.
Multiset partitions of the described multiset are A333942.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Sum is A070939.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Length of Lyndon factorization is A329312.
- Dealings are counted by A333939.
Cf. A065609, A275692, A318284, A326774, A333764, A333765, A333940.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
normize[m_]:=m/.Rule@@@Table[{Union[m][[i]],i},{i,Length[Union[m]]}];
ptnToNorm[y_]:=Join@@Table[ConstantArray[i,y[[i]]],{i,Length[y]}];
Table[Length[Union[Table[Sort[normize/@m],{m,mps[ptnToNorm[stc[n]]]}]]],{n,0,100}]

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

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Apr 13 2020

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 factorization of a composition c is a multiset of compositions whose 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 Lyndon-word factorization of the n-th composition in standard order.

			We have  a(300) = 5, because the 300th composition (3,2,1,3) has the following Lyndon factorizations:
  ((3,2,1,3))
  ((1,3),(3,2))
  ((2),(3,1,3))
  ((3),(2,1,3))
  ((2),(3),(1,3))

The dual version is A333765.
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.
- Dealing are counted by A333939.
- Reversed necklaces are A333943.
- Length of co-Lyndon factorization is A334029.
- Combinatory separations are A334030.
Cf. A000740, A001037, A034691, A060223, A269134, A292884, A328596.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
lynprod[]:={};lynprod[{},b_List]:=b;lynprod[a_List,{}]:=a;lynprod[a_List]:=a;
lynprod[{x_,a___},{y_,b___}]:=Switch[Ordering[If[x=!=y,{x,y},{lynprod[{a},{x,b}],lynprod[{x,a},{b}]}]],{2,1},Prepend[lynprod[{a},{y,b}],x],{1,2},Prepend[lynprod[{x,a},{b}],y]];
lynprod[a_List,b_List,c__List]:=lynprod[a,lynprod[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]],lynprod@@#==stc[n]&]],{n,0,100}]

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

A329314 Irregular triangle read by rows where row n gives the lengths of the components in the Lyndon factorization of the binary expansion of n.

Original entry on oeis.org

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

Offset: 0

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

			Triangle begins:
   0: ()         20: (1211)      40: (12111)     60: (111111)
   1: (1)        21: (122)       41: (123)       61: (11112)
   2: (11)       22: (131)       42: (1221)      62: (111111)
   3: (11)       23: (14)        43: (15)        63: (111111)
   4: (111)      24: (11111)     44: (1311)      64: (1111111)
   5: (12)       25: (113)       45: (132)       65: (16)
   6: (111)      26: (1121)      46: (141)       66: (151)
   7: (111)      27: (113)       47: (15)        67: (16)
   8: (1111)     28: (11111)     48: (111111)    68: (1411)
   9: (13)       29: (1112)      49: (114)       69: (16)
  10: (121)      30: (11111)     50: (1131)      70: (151)
  11: (13)       31: (11111)     51: (114)       71: (16)
  12: (1111)     32: (111111)    52: (11211)     72: (13111)
  13: (112)      33: (15)        53: (1122)      73: (133)
  14: (1111)     34: (141)       54: (1131)      74: (151)
  15: (1111)     35: (15)        55: (114)       75: (16)
  16: (11111)    36: (1311)      56: (111111)    76: (1411)
  17: (14)       37: (15)        57: (1113)      77: (16)
  18: (131)      38: (141)       58: (11121)     78: (151)
  19: (14)       39: (15)        59: (1113)      79: (16)

Row lengths are A211100.
Row sums are A029837, or, if the first term is 1, A070939.
Ignoring the first digit gives A329325.
Positions of rows of length 2 are A329327.
Binary Lyndon words are counted by A001037 and ranked by A102659.
Numbers whose reversed binary expansion is a Lyndon word are A328596.
Length of the co-Lyndon factorization of the binary expansion is A329312.
Cf. A059966, A211097, A275692, A296372, A329313, A329315, A329318.

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]]&]]]];
Table[Length/@lynfac[If[n==0,{},IntegerDigits[n,2]]],{n,0,50}]

A329324 Number of Lyndon compositions of n whose reverse is not a co-Lyndon composition.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 2, 7, 16, 37, 76, 166, 328, 669, 1326, 2626, 5138, 10104, 19680, 38442, 74822, 145715, 283424, 551721, 1073224

Offset: 1

Gus Wiseman, Nov 11 2019

A Lyndon composition of n is a finite sequence summing to n that is lexicographically strictly less than all of its cyclic rotations. A co-Lyndon composition of n is a finite sequence summing to n that is lexicographically strictly greater than all of its cyclic rotations.

			The a(6) = 1 through a(9) = 16 compositions:
  (132)  (142)   (143)    (153)
         (1132)  (152)    (162)
                 (1142)   (243)
                 (1232)   (1143)
                 (1322)   (1152)
                 (11132)  (1242)
                 (11312)  (1332)
                          (1422)
                          (11142)
                          (11232)
                          (11322)
                          (11412)
                          (12132)
                          (111132)
                          (111312)
                          (112212)

Lyndon and co-Lyndon compositions are counted by A059966.
Numbers whose reversed binary expansion is Lyndon are A328596.
Numbers whose binary expansion is co-Lyndon are A275692.
Lyndon compositions that are not weakly increasing are A329141.
Cf. A000740, A001037, A008965, A060223, A102659, A211100, A329131, A329312, A329313, A329318, A329326.

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

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

A329325 Irregular triangle read by rows where row n gives the lengths of the components in the Lyndon factorization of the binary expansion of n with first digit removed.

Original entry on oeis.org

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

Offset: 1

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

			Triangle begins:
   1: ()        21: (22)       41: (23)       61: (1112)
   2: (1)       22: (31)       42: (221)      62: (11111)
   3: (1)       23: (4)        43: (5)        63: (11111)
   4: (11)      24: (1111)     44: (311)      64: (111111)
   5: (2)       25: (13)       45: (32)       65: (6)
   6: (11)      26: (121)      46: (41)       66: (51)
   7: (11)      27: (13)       47: (5)        67: (6)
   8: (111)     28: (1111)     48: (11111)    68: (411)
   9: (3)       29: (112)      49: (14)       69: (6)
  10: (21)      30: (1111)     50: (131)      70: (51)
  11: (3)       31: (1111)     51: (14)       71: (6)
  12: (111)     32: (11111)    52: (1211)     72: (3111)
  13: (12)      33: (5)        53: (122)      73: (33)
  14: (111)     34: (41)       54: (131)      74: (51)
  15: (111)     35: (5)        55: (14)       75: (6)
  16: (1111)    36: (311)      56: (11111)    76: (411)
  17: (4)       37: (5)        57: (113)      77: (6)
  18: (31)      38: (41)       58: (1121)     78: (51)
  19: (4)       39: (5)        59: (113)      79: (6)
  20: (211)     40: (2111)     60: (11111)    80: (21111)
For example, the trimmed binary expansion of 41 is (01001), with Lyndon factorization (01)(001), so row 41 is {2,3}.

Row lengths are A211097.
Row sums are A000523.
Keeping the first digit gives A329314.
Positions of singleton rows are A329327.
Binary Lyndon words are counted by A001037 and ranked by A102659.
Numbers whose reversed binary expansion is a Lyndon word are A328596.
Length of the co-Lyndon factorization of the binary expansion is A329312.
Cf. A059966, A211097, A257250, A275692, A296372, A328594, A329313, A329315, A329318.

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]]&]]]];
Table[Length/@lynfac[Rest[IntegerDigits[n,2]]],{n,100}]

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

Original entry on oeis.org

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

A095684 Triangle read by rows. There are 2^(m-1) rows of length m, for m = 1, 2, 3, ... The rows are in lexicographic order. The rows have the property that the first entry is 1, the second distinct entry (reading from left to right) is 2, the third distinct entry is 3, etc.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Jun 25 2004

Row k is the unique multiset that covers an initial interval of positive integers and has multiplicities equal to the parts of the k-th composition in standard order (graded reverse-lexicographic, A066099). This composition 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. For example, the 13th composition is (1,2,1), so row 13 is {1,2,2,3}. - Gus Wiseman, Apr 26 2020

			1, 11, 12, 111, 112, 122, 123, 1111, 1112, 1122, 1123, 1222, 1223, 1233, ...
The 8 strings of length 4 are 1111, 1112, 1122, 1123, 1222, 1223, 1233, 1234.
From _Gus Wiseman_, Apr 26 2020: (Start)
The triangle read by columns begins:
  1:{1}  2:{1,1}  4:{1,1,1}   8:{1,1,1,1}  16:{1,1,1,1,1}
         3:{1,2}  5:{1,1,2}   9:{1,1,1,2}  17:{1,1,1,1,2}
                  6:{1,2,2}  10:{1,1,2,2}  18:{1,1,1,2,2}
                  7:{1,2,3}  11:{1,1,2,3}  19:{1,1,1,2,3}
                             12:{1,2,2,2}  20:{1,1,2,2,2}
                             13:{1,2,2,3}  21:{1,1,2,2,3}
                             14:{1,2,3,3}  22:{1,1,2,3,3}
                             15:{1,2,3,4}  23:{1,1,2,3,4}
                                           24:{1,2,2,2,2}
                                           25:{1,2,2,2,3}
                                           26:{1,2,2,3,3}
                                           27:{1,2,2,3,4}
                                           28:{1,2,3,3,3}
                                           29:{1,2,3,3,4}
                                           30:{1,2,3,4,4}
                                           31:{1,2,3,4,5}
(End)

J. C. Kieffer, W. Szpankowski and E.-H. Yang, Problems on sequences: information theory and computer science interface, IEEE Trans. Inform. Theory, 50 (No. 7, 2004), 1385-1392.

See A096299 for another version.
The number of distinct parts in row n is A000120(n), also the maximum part.
Row sums are A029931.
Heinz numbers of rows are A057335.
Row lengths are A070939.
Row products are A284001.
The version for prime indices is A305936.
There are A333942(n) multiset partitions of row n.
Multisets of compositions are counted by A034691.
Combinatory separations of normal multisets are A269134.
All of the following pertain to compositions in standard order (A066099):
- Necklaces are A065609.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon words are A275692.
- Dealings are counted by A333939.
- Distinct parts are counted by A334028.
Cf. A318284, A333764, A333940, A334030.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
ptnToNorm[y_]:=Join@@Table[ConstantArray[i,y[[i]]],{i,Length[y]}];
Table[ptnToNorm[stc[n]],{n,15}] (* Gus Wiseman, Apr 26 2020 *)

A257250 Numbers n for which A256999(n) = n; numbers that cannot be made any larger by rotating (by one or more steps) the non-msb bits of their binary representation (with A080541 or A080542).

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 8, 12, 14, 15, 16, 24, 26, 28, 30, 31, 32, 48, 52, 56, 58, 60, 62, 63, 64, 96, 100, 104, 106, 112, 114, 116, 118, 120, 122, 124, 126, 127, 128, 192, 200, 208, 212, 224, 226, 228, 232, 234, 236, 240, 242, 244, 246, 248, 250, 252, 254, 255, 256, 384, 392, 400, 416, 420, 424, 426, 448, 450

Offset: 0

Antti Karttunen, May 16 2015

These correspond to the maximal (lexicographically largest) representatives selected from each equivalence class of binary necklaces. See the last example.
Indexing starts from zero, because a(0) = 0 is a special case.
If k is a member then so also is 2*k, i.e., k with 0 appended to the end of its binary representation.
If k is a member then so also is A004755(k), i.e., k with 1 prepended to the front of its binary representation.
One obtains A065609 if one erases the most significant bit of each term [as A053645(a(n))] and then discards any zero-terms produced from the terms that originally were powers of two (A000079).
First differs from A328607 in lacking 108, with binary expansion 1101100. If we define a dual-necklace to be a finite sequence that is lexicographically maximal (not minimal) among all of its cyclic rotations, these are numbers whose binary expansion, without the most significant digit, is a dual-necklace. - Gus Wiseman, Nov 04 2019

			For n = 5, with binary representation "101", if we rotate other bits than the most significant bit (that is, only the two rightmost digits "01") one step to either direction, we get "110" = 6 > 5, so 5 can be made larger by such rotations, and thus is NOT included in this sequence.
For n = 6, with binary representation "110", no such rotation will yield a larger number, and thus 6 is included in this sequence.
For n = 28, with binary representation "11100", if we rotate non-msb bits towards right, we get additional numbers 22, 19 and 25 (with binary representations "10110", "10011", "11001") before coming to 28 again, and 28 is the largest of these numbers, thus 28 is included in this sequence.
  Also, if we discard the most significant bit of each and consider them just as binary strings, then A053645(28) = 12 is the lexicographically largest representative of {"1100", "0110", "0011", "1001"}, which is the complete set of representatives for a particular equivalence class of binary necklaces, obtained by rotating all bits of binary string "1100" successively towards right or left.

Antti Karttunen, Table of n, a(n) for n = 0..16637
Wikipedia, Necklace (combinatorics)
Index entries for sequences related to necklaces

Complement: A257739.
Odd terms: A000225.
Subsequence of A065609.
Cf. A004755, A053645, A080541, A080542, A256999.
Subsequence: A258003.
The non-dual version is A328668.
The version involving all digits is A065609.
The non-dual reversed version is A328607.
Numbers whose reversed binary expansion is a necklace are A328595.
Binary necklaces are A000031.
Necklace compositions are A008965.
Cf. A000120, A001037, A003714, A014081, A069010, A275692, A328594, A328596.

reckQ[q_]:=Array[OrderedQ[{RotateRight[q,#],q}]&,Length[q]-1,1,And];
Select[Range[0,110],#<=1||reckQ[Rest[IntegerDigits[#,2]]]&] (* Gus Wiseman, Nov 04 2019 *)

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

A284001 a(n) = A005361(A283477(n)).

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 4, 6, 1, 2, 4, 6, 8, 12, 18, 24, 1, 2, 4, 6, 8, 12, 18, 24, 16, 24, 36, 48, 54, 72, 96, 120, 1, 2, 4, 6, 8, 12, 18, 24, 16, 24, 36, 48, 54, 72, 96, 120, 32, 48, 72, 96, 108, 144, 192, 240, 162, 216, 288, 360, 384, 480, 600, 720, 1, 2, 4, 6, 8, 12, 18, 24, 16, 24, 36, 48, 54, 72, 96, 120, 32, 48, 72, 96, 108, 144, 192, 240, 162, 216, 288, 360, 384, 480

Offset: 0

Antti Karttunen, Mar 18 2017

a(n) is the product of elements of the multiset that covers an initial interval of positive integers with multiplicities equal to the parts of the n-th composition in standard order (graded reverse-lexicographic, A066099). This composition is obtained by taking the set of positions of 1's in the reversed binary expansion of n, prepending 0, taking first differences, and reversing again. For example, the 13th composition is (1,2,1) giving the multiset {1,2,2,3} with product 12, so a(13) = 12. - Gus Wiseman, Apr 26 2020

Antti Karttunen, Table of n, a(n) for n = 0..8191
Index entries for sequences related to binary expansion of n

Cf. A005361, A283477, A284002, A284005.
Row products of A095684.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Weighted sum is A029931.
- Necklaces are A065609.
- Sum is A070939.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon words are A275692.
- Distinct parts are counted by A334028.
Cf. A003963, A034691, A053645, A057335, A305936, A318284, A333764, A333940, A333942, A334030.

Table[Times @@ FactorInteger[#][[All, -1]] &[Times @@ Map[#1^#2 & @@ # &, FactorInteger[#] /. {p_, e_} /; e == 1 :> {Times @@ Prime@ Range@ PrimePi@ p, e}] &[Times @@ Prime@ Flatten@ Position[#, 1] &@ Reverse@ IntegerDigits[n, 2]]], {n, 0, 93}] (* Michael De Vlieger, Mar 18 2017 *)

A005361(n) = factorback(factor(n)[, 2]); \\ From A005361
A034386(n) = prod(i=1, primepi(n), prime(i));
A108951(n) = { my(f=factor(n)); prod(i=1, #f~, A034386(f[i, 1])^f[i, 2]) };  \\ From A108951
A019565(n) = {my(j,v); factorback(Mat(vector(if(n, #n=vecextract(binary(n), "-1..1")), j, [prime(j), n[j]])~))}; \\ From A019565
A283477(n) = A108951(A019565(n));
A284001(n) = A005361(A283477(n));

(define (A284001 n) (A005361 (A283477 n)))

a(n) = A005361(A283477(n)).
a(n) = A003963(A057335(n)). - Gus Wiseman, Apr 26 2020
a(n) = A284005(A053645(n)) for n > 0 with a(0) = 1. - Mikhail Kurkov, Jun 05 2021 [verification needed]

cp's OEIS Frontend

A334030 Number of combinatory separations of a multiset whose multiplicities are the parts of the n-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A329314 Irregular triangle read by rows where row n gives the lengths of the components in the Lyndon factorization of the binary expansion of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A329324 Number of Lyndon compositions of n whose reverse is not a co-Lyndon composition.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A329325 Irregular triangle read by rows where row n gives the lengths of the components in the Lyndon factorization of the binary expansion of n with first digit removed.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A095684 Triangle read by rows. There are 2^(m-1) rows of length m, for m = 1, 2, 3, ... The rows are in lexicographic order. The rows have the property that the first entry is 1, the second distinct entry (reading from left to right) is 2, the third distinct entry is 3, etc.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A257250 Numbers n for which A256999(n) = n; numbers that cannot be made any larger by rotating (by one or more steps) the non-msb bits of their binary representation (with A080541 or A080542).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views