A333755 -id:A333755 - cp's OEIS frontend

A124767 Number of level runs for compositions in standard order.

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

Offset: 0

Franklin T. Adams-Watters, Nov 06 2006

The standard order of compositions is given by A066099.

For n > 0, a(n) is one more than the number of adjacent unequal terms in the n-th composition in standard order. Also the number of runs in the same composition. - Gus Wiseman, Apr 08 2020

			Composition number 11 is 2,1,1; the level runs are 2; 1,1; so a(11) = 2.
The table starts:
  0
  1
  1 1
  1 2 2 1
  1 2 1 2 2 3 2 1
  1 2 2 2 2 2 3 2 2 3 2 3 2 3 2 1
  1 2 2 2 1 3 3 2 2 3 1 2 3 4 3 2 2 3 3 3 3 3 4 3 2 3 2 3 2 3 2 1
The 1234567th composition in standard order is (3,2,1,2,2,1,2,5,1,1,1) with runs ((3),(2),(1),(2,2),(1),(2),(5),(1,1,1)), so a(1234567) = 8. - _Gus Wiseman_, Apr 08 2020

Row-lengths are A011782.
Compositions counted by number of runs are A238279 or A333755.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Sum is A070939.
- Weakly decreasing compositions are A114994.
- Adjacent equal pairs are counted by A124762.
- Weakly decreasing runs are counted by A124765.
- Weakly increasing runs are counted by A124766.
- Equal runs are counted by A124767 (this sequence).
- Weakly increasing compositions are A225620.
- Strict compositions A233564.
- Constant compositions are A272919.
- Anti-runs are counted by A333381.
- Adjacent unequal pairs are counted by A333382.
- Anti-run compositions are A333489.
- Runs-resistance is A333628.
- Run-lengths are A333769 (triangle).
Cf. A029931, A048793, A066099, A106356, A228351, A318928, A329744, A333217, A333219, A333627.

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

a(0) = 0, a(n) = 1 + Sum_{1<=i=1 0.

For n > 0, a(n) = A333382(n) + 1. - Gus Wiseman, Apr 08 2020

A025047 Number of alternating compositions, i.e., compositions with alternating increases and decreases, starting with either an increase or a decrease.

Original entry on oeis.org

1, 1, 1, 3, 4, 7, 12, 19, 29, 48, 75, 118, 186, 293, 460, 725, 1139, 1789, 2814, 4422, 6949, 10924, 17168, 26979, 42404, 66644, 104737, 164610, 258707, 406588, 639009, 1004287, 1578363, 2480606, 3898599, 6127152, 9629623, 15134213, 23785388, 37381849, 58750468

Offset: 0

David W. Wilson

nonn

Original name: Wiggly sums: number of sums adding to n in which terms alternately increase and decrease or vice versa.

			From _Joerg Arndt_, Dec 28 2012: (Start)
There are a(7)=19 such compositions of 7:
[ 1] +  [ 1 2 1 2 1 ]
[ 2] +  [ 1 2 1 3 ]
[ 3] +  [ 1 3 1 2 ]
[ 4] +  [ 1 4 2 ]
[ 5] +  [ 1 5 1 ]
[ 6] +  [ 1 6 ]
[ 7] -  [ 2 1 3 1 ]
[ 8] -  [ 2 1 4 ]
[ 9] +  [ 2 3 2 ]
[10] +  [ 2 4 1 ]
[11] +  [ 2 5 ]
[12] -  [ 3 1 2 1 ]
[13] -  [ 3 1 3 ]
[14] +  [ 3 4 ]
[15] -  [ 4 1 2 ]
[16] -  [ 4 3 ]
[17] -  [ 5 2 ]
[18] -  [ 6 1 ]
[19] 0  [ 7 ]
For A025048(7)-1=10 of these the first two parts are increasing (marked by '+'),
and for A025049(7)-1=8 the first two parts are decreasing (marked by '-').
The composition into one part is counted by both A025048 and A025049.
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..3333
Edward A. Bender and E. Rodney Canfield, Locally Restricted Compositions III. Adjacent-Part Periodic Inequalities, Electronic Journal of Combinatorics 17 (2010), #R145.

Dominated by A003242 (anti-run compositions), complement A261983.
The ascending case is A025048.
The descending case is A025049.
The version allowing pairs (x,x) is A344604.
These compositions are ranked by A345167, permutations A349051.
The complement is counted by A345192, ranked by A345168.
The version for patterns is A345194 (with twins: A344605).
A001250 counts alternating permutations, complement A348615.
A011782 counts compositions.
A032020 counts strict compositions.
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A274174 counts compositions with equal parts contiguous.
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A345164 counts alternating permutations of prime indices.
A345165 counts partitions w/o alternating permutation, ranked by A345171.
A345170 counts partitions w/ alternating permutation, ranked by A345172.
Cf. A000070, A008965, A238279, A333755, A344606, A344614, A344653, A344740, A345163, A345166, A345169.

b:= proc(n, l, t) option remember; `if`(n=0, 1, add(
      b(n-j, j, 1-t), j=`if`(t=1, 1..min(l-1, n), l+1..n)))
    end:
a:= n-> 1+add(add(b(n-j, j, i), i=0..1), j=1..n-1):
seq(a(n), n=0..40);  # Alois P. Heinz, Jan 31 2024

wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],wigQ]],{n,0,15}] (* Gus Wiseman, Jun 17 2021 *)

D(n,f)={my(M=matrix(n,n,j,k,k>=j), s=M[,n]); for(b=1, n, f=!f; M=matrix(n,n,j,k,if(k1, M[j-k,k-1]), M[j-k,n]-M[j-k,k] ))); for(k=2, n, M[,k]+=M[,k-1]); s+=M[,n]); s~}
seq(n) = concat([1], D(n,0) + D(n,1) - vector(n,j,1)) \\ Andrew Howroyd, Jan 31 2024

a(n) = A025048(n) + A025049(n) - 1 = sum_k[A059881(n, k)] = sum_k[S(n, k) + T(n, k)] - 1 where if n>k>0 S(n, k) = sum_j[T(n - k, j)] over j>k and T(n, k) = sum_j[S(n - k, j)] over k>j (note reversal) and if n>0 S(n, n) = T(n, n) = 1; S(n, k) = A059882(n, k), T(n, k) = A059883(n, k). - Henry Bottomley, Feb 05 2001
a(n) ~ c * d^n, where d = 1.571630806607064114100138865739690782401305155950789062725..., c = 0.82222360450823867604750473815253345888526601460811483897... . - Vaclav Kotesovec, Sep 12 2014
a(n) = A344604(n) + 1 - n mod 2. - Gus Wiseman, Jun 17 2021

Better name using a comment of Franklin T. Adams-Watters by Peter Luschny, Oct 31 2021

A102726 Number of compositions of the integer n into positive parts that avoid a fixed pattern of three letters.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 31, 60, 114, 214, 398, 732, 1334, 2410, 4321, 7688, 13590, 23869, 41686, 72405, 125144, 215286, 368778, 629156, 1069396, 1811336, 3058130, 5147484, 8639976, 14463901, 24154348, 40244877, 66911558, 111026746, 183886685, 304034456, 501877227

Offset: 0

Herbert S. Wilf, Feb 07 2005

The sequence is the same no matter which of the six patterns of three letters is chosen as the one to be avoided.

			a(6) = 31 because there are 32 compositions of 6 into positive parts and only one of these, namely 6 = 1+2+3, contains the pattern (123), the other 31 compositions of 6 avoid that pattern.

Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..900 (first 400 terms from Alois P. Heinz)
M. Elder and V. Vatter, Problems and conjectures presented at the third international conference on permutation petterns
Carla D. Savage and Herbert S. Wilf, Pattern avoidance in compositions and multiset permutations, Advances in Applied Mathematics 36 (2006), pp.194-201.
Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

The version for patterns is A226316.
These compositions are ranked by the complement of A335479.
The matching version is A335514.
The version for prime indices is A335521.
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Compositions are counted by A011782.
Strict compositions are counted by A032020 and ranked by A233564.
Patterns matched by compositions are counted by A335456.
Minimal patterns avoided by a given composition are counted by A335465.
Cf. A056986, A106356, A232464, A269134, A333755.

b:= proc(n, m, t) option remember; `if`(n=0, 1,
      add(b(n-i, min(m, i, n-i), min(t, n-i,
      `if`(i>m, i, t))), i=1..min(n, t)))
    end:
a:= n-> b(n$3):
seq(a(n), n=0..50);  # Alois P. Heinz, Mar 18 2014

b[n_, m_, t_] := b[n, m, t] = If[n == 0, 1, Sum[b[n - i, Min[m, i, n - i], Min[t, n - i, If[i > m, i, t]]], {i, 1, Min[n, t]}]];
a[n_] := b[n, n, n];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Nov 10 2017, after Alois P. Heinz *)
mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[Union[mstype/@Subsets[#]],{1,2,3}]&]],{n,0,10}] (* Gus Wiseman, Jun 22 2020 *)

seq(n)={Vec(sum(i=1, n, prod(j=1, n, if(i==j, 1, (1-x^i)/((1-x^(j-i))*(1-x^i-x^j))) + O(x*x^n))/(1-x^i)))} \\ Andrew Howroyd, Dec 31 2020

G.f.: Sum_{i>=1} (1/(1-x^i))*Product_{j>=1, j<>i} (1-x^i)/((1-x^(j-i))*(1-x^i-x^j)).

Asymptotics (Savage and Wilf, 2005): a(n) ~ c * ((1+sqrt(5))/2)^n, where c = r/(r-1)/(r-s) * (r * Product_{j>=3} (1-1/r)/(1-r^(1-j))/(1-1/r-r^(-j)) - Product_{j>=3} (1-1/r^2)/(1-r^(2-j))/(1-1/r^2-r^(-j)) ) = 18.9399867283479198666671671745270505487677312850521421513193261105... and r = (1+sqrt(5))/2, s = (1-sqrt(5))/2. - Vaclav Kotesovec, May 02 2014

More terms from Ralf Stephan, May 27 2005

A374629 Irregular triangle listing the leaders of maximal weakly increasing runs in the n-th composition in standard order.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Jul 20 2024

The leaders of maximal weakly increasing runs in a sequence are obtained by splitting it into maximal weakly 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 58654th composition in standard order is (1,1,3,2,4,1,1,1,2), with maximal weakly increasing runs ((1,1,3),(2,4),(1,1,1,2)), so row 58654 is (1,2,1).
The nonnegative integers, corresponding compositions, and leaders of maximal weakly increasing runs begin:
    0:      () -> ()      15: (1,1,1,1) -> (1)
    1:     (1) -> (1)     16:       (5) -> (5)
    2:     (2) -> (2)     17:     (4,1) -> (4,1)
    3:   (1,1) -> (1)     18:     (3,2) -> (3,2)
    4:     (3) -> (3)     19:   (3,1,1) -> (3,1)
    5:   (2,1) -> (2,1)   20:     (2,3) -> (2)
    6:   (1,2) -> (1)     21:   (2,2,1) -> (2,1)
    7: (1,1,1) -> (1)     22:   (2,1,2) -> (2,1)
    8:     (4) -> (4)     23: (2,1,1,1) -> (2,1)
    9:   (3,1) -> (3,1)   24:     (1,4) -> (1)
   10:   (2,2) -> (2)     25:   (1,3,1) -> (1,1)
   11: (2,1,1) -> (2,1)   26:   (1,2,2) -> (1)
   12:   (1,3) -> (1)     27: (1,2,1,1) -> (1,1)
   13: (1,2,1) -> (1,1)   28:   (1,1,3) -> (1)
   14: (1,1,2) -> (1)     29: (1,1,2,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 A124766.
Row-sums are A374630.
Positions of constant rows are A374633, counted by A374631.
Positions of strict rows are A374768, counted by A374632.
For other types of runs we have A374251, A374515, A374683, A374740, A374757.
Positions of non-weakly decreasing rows are A375137.
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
A335456 counts patterns matched by compositions.
All of the following pertain to compositions in standard order:
- Length is A000120.
- Sum is A029837(n+1).
- Leader is A065120.
- Parts are listed by A066099, reverse A228351.
- 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, length A124767, 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. A046660, A106356, A188920, A189076, A238343, A272919, A333213, A373949, A374634, A374635, A374637, A374701, A375123.

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

A373949 Triangle read by rows where T(n,k) is the number of integer compositions of n such that replacing each run of repeated parts with a single part (run-compression) yields a composition of k.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 0, 3, 0, 1, 1, 2, 4, 0, 1, 0, 4, 4, 7, 0, 1, 1, 5, 6, 5, 14, 0, 1, 0, 6, 10, 10, 14, 23, 0, 1, 1, 6, 14, 12, 29, 26, 39, 0, 1, 0, 9, 16, 19, 40, 54, 46, 71, 0, 1, 1, 8, 22, 22, 64, 82, 96, 92, 124, 0, 1, 0, 10, 26, 30, 82, 137, 144, 204, 176, 214

Offset: 0

Gus Wiseman, Jun 28 2024

			Triangle begins:
   1
   0   1
   0   1   1
   0   1   0   3
   0   1   1   2   4
   0   1   0   4   4   7
   0   1   1   5   6   5  14
   0   1   0   6  10  10  14  23
   0   1   1   6  14  12  29  26  39
   0   1   0   9  16  19  40  54  46  71
   0   1   1   8  22  22  64  82  96  92 124
   0   1   0  10  26  30  82 137 144 204 176 214
   0   1   1  11  32  31 121 186 240 331 393 323 378
Row n = 6 counts the following compositions:
  .  (111111)  (222)  (33)     (3111)   (411)   (6)
                      (2211)   (1113)   (114)   (51)
                      (1122)   (1221)   (1311)  (15)
                      (21111)  (12111)  (1131)  (42)
                      (11112)  (11211)  (2112)  (24)
                               (11121)          (141)
                                                (321)
                                                (312)
                                                (231)
                                                (213)
                                                (132)
                                                (123)
                                                (2121)
                                                (1212)
For example, the composition (1,2,2,1) with compression (1,2,1) is counted under T(6,4).

John Tyler Rascoe, Rows n = 0..130, flattened

Column k = n is A003242 (anti-runs or compressed compositions).
Row-sums are A011782.
Same as A373951 with rows reversed.
Column k = 3 is A373952.
This statistic is represented by A373953, difference A373954.
A114901 counts compositions with no isolated parts.
A116861 counts partitions by compressed sum, by compressed length A116608.
A124767 counts runs in standard compositions, anti-runs A333381.
A240085 counts compositions with no unique parts.
A333755 counts compositions by compressed length.
A373948 represents the run-compression transformation.
Cf. A037201 (halved A373947), A106356, A124762, A238130, A238279, A238343, A285981, A333213, A333489, A373950.

Table[Length[Select[Join@@Permutations /@ IntegerPartitions[n],Total[First/@Split[#]]==k&]], {n,0,10},{k,0,n}]

T_xy(row_max) = {my(N=row_max+1, x='x+O('x^N), h=1/(1-sum(i=1,N, (y^i*x^i)/(1+x^i*(y^i-1))))); vector(N, n, Vecrev(polcoeff(h, n-1)))}
T_xy(13) \\ John Tyler Rascoe, Mar 20 2025

G.f.: 1/(1 - Sum_{i>0} (y^i * x^i)/(1 + x^i * (y^i - 1))). - John Tyler Rascoe, Mar 20 2025

A374249 Numbers k such that the k-th composition in standard order has its equal parts contiguous.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 23, 24, 26, 28, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 47, 48, 50, 52, 56, 58, 60, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 78, 79, 80, 81, 83, 84, 85

Offset: 1

Gus Wiseman, Jul 13 2024

nonn

These are compositions avoiding the patterns (1,2,1) and (2,1,2).

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 terms together with their standard compositions begin:
   0: ()
   1: (1)
   2: (2)
   3: (1,1)
   4: (3)
   5: (2,1)
   6: (1,2)
   7: (1,1,1)
   8: (4)
   9: (3,1)
  10: (2,2)
  11: (2,1,1)
  12: (1,3)
  14: (1,1,2)
  15: (1,1,1,1)
  16: (5)
See A374253 for the complement: 13, 22, 25, 27, 29, ...

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

The strict (also anti-run) case is A233564, counted by A032020.
Compositions of this type are counted by A274174.
Permutations of prime indices of this type are counted by A333175.
The complement is A374253 (anti-run A374254), counted by A335548.
A003242 counts anti-run compositions, ranks A333489.
A011782 counts compositions.
A066099 lists compositions in standard order.
A124767 counts runs in standard compositions, anti-runs A333381.
A333755 counts compositions by number of runs.
A335454 counts patterns matched by standard compositions.
A335462 counts (1,2,1)- and (2,1,2)-matching permutations of prime indices.
- A335470 counts (1,2,1)-matching compositions, ranks A335466.
- A335471 counts (1,2,1)-avoiding compositions, ranks A335467.
- A335472 counts (2,1,2)-matching compositions, ranks A335468.
- A335473 counts (2,1,2)-avoiding compositions, ranks A335469.
Cf. A106356, A124762, A238130, A238279, A261982, A272919, A333382, A335450, A335460, A335524, A335525.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],UnsameQ@@First/@Split[stc[#]]&]

Equals A335467 /\ A335469.

A189076 Number of compositions of n that avoid the pattern 23-1.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 31, 61, 118, 228, 440, 846, 1623, 3111, 5955, 11385, 21752, 41530, 79250, 151161, 288224, 549408, 1047034, 1995000, 3800662, 7239710, 13789219, 26261678, 50012275, 95237360, 181350695, 345315255, 657506300, 1251912618, 2383636280, 4538364446

Offset: 0

N. J. A. Sloane, Apr 16 2011

nonn

Note that an exponentiation ^(-1) is missing in Example 4.4. The notation in Theorem 4.3 is complete.

Theorem: The reverse of a composition avoids 23-1 iff its leaders of maximal weakly increasing runs are weakly decreasing. For example, the composition y = (3,2,1,2,2,1,2,5,1,1,1) has maximal weakly increasing runs ((3),(2),(1,2,2),(1,2,5),(1,1,1)), with leaders (3,2,1,1,1), which are weakly decreasing, so the reverse of y is counted under a(21). - Gus Wiseman, Aug 19 2024

			From _Gus Wiseman_, Aug 19 2024: (Start)
The a(6) = 31 compositions:
  .  (6)  (5,1)  (4,1,1)  (3,1,1,1)  (2,1,1,1,1)  (1,1,1,1,1,1)
          (1,5)  (1,4,1)  (1,3,1,1)  (1,2,1,1,1)
          (4,2)  (1,1,4)  (1,1,3,1)  (1,1,2,1,1)
          (2,4)  (3,2,1)  (1,1,1,3)  (1,1,1,2,1)
          (3,3)  (3,1,2)  (2,2,1,1)  (1,1,1,1,2)
                 (2,3,1)  (2,1,2,1)
                 (2,1,3)  (2,1,1,2)
                 (1,2,3)  (1,2,2,1)
                 (2,2,2)  (1,2,1,2)
                          (1,1,2,2)
Missing is (1,3,2), reverse of (2,3,1).
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..300
S. Heubach, T. Mansour and A. O. Munagi, Avoiding Permutation Patterns of Type (2,1) in Compositions, Online Journal of Analytic Combinatorics, 4 (2009).
Wikipedia, Permutation pattern.
Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

The non-dashed version is A102726.
The version for 3-12 is A188900, complement A375406.
Avoiding 12-1 also gives A188920 in reverse.
The version for 13-2 is A189077.
For identical leaders we have A374631, ranks A374633.
For distinct leaders we have A374632, ranks A374768.
The complement is counted by A374636, ranks A375137.
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
Cf. A056823, A188919, A238343, A274174, A333213, A335480, A358836, A374635.

A189075 := proc(n) local g,i; g := 1; for i from 1 to n do 1-x^i/mul ( 1-x^j,j=i+1..n-i) ; g := g*% ; end do: g := expand(1/g) ; g := taylor(g,x=0,n+1) ; coeftayl(g,x=0,n) ; end proc: # R. J. Mathar, Apr 16 2011

a[n_] := Module[{g = 1, xi}, Do[xi = 1 - x^i/Product[1 - x^j, {j, i+1, n-i}]; g = g xi, {i, n}]; SeriesCoefficient[1/g, {x, 0, n}]];
a /@ Range[0, 32] (* Jean-François Alcover, Apr 02 2020, after R. J. Mathar *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,y_,z_,_,x_,_}/;xGus Wiseman, Aug 19 2024 *)

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

Original entry on oeis.org

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

A345192 Number of non-alternating compositions of n.

Original entry on oeis.org

0, 0, 1, 1, 4, 9, 20, 45, 99, 208, 437, 906, 1862, 3803, 7732, 15659, 31629, 63747, 128258, 257722, 517339, 1037652, 2079984, 4167325, 8346204, 16710572, 33449695, 66944254, 133959021, 268028868, 536231903, 1072737537, 2145905285, 4292486690, 8586035993, 17173742032, 34350108745, 68704342523, 137415168084

Offset: 0

Gus Wiseman, Jun 17 2021

nonn

First differs from A261983 at a(6) = 20, A261983(6) = 18.

A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,2,2,2,1) has no alternating permutations, even though it does have the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2).

			The a(2) = 1 through a(6) = 20 compositions:
  (11)  (111)  (22)    (113)    (33)
               (112)   (122)    (114)
               (211)   (221)    (123)
               (1111)  (311)    (222)
                       (1112)   (321)
                       (1121)   (411)
                       (1211)   (1113)
                       (2111)   (1122)
                       (11111)  (1131)
                                (1221)
                                (1311)
                                (2112)
                                (2211)
                                (3111)
                                (11112)
                                (11121)
                                (11211)
                                (12111)
                                (21111)
                                (111111)

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

The complement is counted by A025047 (ascend: A025048, descend: A025049).
Dominates A261983 (non-anti-run compositions), ranked by A348612.
These compositions are ranked by A345168, complement A345167.
The case without twins is A348377.
The version for factorizations is A348613.
A001250 counts alternating permutations, complement A348615.
A003242 counts anti-run compositions.
A011782 counts compositions.
A032020 counts strict compositions.
A106356 counts compositions by number of maximal anti-runs.
A114901 counts compositions where each part is adjacent to an equal part.
A274174 counts compositions with equal parts contiguous.
A325534 counts separable partitions, ranked by A335433.
A325535 counts inseparable partitions, ranked by A335448.
A344604 counts alternating compositions with twins.
A344605 counts alternating patterns with twins.
A344654 counts non-twin partitions with no alternating permutation.
A345162 counts normal partitions with no alternating permutation.
A345164 counts alternating permutations of prime indices.
A345170 counts partitions w/ alternating permutation, ranked by A345172.
A345165 counts partitions w/o alternating permutation, ranked by A345171.
Patterns:
- A128761 avoiding (1,2,3) adjacent.
- A344614 avoiding (1,2,3) and (3,2,1) adjacent.
- A344615 weakly avoiding (1,2,3) adjacent.
Cf. A000070, A008965, A178470, A238279, A333755, A335126, A344606, A344653, A344740, A345163, A345166, A345169, A345173, A348380.

wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!wigQ[#]&]],{n,0,15}]

a(n) = A011782(n) - A025047(n).

A353837 Number of integer partitions of n with all distinct run-sums.

Original entry on oeis.org

1, 1, 2, 3, 4, 7, 10, 14, 17, 28, 35, 49, 62, 85, 107, 149, 174, 238, 305, 384, 476, 614, 752, 950, 1148, 1451, 1763, 2205, 2654, 3259, 3966, 4807, 5773, 7039, 8404, 10129, 12140, 14528, 17288, 20668, 24505, 29062, 34437, 40704, 48059, 56748, 66577, 78228

Offset: 0

Gus Wiseman, May 26 2022

nonn

The run-sums of a sequence are the sums of its maximal consecutive constant subsequences (runs). For example, the run-sums of (2,2,1,1,1,3,2,2) are (4,3,3,4). The first partition whose run-sums are not all distinct is (2,1,1).

			The a(0) = 1 through a(6) = 10 partitions:
  ()  (1)  (2)   (3)    (4)     (5)      (6)
           (11)  (21)   (22)    (32)     (33)
                 (111)  (31)    (41)     (42)
                        (1111)  (221)    (51)
                                (311)    (222)
                                (2111)   (321)
                                (11111)  (411)
                                         (2211)
                                         (21111)
                                         (111111)

Max Alekseyev, Table of n, a(n) for n = 0..100

For multiplicities instead of run-sums we have A098859, ranked by A130091.
For equal run-sums we have A304442, ranked by A353833 (nonprime A353834).
These partitions are ranked by A353838, complement A353839.
The version for compositions is A353850, ranked by A353852.
The weak version (rucksack partitions) is A353864, ranked by A353866.
The weak perfect version is A353865, ranked by A353867.
A005811 counts runs in binary expansion.
A275870 counts collapsible partitions, ranked by A300273.
A351014 counts distinct runs in standard compositions.
A353832 represents the operation of taking run-sums of a partition.
A353840-A353846 pertain to partition run-sum trajectory.
A353849 counts distinct run-sums in standard compositions.
Cf. A000041, A008284, A047966, A071625, A073093, A116608, A175413, A181819, A333755, A353848, A353867.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@Total/@Split[#]&]],{n,0,15}]

a353837 = lambda n: sum( abs(BipartiteGraph( Matrix(len(p), len(D:=list(set.union(*map(lambda t: set(divisors(t)),p)))), lambda i,j: p[i]%D[j]==0) ).matching_polynomial()[len(D)-len(p)]) for p in Partitions(n,max_slope=-1) ) # Max Alekseyev, Sep 11 2023

cp's OEIS Frontend

A124767 Number of level runs for compositions in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A025047 Number of alternating compositions, i.e., compositions with alternating increases and decreases, starting with either an increase or a decrease.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A102726 Number of compositions of the integer n into positive parts that avoid a fixed pattern of three letters.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A374629 Irregular triangle listing the leaders of maximal weakly increasing runs in the n-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A373949 Triangle read by rows where T(n,k) is the number of integer compositions of n such that replacing each run of repeated parts with a single part (run-compression) yields a composition of k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A374249 Numbers k such that the k-th composition in standard order has its equal parts contiguous.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A189076 Number of compositions of n that avoid the pattern 23-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs