A185700 -id:A185700 - cp's OEIS frontend

A299023 Number of compositions of n whose standard factorization into Lyndon words has all strict compositions as factors.

1, 2, 4, 7, 12, 23, 38, 66, 112, 193, 319, 539, 887, 1466, 2415, 3951, 6417, 10428, 16817, 27072, 43505, 69560, 110916, 176469, 279893, 442742, 698919, 1100898, 1729530, 2712134, 4244263, 6628174, 10332499, 16077835, 24972415, 38729239, 59958797, 92685287

Offset: 1

Gus Wiseman, Jan 31 2018

nonn

			The a(5) = 12 compositions:
      (5) = (5)
     (41) = (4)*(1)
     (14) = (14)
     (32) = (3)*(2)
     (23) = (23)
    (311) = (3)*(1)*(1)
    (131) = (13)*(1)
    (221) = (2)*(2)*(1)
    (212) = (2)*(12)
   (2111) = (2)*(1)*(1)*(1)
   (1211) = (12)*(1)*(1)
  (11111) = (1)*(1)*(1)*(1)*(1)
Not included:
    (113) = (113)
    (122) = (122)
   (1121) = (112)*(1)
   (1112) = (1112)

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

Cf. A001045, A032020, A032153, A034691, A049311, A059966, A089259, A098407, A116540, A185700, A270995, A296373, A299024, A299026, A299027.

nn=50;
ser=Product[1/(1-x^n)^Total[(Length[#]-1)!&/@Select[IntegerPartitions[n],UnsameQ@@#&]],{n,nn}];
Table[SeriesCoefficient[ser,{x,0,n}],{n,nn}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(N)={EulerT(Vec(sum(n=1, N-1, (n-1)!*x^(n*(n+1)/2)/prod(k=1, n, 1-x^k + O(x^N)))))} \\ Andrew Howroyd, Dec 01 2018

Euler transform of A032153.

A299024 Number of compositions of n whose standard factorization into Lyndon words has distinct strict compositions as factors.

Original entry on oeis.org

1, 1, 3, 4, 7, 13, 21, 34, 58, 98, 158, 258, 421, 676, 1108, 1777, 2836, 4544, 7220, 11443, 18215, 28729, 45203, 71139, 111518, 174402, 272367, 424892, 660563, 1025717, 1590448, 2460346, 3800816, 5862640, 9026963, 13885425, 21321663, 32695098, 50073855

Offset: 1

Gus Wiseman, Jan 31 2018

nonn

			The a(5) = 7 compositions:
      (5) = (5)
     (41) = (4)*(1)
     (14) = (14)
     (32) = (3)*(2)
     (23) = (23)
    (131) = (13)*(1)
    (212) = (2)*(12)
Not included:
    (311) = (3)*(1)*(1)
    (113) = (113)
    (221) = (2)*(2)*(1)
    (122) = (122)
   (2111) = (2)*(1)*(1)*(1)
   (1211) = (12)*(1)*(1)
   (1121) = (112)*(1)
   (1112) = (1112)
  (11111) = (1)*(1)*(1)*(1)*(1)

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

Cf. A001045, A032020, A032153, A034691, A049311, A050342, A059966, A089259, A098407, A116540, A185700, A270995, A283877, A292432, A296373, A299023, A299026, A299027.

nn=50;
ser=Product[(1+x^n)^Total[(Length[#]-1)!&/@Select[IntegerPartitions[n],UnsameQ@@#&]],{n,nn}];
Table[SeriesCoefficient[ser,{x,0,n}],{n,nn}]

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v,n,(-1)^(n-1)/n))))-1,-#v)}
seq(N)={WeighT(Vec(sum(n=1, N-1, (n-1)!*x^(n*(n+1)/2)/prod(k=1, n, 1-x^k + O(x^N)))))} \\ Andrew Howroyd, Dec 01 2018

Weigh transform of A032153.

A299026 Number of compositions of n whose standard factorization into Lyndon words has all weakly increasing factors.

Original entry on oeis.org

1, 2, 4, 8, 16, 31, 59, 111, 205, 378, 685, 1238, 2213, 3940, 6955, 12221, 21333, 37074, 64073, 110267, 188877, 322244, 547522, 926903, 1563370, 2628008, 4402927, 7353656, 12244434, 20329271, 33657560, 55574996, 91525882, 150356718, 246403694, 402861907

Offset: 1

Gus Wiseman, Feb 01 2018

nonn

			The 2^6 - a(7) = 5 compositions of 7 whose Lyndon prime factors are not all weakly increasing: (11212), (1132), (1213), (1321), (142).

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

Cf. A001045, A032153, A034691, A049311, A059966, A098407, A167934, A185700, A270995, A296373, A299023, A299024, A299027.

nn=50;
ser=Product[1/(1-x^n)^(PartitionsP[n]-DivisorSigma[0,n]+1),{n,nn}];
Table[SeriesCoefficient[ser,{x,0,n}],{n,nn}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={EulerT(vector(n, n, numbpart(n) - numdiv(n) + 1))} \\ Andrew Howroyd, Dec 01 2018

Euler transform of A167934.

A299027 Number of compositions of n whose standard factorization into Lyndon words has all distinct weakly increasing factors.

Original entry on oeis.org

1, 1, 3, 5, 11, 20, 38, 69, 125, 225, 400, 708, 1244, 2176, 3779, 6532, 11229, 19223, 32745, 55555, 93875, 158025, 265038, 443009, 738026, 1225649, 2029305, 3350167, 5515384, 9055678, 14830076, 24226115, 39480306, 64190026, 104130753, 168556588, 272268482

Offset: 1

Gus Wiseman, Feb 01 2018

nonn

			The a(5) = 11 compositions:
      (5) = (5)
     (41) = (4)*(1)
     (14) = (14)
     (32) = (3)*(2)
     (23) = (23)
    (131) = (13)*(1)
    (113) = (113)
    (212) = (2)*(12)
    (122) = (122)
   (1121) = (112)*(1)
   (1112) = (1112)
Not included:
    (311) = (3)*(1)*(1)
    (221) = (2)*(2)*(1)
   (2111) = (2)*(1)*(1)*(1)
   (1211) = (12)*(1)*(1)
  (11111) = (1)*(1)*(1)*(1)*(1)

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

Cf. A001045, A032153, A034691, A049311, A059966, A098407, A116540, A185700, A270995, A283877, A292432, A293993, A296373, A299023, A299024, A299026.

nn=50;
ser=Product[(1+x^n)^(PartitionsP[n]-DivisorSigma[0,n]+1),{n,nn}];
Table[SeriesCoefficient[ser,{x,0,n}],{n,nn}]

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v,n,(-1)^(n-1)/n))))-1,-#v)}
seq(n)={WeighT(vector(n, n, numbpart(n) - numdiv(n) + 1))} \\ Andrew Howroyd, Dec 01 2018

Weigh transform of A167934.

A188160 For an unordered partition of n with k parts, remove 1 from each part and append the number k to get a new partition until a partition is repeated. a(n) gives the maximum steps to reach a period considering all unordered partitions of n.

Original entry on oeis.org

0, 1, 2, 4, 5, 6, 7, 8, 10, 12, 12, 12, 13, 18, 20, 20, 17, 18, 21, 28, 30, 30, 24, 24, 25, 32, 40, 42, 42, 35, 31, 32, 36, 45, 54, 56, 56, 48, 40, 40, 41, 50, 60, 70, 72, 72, 63, 54, 49, 50, 55, 66, 77, 88, 90, 90, 80, 70, 60, 60, 61

Offset: 1

Paul Weisenhorn, Mar 28 2011

nonn

Alternatively, if one iteratively removes the largest part z(1) and adds 1 to the next z(1) parts to get a new partition until a partition recurs, one gets the same maximum number of steps to reach a period.
The two shuffling operations are isomorphic for unordered partitions.
The two operations have the same length and number of periods for ordered and unordered partitions.
The steps count the operations including any pre-periodic part up to the end of first period, that is, the number of distinct partitions without including the first return.

			For k=6 and 0 <= j <= 1:
a(19)=21;  a(20)=28;  a(21)=30;  a(22)=30;  a(23)=24;  a(24)=24;  a(25)=25.
For n=4: (1+1+1+1)->(4)->(3+1)->(2+2)->(2+1+1)--> a(4)=4.
For n=5: (1+1+1+1+1)->(5)->(4+1)->(3+2)->(2+2+1)->(3+1+1)-->a(5)=5.

R. Baumann LOG IN, 4 (1987)
Halder, Heise Einführung in Kombinatorik, Hanser Verlag (1976) 75 ff.

Ethan Akin, Morton Davis, Bulgarian solitaire, Am. Math. Monthly 92 (4) (1985) 237-250
J. Brandt, Cycles of partitions, Proc. Am. Math. Soc. 85 (3) (1982) 483-486

Cf. A185700, A177922, A184996, A037306.

A188160 := proc(n)
        local k,j,T ;
        if n <= 2 then
                return n-1 ;
        end if;
        for k from 0 do
                T := k*(k+1) /2 ;
                if n = T and k >= 1 then
                        return k*(k-1) ;
                end if;
                if k>=4 then
                        j := T-1-n ;
                        if j>= 0 and j <= (k-4)/2 then
                                return k^2-k-2-(k+1)*j ;
                        end if;
                        j := n-T-1 ;
                        if j>= 0 and j <= (k-4)/2 then
                                return k^2-k-k*j ;
                        end if;
                end if;
                if k >= 2 then
                        j := n-(k^2+2*k-(k mod 2))/2 ;
                        if j>=0 and j <= 1 then
                                return (k^2+2*k-(k mod 2))/2+j
                        end if;
                end if;
        end do:
        return -1 ;
end proc: # R. J. Mathar, Apr 22 2011

a((k^2+k-2)/2-j) = k^2-k-2-(k+1)*j with 0<=j<=(k-4)/2  and 4<=k.
a((k^2+k+2)/2+j) = k^2-k-k*j with 0<=j<=(k-4)/2 and 4<=k,
a((k^2+2*k-(k mod 2))/2+j) = (k^2+2*k-(k mod 2))/2+j  with 0 <= j <= 1 and 2 <= k.
a(T(k)) = 2*T(k-1) = k^2-k with 1 <= k for the triangular numbers T(k)=A000217(k).

A296976 List of normal Lyndon sequences ordered first by length and then reverse-lexicographically, where a finite sequence is normal if it spans an initial interval of positive integers.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Dec 22 2017

Row n is formed by A060223(n) sequences and has length A296975(n).

			Triangle of normal Lyndon sequences begins:
1,
12,
132,123,122,112,
1432,1423,1342,1332,1324,1323,1322,1243,1234,1233,1232,1223,1222,1213,1132,1123,1122,1112.

Cf. A000670, A019536, A060223, A095684, A185700, A281013, A294859, A296372, A296656, A296818, A296975-A296978.

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
normseqs[n_]:=Union@@Permutations/@Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Select[Reverse@normseqs@n,LyndonQ],{n,5}]

A296977 List of normal Lyndon sequences ordered first by length and then lexicographically, where a finite sequence is normal if it spans an initial interval of positive integers.

Original entry on oeis.org

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

Offset: 1

Gus Wiseman, Dec 22 2017

Row n is formed by A060223(n) sequences and has length A296975(n).

			Triangle of normal Lyndon sequences begins:
1,
12,
112,122,123,132,
1112,1122,1123,1132,1213,1222,1223,1232,1233,1234,1243,1322,1323,1324,1332,1342,1423,1432.

Cf. A000670, A019536, A060223, A095684, A185700, A281013, A294859, A296372, A296656, A296818, A296975, A296976.

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
normseqs[n_]:=Union@@Permutations/@Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
Table[Select[normseqs[n],LyndonQ],{n,5}]

A299072 Sequence is an irregular triangle read by rows with zeros removed where T(n,k) is the number of compositions of n whose standard factorization into Lyndon words has k distinct factors.

Original entry on oeis.org

1, 2, 3, 1, 5, 3, 7, 9, 13, 17, 2, 19, 39, 6, 35, 72, 21, 59, 141, 55, 1, 107, 266, 132, 7, 187, 511, 300, 26, 351, 952, 660, 85, 631, 1827, 1395, 240, 3, 1181, 3459, 2901, 636, 15, 2191, 6595, 5977, 1554, 67, 4115, 12604, 12123, 3698, 228, 7711, 24173, 24504

Offset: 1

Gus Wiseman, Feb 01 2018

Row sums are 2^(n-1). First column is A008965. A regular version is A299070.

			Triangle begins:
    1
    2
    3    1
    5    3
    7    9
   13   17    2
   19   39    6
   35   72   21
   59  141   55    1
  107  266  132    7
  187  511  300   26

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

Cf. A001045, A001221, A008965, A059966, A116608, A146289, A185700, A296373, A299070.

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

\\ here b(n) is A059966.
b(n)={sumdiv(n, d, moebius(n/d) * (2^d-1))/n}
A(n)=[Vecrev(p/y) | p<-Vec(prod(k=1, n, (1 - y + y/(1-x^k) + O(x*x^n))^b(k))-1)]
my(T=A(15)); for(n=1, #T, print(T[n])) \\ Andrew Howroyd, Dec 08 2018

A184996 For each ordered partition of n with k numbers, remove 1 from each part and add the number k to get a new partition, until a partition is repeated. Among all ordered partitions of n, a(n) gives the maximum number of steps needed to reach a period.

Original entry on oeis.org

0, 1, 3, 5, 7, 8, 9, 11, 13, 15, 15, 16, 17, 22, 24, 24, 22, 23, 26, 33, 35, 35, 29, 30, 31, 38, 46, 48, 48, 41, 38, 39, 43, 52, 61, 63, 63, 55, 47, 48, 49, 58, 68, 78, 80, 80, 71, 62, 58, 59, 64, 75, 86, 97, 99, 99, 89, 79, 69, 70, 71, 82, 94, 106, 118, 120, 120, 109, 98, 87

Offset: 1

Paul Weisenhorn, Mar 28 2011

nonn

If one plays with p(n,n) unordered partitions, one gets the same number and length of periods.

If one removes the first part z(1) of each partition and adds 1 to the next z(1) parts to get a new partition, until a partition is repeated, one gets the same length and number of periods, playing with 2^(n-1) ordered or p(n,n) unordered partitions (A185700, A092964, A037306)

			For k=6: a(19)=26; a(20)=3; a(21)=35; a(22)=35; a(23)=29; a(24)=30; a(25)=31.
For n=4: (1+1+1+1)->(4)->(3+1)->(2+2)->(1+1+2)->(1+3)--> a(4)=5 steps.
For n=5: (1+1+1+1+1)->(5)->(4+1)->(3+2)->(2+1+2)->(1+1+3)->(2+3)->(1+2+2)--> a(5)=7 steps.

R. Baumann, Computer-Knobelei, LOGIN, 4 (1987), pages ?.
H. R. Halder and W. Heise, Einführung in Kombinatorik, Hanser Verlag, Munich, 1976, pp. 75ff.

Cf. A185700, A092964, A037306.

a((k^2+k-2)/2-j)=k^2-3-(k+1)*j with 0<=j<=(k-4) div 2 and 4<=k.
a((k^2+k+2)/2+j)=k^2-1-k*j with 0<=j<=(k-5) div 2 and 5<=k.
a((k^2+2*k-2+k mod 2)/2+j)=(k^2+4*k-2+k mod 2)/2+j with 0<=j<=2-k mod 2 and 4<=k.
a(T(k))=k^2-1 with 1<= k  for all triangular numbers T(k).

Partially edited by N. J. A. Sloane, Apr 08 2011

A299070 Regular triangle T(n,k) is the number of compositions of n whose standard factorization into Lyndon words has k distinct factors.

Original entry on oeis.org

1, 2, 0, 3, 1, 0, 5, 3, 0, 0, 7, 9, 0, 0, 0, 13, 17, 2, 0, 0, 0, 19, 39, 6, 0, 0, 0, 0, 35, 72, 21, 0, 0, 0, 0, 0, 59, 141, 55, 1, 0, 0, 0, 0, 0, 107, 266, 132, 7, 0, 0, 0, 0, 0, 0, 187, 511, 300, 26, 0, 0, 0, 0, 0, 0, 0

Offset: 1

Gus Wiseman, Feb 01 2018

Row sums are 2^(n-1). First column is A008965. A version without the zeros is A299072.

			Triangle begins:
    1
    2    0
    3    1    0
    5    3    0    0
    7    9    0    0    0
   13   17    2    0    0    0
   19   39    6    0    0    0    0
   35   72   21    0    0    0    0    0
   59  141   55    1    0    0    0    0    0
  107  266  132    7    0    0    0    0    0    0
  187  511  300   26    0    0    0    0    0    0    0.
The a(5,2) = 9 compositions are (41), (32), (311), (131), (221), (212), (2111), (1211), (1121) with factorizations
    (41) = (4) * (1)
    (32) = (3) * (2)
   (311) = (3) * (1)^2
   (131) = (13) * (1)
   (221) = (2)^2 * (1)
   (212) = (2) * (12)
  (2111) = (2) * (1)^3
  (1211) = (12) * (1)^2
  (1121) = (112) * (1).

Cf. A001045, A001221, A008965, A059966, A116608, A146289, A185700, A296373, A299072.

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

cp's OEIS Frontend

A299023 Number of compositions of n whose standard factorization into Lyndon words has all strict compositions as factors.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A299024 Number of compositions of n whose standard factorization into Lyndon words has distinct strict compositions as factors.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A299026 Number of compositions of n whose standard factorization into Lyndon words has all weakly increasing factors.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A299027 Number of compositions of n whose standard factorization into Lyndon words has all distinct weakly increasing factors.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A188160 For an unordered partition of n with k parts, remove 1 from each part and append the number k to get a new partition until a partition is repeated. a(n) gives the maximum steps to reach a period considering all unordered partitions of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Formula

A296976 List of normal Lyndon sequences ordered first by length and then reverse-lexicographically, where a finite sequence is normal if it spans an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A296977 List of normal Lyndon sequences ordered first by length and then lexicographically, where a finite sequence is normal if it spans an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A299072 Sequence is an irregular triangle read by rows with zeros removed where T(n,k) is the number of compositions of n whose standard factorization into Lyndon words has k distinct factors.

Views

Author

Keywords

Comments