A333213 -id:A333213 - cp's OEIS frontend

A188920 a(n) is the limiting term of the n-th column of the triangle in A188919.

1, 1, 2, 4, 7, 13, 22, 38, 63, 105, 169, 274, 434, 686, 1069, 1660, 2548, 3897, 5906, 8911, 13352, 19917, 29532, 43605, 64056, 93715, 136499, 198059, 286233, 412199, 591455, 845851, 1205687, 1713286, 2427177, 3428611, 4829563, 6784550, 9505840, 13284849

Offset: 0

N. J. A. Sloane, Apr 13 2011

nonn

Also the number of integer compositions of n whose reverse avoids 12-1 and 23-1.

Theorem: The reverse of a composition avoids 12-1 and 23-1 iff its leaders of maximal weakly increasing runs, obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each, are strictly decreasing. For example, the composition y = (4,5,3,2,2,3,1,3,5) has reverse (5,3,1,3,2,2,3,5,4), which avoids 12-1 and 23-1, while the maximal weakly increasing runs of y are ((4,5),(3),(2,2,3),(1,3,5)), with leaders (4,3,2,1), which are strictly decreasing, as required. - Gus Wiseman, Aug 20 2024

			From _Gus Wiseman_, Aug 20 2024: (Start)
The a(0) = 1 through a(6) = 22 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)
                                (212)    (123)
                                (221)    (132)
                                (311)    (213)
                                (1112)   (222)
                                (2111)   (312)
                                (11111)  (321)
                                         (411)
                                         (1113)
                                         (1122)
                                         (2112)
                                         (2211)
                                         (3111)
                                         (11112)
                                         (21111)
                                         (111111)
(End)

John Tyler Rascoe, Table of n, a(n) for n = 0..200
A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011.
Andrew M. Baxter and Lara K. Pudwell, Enumeration schemes for dashed patterns, arXiv preprint arXiv:1108.2642 [math.CO], 2011-2012.
Wikipedia, Permutation pattern.
Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

For leaders of identical runs we have A000041.
Matching 23-1 only gives A189076.
An opposite version is A358836.
For identical leaders we have A374631, ranks A374633.
For distinct leaders we have A374632, ranks A374768.
For weakly increasing leaders we have A374635.
For non-weakly decreasing leaders we have A374636, ranks A375137.
For leaders of anti-runs we have A374680.
For leaders of strictly increasing runs we have A374689.
The complement is counted by A375140, ranks A375295, reverse A375296.
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
Cf. A056823, A102726, A188900, A188919, A189077, A238343, A333213, A335480/A335482, A374679, A374688.

b[u_, o_] := b[u, o] = Expand[If[u + o == 0, 1, Sum[b[u - j, o + j - 1]*x^(o + j - 1), {j, 1, u}] + Sum[If[u == 0, b[u + j - 1, o - j]*x^(o - j), 0], {j, 1, o}]]];
T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[0, n]];
Take[T[40], 40] (* Jean-François Alcover, Sep 15 2018, after Alois P. Heinz in A188919 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Greater@@First/@Split[Reverse[#],LessEqual]&]],{n,0,15}] (* Gus Wiseman, Aug 20 2024 *)
- or -
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], !MatchQ[#,{_,y_,z_,_,x_,_}/;x<=yGus Wiseman, Aug 20 2024 *)

B_x(i,N) = {my(x='x+O('x^N), f=(x^i)/(1-x^i)*prod(j=i+1,N-i,1/(1-x^j))); f}
A_x(N) = {my(x='x+O('x^N), f=1+sum(i=1,N, B_x(i,N)*prod(j=1,i-1,1+B_x(j,N)))); Vec(f)}
A_x(60) \\ John Tyler Rascoe, Aug 23 2024

a(n) = 2^(n-1) - A375140(n).

G.f.: 1 + Sum_{i>0} (B(i,x) * Product_{j=1..i-1} (1 + B(j,x))) where B(i,x) = (x^i)/(1-x^i) * Product_{j>i} (1/(1-x^j)). - John Tyler Rascoe, Aug 23 2024

More terms from Andrew Baxter, May 17 2011

a(30)-a(39) from Alois P. Heinz, Nov 14 2015

A124765 Number of monotonically decreasing runs for compositions in standard order.

Original entry on oeis.org

0, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 1, 2, 2, 2, 1, 2, 2, 2, 2, 3, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 1, 2, 1, 2, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 3, 2, 3

Offset: 0

Franklin T. Adams-Watters, Nov 06 2006

The standard order of compositions is given by A066099.

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. a(n) is the number of maximal weakly decreasing runs in this composition. Alternatively, a(n) is one plus the number of strict ascents in the same composition. For example, the weakly decreasing runs of the 1234567th composition are ((3,2,1),(2,2,1),(2),(5,1,1,1)), so a(1234567) = 4. The 3 strict ascents together with the weak descents are: 3 >= 2 >= 1 < 2 >= 2 >= 1 < 2 < 5 >= 1 >= 1 >= 1. - Gus Wiseman, Apr 08 2020

			Composition number 11 is 2,1,1; the decreasing runs are 2,1,1; so a(11) = 1.
The table starts:
  0
  1
  1 1
  1 1 2 1
  1 1 1 1 2 2 2 1
  1 1 1 1 2 1 2 1 2 2 2 2 2 2 2 1
  1 1 1 1 1 1 2 1 2 2 1 1 2 2 2 1 2 2 2 2 3 2 3 2 2 2 2 2 2 2 2 1

Antti Karttunen, Table of n, a(n) for n = 0..16383

Cf. A066099, A124760, A011782 (row lengths).
Compositions of n with k strict ascents are A238343.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Sum is A070939.
- Weakly decreasing compositions are A114994.
- Weakly decreasing runs are counted by A124765.
- Weakly increasing runs are counted by A124766.
- Equal runs are counted by A124767.
- Strictly increasing runs are counted by A124768.
- Strictly decreasing runs are counted by A124769.
- Weakly increasing compositions are A225620.
- Reverse is A228351 (triangle).
- Strict compositions are A233564.
- Constant compositions are A272919.
- Normal compositions are A333217.
- Strictly decreasing compositions are A333255.
- Strictly increasing compositions are A333256.
- Anti-runs are counted by A333381.
- Adjacent unequal pairs are counted by A333382.
- Anti-runs are A333489.
- Runs-resistance is A333628.
Cf. A124761, A124763, A124764, A233249, A333213, A333380.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Split[stc[n],GreaterEqual]],{n,0,100}] (* Gus Wiseman, Apr 08 2020 *)

a(0) = 0, a(n) = A124760(n) + 1 for n > 0.

A124769 Number of strictly decreasing runs for compositions in standard order.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 2, 2, 2, 3, 4, 1, 1, 1, 2, 2, 2, 2, 3, 2, 2, 3, 3, 3, 3, 4, 5, 1, 1, 1, 2, 2, 1, 2, 3, 2, 2, 3, 3, 2, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 3, 3, 4, 4, 4, 4, 5, 6, 1, 1, 1, 2, 1, 1, 2, 3, 2, 2, 2, 2, 2, 2, 3, 4, 2, 2, 2, 3, 3, 3, 3, 4, 2, 2, 3, 3, 3, 3, 4, 5, 2, 2, 2, 3, 3, 2, 3, 4, 3

Offset: 0

Franklin T. Adams-Watters, Nov 06 2006

The standard order of compositions is given by A066099.

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. a(n) is the number of maximal strictly decreasing runs in this composition. Alternatively, a(n) is one plus the number of weak ascents in the same composition. For example, the strictly decreasing runs of the 1234567th composition are ((3,2,1),(2),(2,1),(2),(5,1),(1),(1)), so a(1234567) = 7. The 6 weak ascents together with the strict descents are: 3 > 2 > 1 <= 2 <= 2 > 1 <= 2 <= 5 > 1 <= 1 <= 1. - Gus Wiseman, Apr 08 2020

			Composition number 11 is 2,1,1; the strictly increasing runs are 2,1; 1; so a(11) = 2.
The table starts:
  0
  1
  1 2
  1 1 2 3
  1 1 2 2 2 2 3 4
  1 1 1 2 2 2 2 3 2 2 3 3 3 3 4 5
  1 1 1 2 2 1 2 3 2 2 3 3 2 2 3 4 2 2 2 3 3 3 3 4 3 3 4 4 4 4 5 6

Cf. A066099, A124764, A011782 (row lengths).
Compositions of n with k weak ascents are A333213.
Positions of ones are A333256.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Partial sums from the right are A048793 (triangle).
- Sum is A070939.
- Weakly decreasing compositions are A114994.
- Weakly decreasing runs are counted by A124765.
- Weakly increasing runs are counted by A124766.
- Equal runs are counted by A124767.
- Strictly increasing runs are counted by A124768.
- Strictly decreasing runs are counted by A124769 (this sequence).
- Reversed initial intervals A164894.
- Weakly increasing compositions are A225620.
- Reverse is A228351 (triangle).
- Strict compositions are A233564.
- Constant compositions are A272919.
- Normal compositions are A333217.
- Permutations are A333218.
- Heinz number is A333219.
- Strictly decreasing compositions are A333255.
- Strictly increasing compositions are A333256.
- Anti-runs are A333489.
Cf. A124760, A124761, A124763, A233249, A238343.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Split[stc[n],Greater]],{n,0,100}] (* Gus Wiseman, Apr 08 2020 *)

a(0) = 0, a(n) = A124764(n) + 1 for n > 0.

A344604 Number of alternating compositions of n, including twins (x,x).

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 13, 19, 30, 48, 76, 118, 187, 293, 461, 725, 1140, 1789, 2815, 4422, 6950, 10924, 17169, 26979, 42405, 66644, 104738, 164610, 258708, 406588, 639010, 1004287, 1578364, 2480606, 3898600, 6127152, 9629624, 15134213, 23785389, 37381849, 58750469

Offset: 0

Gus Wiseman, May 27 2021

nonn

We define a composition to be alternating including twins (x,x) if there are no adjacent triples (..., x, y, z, ...) where x <= y <= z or x >= y >= z. Except in the case of twins (x,x), all such compositions are anti-runs (A003242). These compositions avoid the weak consecutive patterns (1,2,3) and (3,2,1), the strict version being A344614.

The version without twins (x,x) is A025047 (alternating compositions).

			The a(1) = 1 through a(7) = 19 compositions:
  (1)  (2)   (3)   (4)    (5)    (6)     (7)
       (11)  (12)  (13)   (14)   (15)    (16)
             (21)  (22)   (23)   (24)    (25)
                   (31)   (32)   (33)    (34)
                   (121)  (41)   (42)    (43)
                          (131)  (51)    (52)
                          (212)  (132)   (61)
                                 (141)   (142)
                                 (213)   (151)
                                 (231)   (214)
                                 (312)   (232)
                                 (1212)  (241)
                                 (2121)  (313)
                                         (412)
                                         (1213)
                                         (1312)
                                         (2131)
                                         (3121)
                                         (12121)

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

A001250 counts alternating permutations.
A005649 counts anti-run patterns.
A025047 counts alternating or wiggly compositions, also A025048, A025049.
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A325534 counts separable partitions.
A325535 counts inseparable partitions.
A344605 counts alternating patterns including twins.
A344606 counts alternating permutations of prime factors including twins.
Counting compositions by patterns:
- A011782 no conditions.
- A003242 avoiding (1,1) adjacent.
- A102726 avoiding (1,2,3).
- A106351 avoiding (1,1) adjacent by sum and length.
- A128695 avoiding (1,1,1) adjacent.
- A128761 avoiding (1,2,3) adjacent.
- A232432 avoiding (1,1,1).
- A335456 all patterns.
- A335457 all patterns adjacent.
- A335514 matching (1,2,3).
- A344614 avoiding (1,2,3) and (3,2,1) adjacent.
- A344615 weakly avoiding (1,2,3) adjacent.
Cf. A000041, A006330, A008965, A238279, A239830, A333213, A238279/A333755, A344612, A344616, A344617, A344618.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,y_,z_,_}/;x<=y<=z||x>=y>=z]&]],{n,0,15}]

a(n > 0) = A025047(n) + 1 if n is even, otherwise A025047(n). - Gus Wiseman, Nov 03 2021

a(21)-a(40) from Alois P. Heinz, Nov 04 2021

A344614 Number of compositions of n with no adjacent triples (..., x, y, z, ...) where x < y < z or x > y > z.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 30, 58, 110, 209, 397, 753, 1429, 2711, 5143, 9757, 18511, 35117, 66621, 126389, 239781, 454897, 863010, 1637260, 3106138, 5892821, 11179603, 21209446, 40237641, 76337091, 144823431, 274752731, 521249018, 988891100, 1876081530, 3559220898, 6752400377

Offset: 0

Gus Wiseman, May 27 2021

nonn

These compositions avoid the strict consecutive patterns (1,2,3) and (3,2,1), the weak version being A344604.

			The a(6) = 30 compositions are:
  (6)  (15)  (114)  (1113)  (11112)  (111111)
       (24)  (132)  (1122)  (11121)
       (33)  (141)  (1131)  (11211)
       (42)  (213)  (1212)  (12111)
       (51)  (222)  (1221)  (21111)
             (231)  (1311)
             (312)  (2112)
             (411)  (2121)
                    (2211)
                    (3111)
Missing are: (123), (321).

A001250 counts alternating permutations.
A005649 counts anti-run patterns.
A025047 counts wiggly compositions (ascend: A025048, descend: A025049).
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A325534 counts separable partitions.
A325535 counts inseparable partitions.
A344604 counts wiggly compositions with twins.
A344605 counts wiggly patterns with twins.
A344606 counts wiggly permutations of prime factors with twins.
Counting compositions by patterns:
- A003242 avoiding (1,1) adjacent.
- A011782 no conditions.
- A106351 avoiding (1,1) adjacent by sum and length.
- A128695 avoiding (1,1,1) adjacent.
- A128761 avoiding (1,2,3).
- A232432 avoiding (1,1,1).
- A335456 all patterns.
- A335457 all patterns adjacent.
- A335514 matching (1,2,3).
- A344604 weakly avoiding (1,2,3) and (3,2,1) adjacent.
- A344614 avoiding (1,2,3) and (3,2,1) adjacent.
- A344615 weakly avoiding (1,2,3) adjacent.
Cf. A000041, A006330, A008965, A049774, A056986, A238279/A333755, A333213, A335515, A344612, A344652.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,y_,z_,_}/;xy>z]&]],{n,0,15}]

More terms from Bert Dobbelaere, Jun 12 2021

A374632 Number of integer compositions of n whose leaders of weakly increasing runs are distinct.

Original entry on oeis.org

1, 1, 2, 4, 7, 13, 23, 40, 69, 119, 200, 335, 557, 917, 1499, 2433, 3920, 6280, 10004, 15837, 24946, 39087, 60952, 94606, 146203, 224957, 344748, 526239, 800251, 1212527, 1830820, 2754993, 4132192, 6178290, 9209308, 13686754, 20282733, 29973869, 44175908, 64936361

Offset: 0

Gus Wiseman, Jul 23 2024

nonn

The leaders of weakly increasing runs in a sequence are obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each.

			The composition (4,2,2,1,1,3) has weakly increasing runs ((4),(2,2),(1,1,3)), with leaders (4,2,1), so is counted under a(13).
The a(0) = 1 through a(5) = 13 compositions:
  ()  (1)  (2)   (3)    (4)     (5)
           (11)  (12)   (13)    (14)
                 (21)   (22)    (23)
                 (111)  (31)    (32)
                        (112)   (41)
                        (211)   (113)
                        (1111)  (122)
                                (212)
                                (221)
                                (311)
                                (1112)
                                (2111)
                                (11111)

Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

Ranked by A374768 = positions of distinct rows in A374629 (sums A374630).
Types of runs (instead of weakly increasing):
- For leaders of constant runs we have A274174, ranks A374249.
- For leaders of anti-runs we have A374518, ranks A374638.
- For leaders of strictly increasing runs we have A374687, ranks A374698.
- For leaders of weakly decreasing runs we have A374743, ranks A335467.
- For leaders of strictly decreasing runs we have A374761, ranks A374767.
Types of run-leaders (instead of distinct):
- For strictly decreasing leaders we appear to have A188920.
- For weakly decreasing leaders we appear to have A189076.
- For identical leaders we have A374631.
- For weakly increasing leaders we have A374635.
- For strictly increasing leaders we have A374634.
A003242 counts anti-run compositions.
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
A335456 counts patterns matched by compositions.
A374637 counts compositions by sum of leaders of weakly increasing runs.
Cf. A106356, A124766, A238343, A261982, A333213, A335548, A373949, A373953.

Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n],UnsameQ@@First/@Split[#,LessEqual]&]],{n,0,15}]

dfs(m, r, v) = 1 + sum(s=1, min(m, r-1), if(!setsearch(v, s), dfs(m-s, s, setunion(v, [s]))*x^s/(1-x^s) + sum(t=s+1, m-s, dfs(m-s-t, t, setunion(v, [s]))*x^(s+t)/prod(i=s, t, 1-x^i))));
lista(nn) = Vec(dfs(nn, nn+1, []) + O(x^(1+nn))); \\ Jinyuan Wang, Feb 13 2025

More terms from Jinyuan Wang, Feb 13 2025

A374635 Number of integer compositions of n whose leaders of weakly increasing runs are themselves weakly increasing.

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 20, 36, 69, 130, 247, 467, 890, 1689, 3213, 6110, 11627, 22121, 42101, 80124, 152512, 290300, 552609, 1051953, 2002583, 3812326, 7257679, 13816867, 26304254, 50077792, 95338234, 181505938, 345554234, 657874081, 1252478707, 2384507463, 4539705261

Offset: 0

Gus Wiseman, Jul 23 2024

nonn

The leaders of weakly increasing runs in a sequence are obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each.

			The composition (1,3,3,2,4,2) has weakly increasing runs ((1,3,3),(2,4),(2)), with leaders (1,2,2), so is counted under a(15).
The a(0) = 1 through a(6) = 20 compositions:
  ()  (1)  (2)   (3)    (4)     (5)      (6)
           (11)  (12)   (13)    (14)     (15)
                 (111)  (22)    (23)     (24)
                        (112)   (113)    (33)
                        (121)   (122)    (114)
                        (1111)  (131)    (123)
                                (1112)   (132)
                                (1121)   (141)
                                (1211)   (222)
                                (11111)  (1113)
                                         (1122)
                                         (1131)
                                         (1212)
                                         (1221)
                                         (1311)
                                         (11112)
                                         (11121)
                                         (11211)
                                         (12111)
                                         (111111)

Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

Ranked by positions of weakly increasing rows in A374629 (sums A374630).
Types of runs (instead of weakly increasing):
- For leaders of constant runs we have A000041.
- For leaders of weakly decreasing runs we have A188900.
- For leaders of anti-runs we have A374681.
- For leaders of strictly increasing runs we have A374690.
- For leaders of strictly decreasing runs we have A374764.
Types of run-leaders (instead of weakly increasing):
- For strictly decreasing leaders we appear to have A188920.
- For weakly decreasing leaders we appear to have A189076.
- For identical leaders we have A374631.
- For distinct leaders we have A374632, ranks A374768.
- For strictly increasing leaders we have A374634.
A003242 counts anti-run compositions.
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
A274174 counts contiguous compositions, ranks A374249.
A335456 counts patterns matched by compositions.
A335548 counts non-contiguous compositions, ranks A374253.
A374637 counts compositions by sum of leaders of weakly increasing runs.
Cf. A106356, A124766, A238343, A261982, A333213, A374518, A374687, A374761.

Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n],LessEqual@@First/@Split[#,LessEqual]&]],{n,0,15}]

dfs(m, r, u) = 1 + sum(s=u, min(m, r-1), x^s/(1-x^s) + sum(t=s+1, m-s, dfs(m-s-t, t, s)*x^(s+t)/prod(i=s, t, 1-x^i)));
lista(nn) = Vec(dfs(nn, nn+1, 1) + O(x^(1+nn))); \\ Jinyuan Wang, Feb 13 2025

More terms from Jinyuan Wang, Feb 13 2025

A373954 Excess run-compression of standard compositions. Sum of all parts minus sum of compressed parts of the n-th integer composition in standard order.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Jun 27 2024

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

We define the (run-) compression of a sequence to be the anti-run obtained by reducing each run of repeated parts to a single part. Alternatively, compression removes all parts equal to the part immediately to their left. For example, (1,1,2,2,1) has compression (1,2,1).

			The excess compression of (2,1,1,3) is 1, so a(92) = 1.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

For length instead of sum we have A124762, counted by A106356.
The opposite for length is A124767, counted by A238279 and A333755.
Positions of zeros are A333489, counted by A003242.
Positions of nonzeros are A348612, counted by A131044.
Compositions counted by this statistic are A373951, opposite A373949.
Compression of standard compositions is A373953.
Positions of ones are A373955.
A037201 gives compression of first differences of primes, halved A373947.
A066099 lists the parts of all compositions in standard order.
A114901 counts compositions with no isolated parts.
A116861 counts partitions by this statistic, by length A116608.
A240085 counts compositions with no unique parts.
A333627 takes the rank of a composition to the rank of its run-lengths.
Cf. A070939, A238130, A238343, A272919, A285981, A333213, A333381, A333382.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Total[stc[n]]-Total[First/@Split[stc[n]]],{n,0,100}]

a(n) = A029837(n) - A373953(n).

A374683 Irregular triangle read by rows where row n lists the leaders of strictly increasing runs in the n-th composition in standard order.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Jul 26 2024

The leaders of strictly increasing runs in a sequence are obtained by splitting it into maximal strictly increasing subsequences and taking the first term of each.

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The maximal strictly increasing subsequences of the 1234567th composition in standard order are ((3),(2),(1,2),(2),(1,2,5),(1),(1),(1)), so row 1234567 is (3,2,1,2,1,1,1,1).
The nonnegative integers, corresponding compositions, and leaders of strictly increasing runs begin:
   0:      () -> ()         15: (1,1,1,1) -> (1,1,1,1)
   1:     (1) -> (1)        16:       (5) -> (5)
   2:     (2) -> (2)        17:     (4,1) -> (4,1)
   3:   (1,1) -> (1,1)      18:     (3,2) -> (3,2)
   4:     (3) -> (3)        19:   (3,1,1) -> (3,1,1)
   5:   (2,1) -> (2,1)      20:     (2,3) -> (2)
   6:   (1,2) -> (1)        21:   (2,2,1) -> (2,2,1)
   7: (1,1,1) -> (1,1,1)    22:   (2,1,2) -> (2,1)
   8:     (4) -> (4)        23: (2,1,1,1) -> (2,1,1,1)
   9:   (3,1) -> (3,1)      24:     (1,4) -> (1)
  10:   (2,2) -> (2,2)      25:   (1,3,1) -> (1,1)
  11: (2,1,1) -> (2,1,1)    26:   (1,2,2) -> (1,2)
  12:   (1,3) -> (1)        27: (1,2,1,1) -> (1,1,1)
  13: (1,2,1) -> (1,1)      28:   (1,1,3) -> (1,1)
  14: (1,1,2) -> (1,1)      29: (1,1,2,1) -> (1,1,1)

Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

Row-leaders are A065120.
Row-lengths are A124768.
Other types of runs: A374251, A374515, A374740.
The weak version is A374629, sum A374630, length A124766.
Row-sums are A374684.
Positions of identical rows are A374685, counted by A374686.
Positions of distinct (strict) rows are A374698, counted by A374687.
The opposite version is A374757, sum A374758, length A124769.
All of the following pertain to compositions in standard order:
- Length is A000120.
- Sum is A029837(n+1) (or sometimes A070939).
- Parts are listed by A066099.
- Number of adjacent equal pairs is A124762, unequal A333382.
- Number of max runs: A124765, A124767, A333381.
- Run-length transform is A333627, sum A070939.
- Run-compression transform is A373948, sum A373953, excess A373954.
- Ranks of contiguous compositions are A374249, counted by A274174.
- Ranks of non-contiguous compositions are A374253, counted by A335548.
Cf. A106356, A188920, A189076, A238343, A272919, A333213, A373949, A374700.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[First/@Split[stc[n],Less],{n,0,100}]

A374740 Irregular triangle read by rows where row n lists the leaders of weakly decreasing runs in the n-th composition in standard order.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Jul 24 2024

The leaders of weakly decreasing runs in a sequence are obtained by splitting it into maximal weakly decreasing subsequences and taking the first term of each.

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The maximal weakly decreasing subsequences of the 1234567th composition in standard order are ((3,2,1),(2,2,1),(2),(5,1,1,1)), so row 1234567 is (3,2,2,5).
The nonnegative integers, corresponding compositions, and leaders of weakly decreasing runs begin:
    0: () -> ()           15: (1,1,1,1) -> (1)
    1: (1) -> (1)         16: (5) -> (5)
    2: (2) -> (2)         17: (4,1) -> (4)
    3: (1,1) -> (1)       18: (3,2) -> (3)
    4: (3) -> (3)         19: (3,1,1) -> (3)
    5: (2,1) -> (2)       20: (2,3) -> (2,3)
    6: (1,2) -> (1,2)     21: (2,2,1) -> (2)
    7: (1,1,1) -> (1)     22: (2,1,2) -> (2,2)
    8: (4) -> (4)         23: (2,1,1,1) -> (2)
    9: (3,1) -> (3)       24: (1,4) -> (1,4)
   10: (2,2) -> (2)       25: (1,3,1) -> (1,3)
   11: (2,1,1) -> (2)     26: (1,2,2) -> (1,2)
   12: (1,3) -> (1,3)     27: (1,2,1,1) -> (1,2)
   13: (1,2,1) -> (1,2)   28: (1,1,3) -> (1,3)
   14: (1,1,2) -> (1,2)   29: (1,1,2,1) -> (1,2)

Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

Row-leaders are A065120.
Row-lengths are A124765.
Other types of runs are A374251, A374515, A374683, A374757.
The opposite is A374629.
Positions of distinct (strict) rows are A374701, counted by A374743.
Row-sums are A374741, opposite A374630.
Positions of identical rows are A374744, counted by A374742.
All of the following pertain to compositions in standard order:
- Length is A000120.
- Sum is A029837(n+1) (or sometimes A070939).
- Parts are listed by A066099.
- Number of adjacent equal pairs is A124762, unequal A333382.
- Number of max runs: A124765, A124766, A124767, A124768, A124769, A333381.
- Ranks of anti-run compositions are A333489, counted by A003242.
- Run-length transform is A333627, sum A070939.
- Run-compression transform is A373948, sum A373953, excess A373954.
- Ranks of contiguous compositions are A374249, counted by A274174.
- Ranks of non-contiguous compositions are A374253, counted by A335548.
Cf. A106356, A188920, A189076, A238343, A272919, A333213, A373949, A374634, A374635, A374637.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[First/@Split[stc[n],GreaterEqual],{n,0,100}]

cp's OEIS Frontend

A188920 a(n) is the limiting term of the n-th column of the triangle in A188919.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A124765 Number of monotonically decreasing runs for compositions in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A124769 Number of strictly decreasing runs for compositions in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A344604 Number of alternating compositions of n, including twins (x,x).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A344614 Number of compositions of n with no adjacent triples (..., x, y, z, ...) where x < y < z or x > y > z.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A374632 Number of integer compositions of n whose leaders of weakly increasing runs are distinct.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A374635 Number of integer compositions of n whose leaders of weakly increasing runs are themselves weakly increasing.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI