A329397 Number of compositions of n whose Lyndon factorization is uniform.

1, 2, 4, 7, 12, 20, 33, 55, 92, 156, 267, 466, 822, 1473, 2668, 4886, 9021, 16786, 31413, 59101, 111654, 211722, 402697, 768025, 1468170, 2812471, 5397602, 10376418, 19978238, 38519537, 74365161, 143742338, 278156642, 538831403, 1044830113, 2027879831

Offset

1,2

Comments

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

A sequence of words is uniform if they all have the same length.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1000

Formula

G.f.: Sum_{r>=1} (exp(Sum_{k>=1} B(r, x^k)/k) - 1) where B(r, x) = (Sum_{d|r} mu(d)/(1 - x^d)^(r/d))*x^r/r. - Andrew Howroyd, Feb 03 2022

Example

The a(1) = 1 through a(6) = 20 Lyndon factorizations:
  (1)  (2)     (3)        (4)           (5)              (6)
       (1)(1)  (12)       (13)          (14)             (15)
               (2)(1)     (112)         (23)             (24)
               (1)(1)(1)  (2)(2)        (113)            (114)
                          (3)(1)        (122)            (123)
                          (2)(1)(1)     (1112)           (132)
                          (1)(1)(1)(1)  (3)(2)           (1113)
                                        (4)(1)           (1122)
                                        (2)(2)(1)        (3)(3)
                                        (3)(1)(1)        (4)(2)
                                        (2)(1)(1)(1)     (5)(1)
                                        (1)(1)(1)(1)(1)  (11112)
                                                         (12)(12)
                                                         (2)(2)(2)
                                                         (3)(2)(1)
                                                         (4)(1)(1)
                                                         (2)(2)(1)(1)
                                                         (3)(1)(1)(1)
                                                         (2)(1)(1)(1)(1)
                                                         (1)(1)(1)(1)(1)(1)

Mathematica

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, #]]&]]]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], SameQ@@Length/@lynfac[#]&]], {n, 10}]

Prog

(PARI) EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
B(n, k) = {sumdiv(n, d, moebius(d)/(1-x^d)^(n/d) + O(x*x^k))/n}
seq(n) = {sum(d=1, n-1, my(v=Vec(B(d, n-d), -n)); EulerT(v))} \\ Andrew Howroyd, Feb 03 2022

Crossrefs

Lyndon and co-Lyndon compositions are (both) counted by A059966.

Lyndon compositions that are not weakly increasing are A329141.

Lyndon compositions whose reverse is not co-Lyndon are A329324.

Cf. A000740, A001037, A008965, A060223, A102659, A211100, A275692, A328596, A329312, A329318, A329395, A329396, A329398, A329399.

Sequence in context: A179111 A093607 A005182 * A172524 A094925 A289168

Adjacent sequences: A329394 A329395 A329396 * A329398 A329399 A329400

Keyword

nonn

Author

Gus Wiseman, Nov 13 2019

Extensions

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

Terms a(26) and beyond from Andrew Howroyd, Feb 03 2022

Status

approved