A228369 -id:A228369 - cp's OEIS frontend

A296373 Triangle T(n,k) = number of compositions of n whose factorization into Lyndon words (aperiodic necklaces) is of length k.

1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 6, 5, 3, 1, 1, 9, 12, 6, 3, 1, 1, 18, 21, 14, 6, 3, 1, 1, 30, 45, 27, 15, 6, 3, 1, 1, 56, 84, 61, 29, 15, 6, 3, 1, 1, 99, 170, 120, 67, 30, 15, 6, 3, 1, 1, 186, 323, 254, 136, 69, 30, 15, 6, 3, 1, 1, 335, 640, 510, 295, 142, 70, 30, 15, 6, 3, 1, 1

Offset: 1

Gus Wiseman, Dec 11 2017

			Triangle begins:
    1;
    1,   1;
    2,   1,   1;
    3,   3,   1,   1;
    6,   5,   3,   1,   1;
    9,  12,   6,   3,   1,   1;
   18,  21,  14,   6,   3,   1,   1;
   30,  45,  27,  15,   6,   3,   1,   1;
   56,  84,  61,  29,  15,   6,   3,   1,   1;
   99, 170, 120,  67,  30,  15,   6,   3,   1,   1;
  186, 323, 254, 136,  69,  30,  15,   6,   3,   1,   1;
  335, 640, 510, 295, 142,  70,  30,  15,   6,   3,   1,   1;

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Wikipedia, Lyndon word: Standard factorization

Cf. A000740, A001045, A008965, A019536, A059966, A060223, A185700, A228369, A232472, A277427, A281013, A296302, A296372.

neckQ[q_]:=Array[OrderedQ[{RotateRight[q,#],q}]&,Length[q]-1,1,And];
aperQ[q_]:=UnsameQ@@Table[RotateRight[q,k],{k,Length[q]}];
qit[q_]:=If[#===Length[q],{q},Prepend[qit[Drop[q,#]],Take[q,#]]]&[Max@@Select[Range[Length[q]],neckQ[Take[q,#]]&&aperQ[Take[q,#]]&]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[qit[#]]===k&]],{n,12},{k,n}]

EulerMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
A(n)=[Vecrev(p/y) | p<-EulerMT(y*vector(n, n, sumdiv(n, d, moebius(n/d) * (2^d-1))/n))]
{ my(T=A(12)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Dec 01 2018

First column is A059966.

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

A296772 Triangle read by rows in which row n lists the compositions of n ordered first by decreasing length and then reverse-lexicographically.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Dec 20 2017

The ordering of compositions in each row is consistent with the reverse-Mathematica ordering of expressions (cf. A124734).

Length of k-th composition is A124748(k-1)+1. - Andrey Zabolotskiy, Dec 20 2017

			Triangle of compositions begins:
(1),
(11),(2),
(111),(21),(12),(3),
(1111),(211),(121),(112),(31),(22),(13),(4),
(11111),(2111),(1211),(1121),(1112),(311),(221),(212),(131),(122),(113),(41),(32),(23),(14),(5).

Cf. A066099, A101211, A108730, A124734, A124748, A228369, A281013, A294859, A296302, A296656, A296773, A296774.

Table[Reverse[Sort[Join@@Permutations/@IntegerPartitions[n]]],{n,6}]

A296773 Triangle read by rows in which row n lists the compositions of n ordered first by decreasing length and then lexicographically.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Dec 20 2017

			Triangle of compositions begins:
(1),
(11),(2),
(111),(12),(21),(3),
(1111),(112),(121),(211),(13),(22),(31),(4),
(11111),(1112),(1121),(1211),(2111),(113),(122),(131),(212),(221),(311),(14),(23),(32),(41),(5).

Cf. A066099, A101211, A108730, A124734, A228369, A281013, A294859, A296302, A296656, A296772, A296774.

Table[Sort[Join@@Permutations/@IntegerPartitions[n],Or[Length[#1]>Length[#2],Length[#1]===Length[#2]&&OrderedQ[{#1,#2}]]&],{n,6}]

A108244 Triangle read by rows: row n gives list of all compositions of n ordered first by decreasing length, then by reverse colexicographical order.

Original entry on oeis.org

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

Offset: 1

Hugo van der Sanden, Jun 20 2005

An example of a sequence which contains all finite sequences of positive integers as subsequences.
From Andrey Zabolotskiy, May 18 2018: (Start)
At first, the ordering within the compositions of fixed length coincides with the lexicographical order (which is the case of A228369), but for n = 5 the partitions {2, 1, 2}, {1, 3, 1}, {2, 2, 1} go in this order because the order becomes reverse lexicographical when they are reversed (read right-to-left): {2, 1, 2}, {1, 3, 1}, {1, 2, 2}.
Length of k-th composition is A124748(k-1)+1.
Reversing every composition gives A296772. (End)

			The first 5 rows are:
{1}
{1, 1}, {2}
{1, 1, 1}, {1, 2}, {2, 1}, {3}
{1, 1, 1, 1}, {1, 1, 2}, {1, 2, 1}, {2, 1, 1}, {1, 3}, {2, 2}, {3, 1}, {4}
{1, 1, 1, 1, 1}, {1, 1, 1, 2}, {1, 1, 2, 1}, {1, 2, 1, 1}, {2, 1, 1, 1}, {1, 1, 3}, {1, 2, 2}, {2, 1, 2}, {1, 3, 1}, {2, 2, 1}, {3, 1, 1}, {1, 4}, {2, 3}, {3, 2}, {4, 1}, {5}

Eric Weisstein's World of Mathematics, Combinatorial composition

Cf. A045623, A124748.

Triangles of compositions: A066099 (main entry for compositions; similar to the Mathematica ordering for partitions, A080577), A124734 (similar to the Abramowitz & Stegun ordering for partitions, A036036), and this sequence (similar to the Maple partition ordering, A080576), A296772.

Flatten[ Table[ Reverse[ # ] & /@ Reverse[ Sort[ Flatten[ Permutations[ # ] & /@ Partitions[ n], 1]]], {n, 6}]] (* Robert G. Wilson v, Jun 22 2005 *)

More terms from Robert G. Wilson v, Jun 22 2005

Name corrected by Andrey Zabolotskiy, May 18 2018

A299151 Numerators of the positive solution to 2^(n-1) = Sum_{d|n} a(d) * a(n/d).

Original entry on oeis.org

1, 1, 2, 7, 8, 14, 32, 121, 126, 248, 512, 1003, 2048, 4064, 8176, 130539, 32768, 65382, 131072, 261868, 524224, 1048064, 2097152, 4193131, 8388576, 16775168, 33554180, 67104688, 134217728, 268426672, 536870912, 8589802359, 2147482624, 4294934528, 8589934336, 17179801257, 34359738368, 68719345664, 137438949376, 274877643724, 549755813888

Offset: 1

Gus Wiseman, Feb 03 2018

Numerators of rational valued sequence f whose Dirichlet convolution with itself yields function g(n) = A000079(n-1) = 2^(n-1). - Antti Karttunen, Aug 10 2018

			Sequence begins: 1, 1, 2, 7/2, 8, 14, 32, 121/2, 126, 248, 512, 1003, 2048, 4064, 8176, 130539/8, 32768.

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

Cf. A000005, A000010, A000740, A018804, A023900, A029935, A034691, A046643, A059966, A228369, A257098, A296302, A298971, A299119, A299149, A299152.

Cf. also A317831.

nn=50;
sys=Table[2^(n-1)==Sum[a[d]*a[n/d],{d,Divisors[n]}],{n,nn}];
Numerator[Array[a,nn]/.Solve[sys,Array[a,nn]][[2]]]

A299151perA299152(n) = if(1==n,n,(2^(n-1)-sumdiv(n,d,if((d>1)&&(dA299151perA299152(d)*A299151perA299152(n/d),0)))/2);
A299151(n) = numerator(A299151perA299152(n));

More terms from Antti Karttunen, Jul 29 2018

A187816 Triangle read by rows in which row n lists the first 2^(n-1) terms of A006519 in nonincreasing order, n >= 1.

Original entry on oeis.org

1, 2, 1, 4, 2, 1, 1, 8, 4, 2, 2, 1, 1, 1, 1, 16, 8, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 32, 16, 8, 8, 4, 4, 4, 4, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 64, 32, 16, 16, 8, 8, 8, 8, 4, 4, 4, 4, 4, 4, 4, 4, 2, 2, 2, 2, 2

Offset: 1

Omar E. Pol, Sep 10 2013

T(n,k) is also the number of parts in the k-th largest region of the diagram of regions of the set of compositions of n, n >= 1, k >= 1, see example.
Row lengths is A000079.
Row sums give A001792(n-1).

			For n = 5 the diagram of regions of the set of compositions of 5 has 2^(5-1) regions, see below:
------------------------------------------------------
.          A006519
.         as a tree
.         of number        Diagram
Region    of parts       of regions     Composition
------------------------------------------------------
.                         _ _ _ _ _
1      | 1          |    |_| | | | |    1, 1, 1, 1, 1
2      |   2        |    |_ _| | | |    2, 1, 1, 1
3      | 1          |    |_|   | | |    1, 2, 1, 1
4      |      4     |    |_ _ _| | |    3, 1, 1
5      | 1          |    |_| |   | |    1, 1, 2, 1
6      |   2        |    |_ _|   | |    2, 2, 1
7      | 1          |    |_|     | |    1, 3, 1
8      |        8   |    |_ _ _ _| |    4, 1
9      | 1          |    |_| | |   |    1, 1, 1, 2
10     |   2        |    |_ _| |   |    2, 1, 2
11     | 1          |    |_|   |   |    1, 2, 2
12     |      4     |    |_ _ _|   |    3, 2
13     | 1          |    |_| |     |    1, 1, 3
14     |   2        |    |_ _|     |    2, 3
15     | 1          |    |_|       |    1, 4
16     |         16 |    |_ _ _ _ _|    5
.
The first largest region in the diagram is the 16th region which contains 16 parts, so T(5,1) = 16. The second largest region is the 8th region which contains 8 parts, so T(5,2) = 8. The third and the fourth largest regions are both the 4th region and the 12th region, each contains 4 parts, so T(5,3) = 4 and T(5,4) = 4. And so on. The sequence of the number of parts of the k-th largest region of the diagram is [16, 8, 4, 4, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1], the same as the 5th row of triangle, as shown below.
Triangle begins:
1;
2,1;
4,2,1,1;
8,4,2,2,1,1,1,1;
16,8,4,4,2,2,2,2,1,1,1,1,1,1,1,1;
32,16,8,8,4,4,4,4,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1;
...

Cf. A000079, A001511, A001792, A006519, A011782, A065120, A187818, A228525, A228369.

A187818 Triangle read by rows in which row n lists the first 2^(n-1) terms of A038712 in nonincreasing order, n >= 1.

Original entry on oeis.org

1, 3, 1, 7, 3, 1, 1, 15, 7, 3, 3, 1, 1, 1, 1, 31, 15, 7, 7, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 63, 31, 15, 15, 7, 7, 7, 7, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 127, 63, 31, 31, 15, 15, 15, 15, 7, 7, 7, 7, 7, 7, 7, 7, 3, 3

Offset: 1

Omar E. Pol, Sep 10 2013

T(n,k) is also the sum of all parts of the k-th largest region of the diagram of regions of the set of compositions of n, n >= 1, k >= 1, see example.
Row lengths is A000079.
Row sums give A001787, n >= 1.

			For n = 5 the diagram of regions of the set of compositions of 5 has 2^(5-1) regions, see below:
------------------------------------------------------
.         A038712 as
.       a tree of sum      Diagram
Region   of all parts    of regions     Composition
------------------------------------------------------
.                         _ _ _ _ _
1      | 1          |    |_| | | | |    1, 1, 1, 1, 1
2      |   3        |    |_ _| | | |    2, 1, 1, 1
3      | 1          |    |_|   | | |    1, 2, 1, 1
4      |      7     |    |_ _ _| | |    3, 1, 1
5      | 1          |    |_| |   | |    1, 1, 2, 1
6      |   3        |    |_ _|   | |    2, 2, 1
7      | 1          |    |_|     | |    1, 3, 1
8      |       15   |    |_ _ _ _| |    4, 1
9      | 1          |    |_| | |   |    1, 1, 1, 2
10     |   3        |    |_ _| |   |    2, 1, 2
11     | 1          |    |_|   |   |    1, 2, 2
12     |      7     |    |_ _ _|   |    3, 2
13     | 1          |    |_| |     |    1, 1, 3
14     |   3        |    |_ _|     |    2, 3
15     | 1          |    |_|       |    1, 4
16     |         31 |    |_ _ _ _ _|    5
.
The first largest region in the diagram is the 16th region which contains 16 parts and the sum of parts is 31, so T(5,1) = 31. The second largest region is the 8th region which contains 8 parts and the sum of parts is 15, so T(5,2) = 15. The third and the fourth largest regions are both the 4th region and the 12th region, each contains 4 parts and the sum of parts is 7, so T(5,3) = 7 and T(5,4) = 7. And so on. The sequence of the sum of all parts of the k-th largest region of the diagram is [31, 15, 7, 7, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1], the same as the 5th row of triangle, as shown below.
Triangle begins:
1;
3,1;
7,3,1,1;
15,7,3,3,1,1,1,1;
31,15,7,7,3,3,3,3,1,1,1,1,1,1,1,1;
63,31,15,15,7,7,7,7,3,3,3,3,3,3,3,3,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1;
...

Cf. A000079, A000225, A001511, A001787, A001792, A006519, A011782, A038712, A065120, A187816, A228525, A228369.

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

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Dec 18 2017

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

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

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

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

A299152 Denominators of the positive solution to 2^(n-1) = Sum_{d|n} a(d) * a(n/d).

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 8, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 16, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Gus Wiseman, Feb 03 2018

			Sequence begins: 1, 1, 2, 7/2, 8, 14, 32, 121/2, 126, 248, 512, 1003, 2048, 4064, 8176, 130539/8, 32768.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000005, A000010, A000740, A018804, A023900, A029935, A034691, A046643, A059966, A228369, A257098, A296302, A298971, A299119, A299149, A299151.

nn=50;
sys=Table[2^(n-1)==Sum[a[d]*a[n/d],{d,Divisors[n]}],{n,nn}];
Denominator[Array[a,nn]/.Solve[sys,Array[a,nn]][[2]]]

up_to = 65537;
prepareA299151perA299152(up_to) = { my(vmemo = vector(up_to)); for(n=1,up_to, vmemo[n] = if(1==n,n,(2^(n-1)-sumdiv(n,d,if((d>1)&&(dA299152 = prepareA299151perA299152(up_to);
A299151perA299152(n) = v299151perA299152[n];
\\ Or without memoization as:
A299151perA299152(n) = if(1==n,n,(2^(n-1)-sumdiv(n,d,if((d>1)&&(dA299151perA299152(d)*A299151perA299152(n/d),0)))/2);
A299152(n) = denominator(A299151perA299152(n)); \\ Antti Karttunen, Jul 29 2018

More terms from Antti Karttunen, Jul 29 2018

cp's OEIS Frontend

A296373 Triangle T(n,k) = number of compositions of n whose factorization into Lyndon words (aperiodic necklaces) is of length k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

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

A296772 Triangle read by rows in which row n lists the compositions of n ordered first by decreasing length and then reverse-lexicographically.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A296773 Triangle read by rows in which row n lists the compositions of n ordered first by decreasing length and then lexicographically.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A108244 Triangle read by rows: row n gives list of all compositions of n ordered first by decreasing length, then by reverse colexicographical order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A299151 Numerators of the positive solution to 2^(n-1) = Sum_{d|n} a(d) * a(n/d).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A187816 Triangle read by rows in which row n lists the first 2^(n-1) terms of A006519 in nonincreasing order, n >= 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

A187818 Triangle read by rows in which row n lists the first 2^(n-1) terms of A038712 in nonincreasing order, n >= 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

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

Views

Author

Keywords

Examples