| Displaying 1-6 of 6 results found.
page
1
Number of compositions of n with uniform Lyndon factorization and uniform co-Lyndon factorization.
+10
34
1, 2, 4, 7, 12, 18, 28, 40, 57, 80, 110, 148, 200, 266, 348, 457, 592, 764, 978, 1248, 1580, 2000, 2508, 3142, 3913
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).
Similarly, the co-Lyndon product is the lexicographically minimal sequence obtainable by shuffling the sequences together, and a co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product, or, equivalently, a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. For example, (1001) has sorted co-Lyndon factorization (1)(100).
A sequence of words is uniform if they all have the same length.
Conjecture: Also the number of compositions of n that are either weakly increasing or weakly decreasing. Hence a(n) = 2 * A000041(n) - A000005(n). - Gus Wiseman, Mar 05 2020
EXAMPLE
The a(1) = 1 through a(6) = 18 compositions:
(1) (2) (3) (4) (5) (6)
(11) (12) (13) (14) (15)
(21) (22) (23) (24)
(111) (31) (32) (33)
(112) (41) (42)
(211) (113) (51)
(1111) (122) (114)
(221) (123)
(311) (222)
(1112) (321)
(2111) (411)
(11111) (1113)
(1122)
(2211)
(3111)
(11112)
(21111)
(111111)
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, #]]&]]]];
colynQ[q_]:=Array[Union[{RotateRight[q, #], q}]=={RotateRight[q, #], 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, #]]&]]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], SameQ@@Length/@lynfac[#]&&SameQ@@Length/@colynfac[#]&]], {n, 10}]
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, A001523, A008965, A059204, A060223, A211100, A328596, A329312, A329318, A329396, A329397, A329399, A332578, A332669, A332834.
Number of Lyndon compositions of n whose reverse is not a co-Lyndon composition.
+10
13
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
COMMENTS
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.
EXAMPLE
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)
MATHEMATICA
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}]
CROSSREFS
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.
Number of compositions of n that are both a reversed Lyndon word and a co-Lyndon word.
+10
7
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
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.
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): - 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.
Number of non-necklace compositions of n.
+10
3
0, 0, 1, 3, 9, 19, 45, 93, 197, 405, 837, 1697, 3465, 7011, 14193, 28653, 57825, 116471, 234549, 471801, 948697, 1906407, 3829581, 7689357, 15435033, 30973005, 62137797, 124630149, 249922665, 501078345, 1004468157, 2013263853, 4034666121, 8084640465
COMMENTS
A necklace composition of n is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations.
EXAMPLE
The a(3) = 1 through a(6) = 19 compositions:
(21) (31) (32) (42)
(121) (41) (51)
(211) (131) (141)
(212) (213)
(221) (231)
(311) (312)
(1121) (321)
(1211) (411)
(2111) (1131)
(1221)
(1311)
(2112)
(2121)
(2211)
(3111)
(11121)
(11211)
(12111)
(21111)
MATHEMATICA
neckQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], !neckQ[#]&]], {n, 10}]
CROSSREFS
Numbers whose prime signature is not a necklace are A329142. Numbers whose reversed binary expansion is a necklace are A328595.
Number of compositions of n whose Lyndon and co-Lyndon factorizations both have the same length.
+10
2
1, 2, 2, 4, 4, 10, 13, 28, 46, 99, 175, 359, 672, 1358, 2627, 5238, 10262, 20438, 40320, 80137
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).
Similarly, the co-Lyndon product is the lexicographically minimal sequence obtainable by shuffling the sequences together, and a co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product, or, equivalently, a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. For example, (1001) has sorted co-Lyndon factorization (1)(100).
EXAMPLE
The a(1) = 1 through a(7) = 13 compositions:
(1) (2) (3) (4) (5) (6) (7)
(11) (111) (22) (131) (33) (151)
(121) (212) (141) (214)
(1111) (11111) (213) (232)
(222) (241)
(231) (313)
(1221) (1312)
(2112) (1321)
(11211) (2113)
(111111) (11311)
(12121)
(21112)
(1111111)
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, #]]&]]]];
colynQ[q_]:=Array[Union[{RotateRight[q, #], q}]=={RotateRight[q, #], 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, #]]&]]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Length[lynfac[#]]==Length[colynfac[#]]&]], {n, 10}]
CROSSREFS
Lyndon and co-Lyndon compositions are (both) counted by A059966. Lyndon compositions that are not weakly increasing are A329141. Lyndon compositions of n whose reverse is not co-Lyndon are A329324. Cf. A000740, A001037, A008965, A060223, A102659, A211100, A275692, A328596, A329312, A329318, A329395, A329398.
Number of compositions of n whose Lyndon factorization is uniform.
+10
2
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
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.
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.
Search completed in 0.007 seconds
|