A334269 Number of compositions of n that are both a reversed Lyndon word and a co-Lyndon word.

1, 1, 2, 3, 6, 8, 16, 23, 40, 62, 110, 169, 302, 492, 856, 1454, 2572, 4428, 7914, 13935, 25036, 44842, 81298, 147149, 268952, 491746, 904594, 1667091, 3085950, 5723367, 10652544, 19865887, 37150314, 69608939, 130723184, 245935633, 463590444, 875306913, 1655451592, 3135613649, 5948011978, 11298215516

Offset

1,3

Comments

Also the number of compositions of n that are both a Lyndon word and a reversed co-Lyndon word.

A composition of n is a finite sequence of positive integers summing to n.

A Lyndon word is a finite sequence of positive integers that is lexicographically strictly less than all of its cyclic rotations. Co-Lyndon is defined similarly, except with strictly greater instead of strictly less.

Links

Table of n, a(n) for n=1..42.

Example

The a(1) = 1 through a(7) = 16 compositions:
  (1)  (2)  (3)   (4)    (5)     (6)      (7)
            (21)  (31)   (32)    (42)     (43)
                  (211)  (41)    (51)     (52)
                         (221)   (321)    (61)
                         (311)   (411)    (322)
                         (2111)  (2211)   (331)
                                 (3111)   (421)
                                 (21111)  (511)
                                          (2221)
                                          (3121)
                                          (3211)
                                          (4111)
                                          (21211)
                                          (22111)
                                          (31111)
                                          (211111)

Mathematica

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

Crossrefs

The version for binary expansion is A334267.

Compositions of this type are ranked by A334266.

Normal sequences of this type are counted by A334270.

Necklace compositions of this type are counted by A334271.

Aperiodic compositions are counted by A000740.

Binary Lyndon words are counted by A001037.

Necklace compositions are counted by A008965.

Normal Lyndon words are counted by A060223.

Lyndon compositions are counted by A059966.

All of the following pertain to compositions in standard order (A066099):

- Lyndon words are A275692.

- Co-Lyndon words are A326774.

- Reversed Lyndon words are A334265.

- Reversed co-Lyndon words are A328596.

- Length of Lyndon factorization is A329312.

- Length of co-Lyndon factorization is A334029.

- Length of Lyndon factorization of reverse is A334297.

- Length of co-Lyndon factorization of reverse is A329313.

- Lyndon factorizations are counted by A333940.

- Co-Lyndon factorizations are counted by A333765.

- Aperiodic compositions are A328594.

- Distinct rotations are counted by A333632.

Cf. A034691, A065609, A275692, A328596, A329141, A329324, A329326, A334266, A334272, A334273, A334274.

Sequence in context: A091070 A133586 A141348 * A029867 A056348 A308546

Adjacent sequences: A334266 A334267 A334268 * A334270 A334271 A334272

Keyword

nonn

Author

Gus Wiseman, Apr 24 2020

Extensions

Offset corrected and a(21)-a(42) from Bert Dobbelaere, Apr 26 2020

Status

approved