|
| |
|
|
A334029
|
|
Length of the co-Lyndon factorization of the k-th composition in standard order.
|
|
11
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
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.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
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.
|
|
|
MATHEMATICA
|
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}]
|
|
|
CROSSREFS
|
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):
- Rotational symmetries are counted by A138904.
- Constant compositions are A272919.
- Co-Lyndon compositions are A326774.
- Aperiodic compositions are A328594.
- Reversed co-necklaces are A328595.
- Co-Lyndon factorizations are counted by A333765.
- Lyndon factorizations are counted by A333940.
Cf. A034691, A060223, A102659, A211097, A292884, A296372, A328596, A329358, A329359, A329362, A329400, A329401, A333939.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
