A059966 -id:A059966 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Dec 18 2017

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

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

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[{#1,#2}]]&],{n,7}]

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

A329740 Number of compositions of n whose multiplicities are distinct and cover an initial interval of positive integers.

Original entry on oeis.org

1, 1, 1, 1, 4, 7, 4, 10, 10, 10, 73, 196, 133, 379, 319, 379, 502, 805, 562, 1108, 13648, 51448, 51691, 115174, 140011, 178597, 203617, 329737, 292300, 456703, 456160, 608386, 633466, 898186, 823009, 39014392, 190352269, 266293795, 493345615, 834326995, 947714938

Offset: 0

Gus Wiseman, Nov 21 2019

nonn

A composition of n is a finite sequence of positive integers with sum n.

			The a(1) = 1 through a(9) = 10 compositions:
  (1)  (2)  (3)  (4)      (5)      (6)      (7)      (8)      (9)
                 (1,1,2)  (1,1,3)  (1,1,4)  (1,1,5)  (1,1,6)  (1,1,7)
                 (1,2,1)  (1,2,2)  (1,4,1)  (1,3,3)  (1,6,1)  (1,4,4)
                 (2,1,1)  (1,3,1)  (4,1,1)  (1,5,1)  (2,2,4)  (1,7,1)
                          (2,1,2)           (2,2,3)  (2,3,3)  (2,2,5)
                          (2,2,1)           (2,3,2)  (2,4,2)  (2,5,2)
                          (3,1,1)           (3,1,3)  (3,2,3)  (4,1,4)
                                            (3,2,2)  (3,3,2)  (4,4,1)
                                            (3,3,1)  (4,2,2)  (5,2,2)
                                            (5,1,1)  (6,1,1)  (7,1,1)

The version allowing repeated multiplicities is A329741.
Complete compositions are A107429.
Compositions whose multiplicities are distinct are A242882.
Cf. A059966, A098504, A244164, A274174, A329739, A329766, A329748.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Range[Length[Union[#]]]==Sort[Length/@Split[Sort[#]]]&]],{n,0,10}]

a(21)-a(40) from Alois P. Heinz, Nov 21 2019

A318731 Number of relatively prime Lyndon compositions (aperiodic necklaces of positive integers) with sum n.

Original entry on oeis.org

1, 0, 1, 2, 5, 7, 17, 27, 54, 93, 185, 324, 629, 1143, 2175, 4050, 7709, 14469, 27593, 52276, 99839, 190371, 364721, 698508, 1342170, 2580165, 4970952, 9585232, 18512789, 35787985, 69273665, 134211600, 260300799, 505278705, 981706783

Offset: 1

Gus Wiseman, Sep 02 2018

nonn

			The a(6) = 7 relatively prime Lyndon compositions are 15, 114, 132, 123, 1113, 1122, 11112.
The a(7) = 17 relatively prime Lyndon compositions:
  16, 25, 34,
  115, 142, 124, 133, 223,
  1114, 1213, 1132, 1123, 1222,
  11113, 11212, 11122,
  111112.

Cf. A000740, A000837, A008965, A059966, A100953, A296302.

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

Moebius transform of A059966. Second Moebius transform of A008965.

A318748 Number of integer compositions of n that have only one part or whose consecutive parts are coprime and the last and first part are also coprime.

Original entry on oeis.org

1, 1, 2, 4, 7, 13, 24, 43, 82, 151, 285, 535, 1005, 1883, 3533, 6631, 12460, 23407, 43952, 82538, 154999, 291088, 546674, 1026687, 1928118, 3621017, 6800300, 12771086, 23984329, 45042959, 84591339, 158863807, 298348613, 560303342, 1052258402, 1976157510

Offset: 0

Gus Wiseman, Sep 02 2018

nonn

			The a(5) = 13 compositions with adjacent parts coprime:
  (5)
  (41) (14) (32) (23)
  (311) (131) (113)
  (2111) (1211) (1121) (1112)
  (11111)
Missing from this list are (221), (212), and (122).

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

Cf. A000740, A008965, A059966, A100953, A167606, A296302, A318726, A318727, A318728, A318745, A328609.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Or[Length[#]==1,And@@CoprimeQ@@@Partition[#,2,1,1]]&]],{n,20}]

b(n, q, pred)={my(M=matrix(n, n)); for(k=1, n, M[k, k]=pred(q, k); for(i=1, k-1, M[i, k]=sum(j=1, k-i, if(pred(j, i), M[j, k-i], 0)))); M[q, ]}
seq(n)={concat([1], vector(n, i, i > 1) + sum(k=1, n, b(n, k, (i, j)->gcd(i, j)==1)))} \\ Andrew Howroyd, Nov 01 2019

a(n) = A328609(n) + 1 for n > 1. - Andrew Howroyd, Nov 01 2019

a(21)-a(35) from Alois P. Heinz, Sep 02 2018

Name corrected by Gus Wiseman, Nov 04 2019

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

A342495 Number of compositions of n with constant (equal) first quotients.

Original entry on oeis.org

1, 1, 2, 4, 5, 6, 8, 10, 10, 11, 12, 12, 16, 16, 18, 20, 19, 18, 22, 22, 24, 28, 24, 24, 30, 27, 30, 30, 34, 30, 38, 36, 36, 36, 36, 40, 43, 40, 42, 46, 48, 42, 52, 46, 48, 52, 48, 48, 56, 55, 54, 54, 58, 54, 60, 58, 64, 64, 60, 60, 72, 64, 68, 74, 69, 72, 72

Offset: 0

Gus Wiseman, Mar 17 2021

nonn

The first quotients of a sequence are defined as if the sequence were an increasing divisor chain, so for example the first quotients of (6,3,1) are (1/2,1/3).

			The composition (1,2,4,8) has first quotients (2,2,2) so is counted under a(15).
The composition (4,5,6) has first quotients (5/4,6/5) so is not counted under a(15).
The a(1) = 1 through a(7) = 10 compositions:
  (1)  (2)   (3)    (4)     (5)      (6)       (7)
       (11)  (12)   (13)    (14)     (15)      (16)
             (21)   (22)    (23)     (24)      (25)
             (111)  (31)    (32)     (33)      (34)
                    (1111)  (41)     (42)      (43)
                            (11111)  (51)      (52)
                                     (222)     (61)
                                     (111111)  (124)
                                               (421)
                                               (1111111)

Eric Weisstein's World of Mathematics, Logarithmically Concave Sequence.
Gus Wiseman, Sequences counting and ranking partitions and compositions by their differences and quotients.

The version for differences instead of quotients is A175342.
The unordered version is A342496, ranked by A342522.
The strict unordered version is A342515.
The distinct version is A342529.
A000005 counts constant compositions.
A000009 counts strictly increasing (or strictly decreasing) compositions.
A000041 counts weakly increasing (or weakly decreasing) compositions.
A003238 counts chains of divisors summing to n - 1 (strict: A122651).
A167865 counts strict chains of divisors > 1 summing to n.
Cf. A002843, A003242, A008965, A048004, A059966, A074206, A167606, A253249, A318991, A318992, A325557, A342528.

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

a(n > 0) = 2*A342496(n) - A000005(n).

cp's OEIS Frontend

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

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

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A329740 Number of compositions of n whose multiplicities are distinct and cover an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A318731 Number of relatively prime Lyndon compositions (aperiodic necklaces of positive integers) with sum n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A318748 Number of integer compositions of n that have only one part or whose consecutive parts are coprime and the last and first part are also coprime.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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.