A238130 -id:A238130 - 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

A114901 Number of compositions of n such that each part is adjacent to an equal part.

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 5, 3, 10, 10, 21, 22, 49, 51, 105, 126, 233, 292, 529, 678, 1181, 1585, 2654, 3654, 6016, 8416, 13606, 19395, 30840, 44517, 70087, 102070, 159304, 233941, 362429, 535520, 825358, 1225117, 1880220, 2801749, 4285086, 6404354, 9769782, 14634907

Offset: 0

Christian G. Bower, Jan 05 2006

nonn

			The 5 compositions of 6 are 3+3, 2+2+2, 2+2+1+1, 1+1+2+2, 1+1+1+1+1+1.
From _Gus Wiseman_, Nov 25 2019: (Start)
The a(2) = 1 through a(9) = 10 compositions:
  (11)  (111)  (22)    (11111)  (33)      (11122)    (44)        (333)
               (1111)           (222)     (22111)    (1133)      (11133)
                                (1122)    (1111111)  (2222)      (33111)
                                (2211)               (3311)      (111222)
                                (111111)             (11222)     (222111)
                                                     (22211)     (1111122)
                                                     (111122)    (1112211)
                                                     (112211)    (1122111)
                                                     (221111)    (2211111)
                                                     (11111111)  (111111111)
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..4000
N. J. A. Sloane, Transforms

The case of partitions is A007690.
Compositions with no adjacent parts equal are A003242.
Compositions with all multiplicities > 1 are A240085.
Compositions with minimum multiplicity 1 are A244164.
Compositions with at least two adjacent parts equal are A261983.
Cf. A178470, A238130, A274174, A329863.

g:= proc(n, i) option remember; add(b(n-i*j, i), j=2..n/i) end:
b:= proc(n, l) option remember; `if`(n=0, 1,
      add(`if`(i=l, 0, g(n,i)), i=1..n/2))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Nov 29 2019

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Min@@Length/@Split[#]>1&]],{n,0,10}] (* Gus Wiseman, Nov 25 2019 *)
g[n_, i_] := g[n, i] = Sum[b[n - i*j, i], {j, 2, n/i}] ;
b[n_, l_] := b[n, l] = If[n==0, 1, Sum[If[i==l, 0, g[n, i]], {i, 1, n/2}]];
a[n_] := b[n, 0];
a /@ Range[0, 50] (* Jean-François Alcover, May 23 2021, after Alois P. Heinz *)

A_x(N,k) = { my(x='x+O('x^N), g=1/(1-sum(i=1,N,sum(j=k+1,N, x^(i*j))/(1+ sum(j=k+1,N, x^(i*j)))))); Vec(g)}
A_x(50,1) \\ John Tyler Rascoe, May 17 2024

INVERT(iMOEBIUS(iINVERT(A000012 shifted right 2 places)))

G.f.: A(x,1) is the k = 1 case of A(x,k) = 1/(1 - Sum_{i>0} ( (Sum_{j>k} x^(i*j))/(1 + Sum_{j>k} x^(i*j)) )) where A(x,k) is the g.f. for compositions of n with all run-lengths > k. - John Tyler Rascoe, May 16 2024

A373948 Run-compression encoded as a transformation of compositions in standard order.

Original entry on oeis.org

0, 1, 2, 1, 4, 5, 6, 1, 8, 9, 2, 5, 12, 13, 6, 1, 16, 17, 18, 9, 20, 5, 22, 5, 24, 25, 6, 13, 12, 13, 6, 1, 32, 33, 34, 17, 4, 37, 38, 9, 40, 41, 2, 5, 44, 45, 22, 5, 48, 49, 50, 25, 52, 13, 54, 13, 24, 25, 6, 13, 12, 13, 6, 1, 64, 65, 66, 33, 68, 69, 70, 17, 72

Offset: 0

Gus Wiseman, Jun 24 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).
For the present sequence, the a(n)-th composition in standard order is obtained by compressing the n-th composition in standard order.

			The standard compositions and their compressions begin:
   0: ()        -->  0: ()
   1: (1)       -->  1: (1)
   2: (2)       -->  2: (2)
   3: (1,1)     -->  1: (1)
   4: (3)       -->  4: (3)
   5: (2,1)     -->  5: (2,1)
   6: (1,2)     -->  6: (1,2)
   7: (1,1,1)   -->  1: (1)
   8: (4)       -->  8: (4)
   9: (3,1)     -->  9: (3,1)
  10: (2,2)     -->  2: (2)
  11: (2,1,1)   -->  5: (2,1)
  12: (1,3)     --> 12: (1,3)
  13: (1,2,1)   --> 13: (1,2,1)
  14: (1,1,2)   -->  6: (1,2)
  15: (1,1,1,1) -->  1: (1)

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

Positions of 1's are A000225.
The image is A333489, counted by A003242.
Sum of standard composition for a(n) is given by A373953, length A124767.
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 compressed sum, by length A116608.
A240085 counts compositions with no unique parts.
A333755 counts compositions by compressed length.
A373949 counts compositions by compressed sum, opposite A373951.
Cf. A106356, A124762, A238130, A238279, A272919, A333381, A333382, A333627, A373952, A373954.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
stcinv[q_]:=Total[2^(Accumulate[Reverse[q]])]/2;
Table[stcinv[First/@Split[stc[n]]],{n,0,30}]

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

A000120(a(n)) = A124767(n).

A373953 Sum of run-compression of the n-th integer composition in standard order.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, Jun 25 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 standard compositions and their compressions and compression sums begin:
   0: ()        --> ()      --> 0
   1: (1)       --> (1)     --> 1
   2: (2)       --> (2)     --> 2
   3: (1,1)     --> (1)     --> 1
   4: (3)       --> (3)     --> 3
   5: (2,1)     --> (2,1)   --> 3
   6: (1,2)     --> (1,2)   --> 3
   7: (1,1,1)   --> (1)     --> 1
   8: (4)       --> (4)     --> 4
   9: (3,1)     --> (3,1)   --> 4
  10: (2,2)     --> (2)     --> 2
  11: (2,1,1)   --> (2,1)   --> 3
  12: (1,3)     --> (1,3)   --> 4
  13: (1,2,1)   --> (1,2,1) --> 4
  14: (1,1,2)   --> (1,2)   --> 3
  15: (1,1,1,1) --> (1)     --> 1

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

Positions of 1's are A000225.
Counting partitions by this statistic gives A116861, by length A116608.
For length instead of sum we have A124767, counted by A238279 and A333755.
Compositions counted by this statistic are A373949, opposite A373951.
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.
A240085 counts compositions with no unique parts.
A333489 ranks anti-runs, counted by A003242.
Cf. A106356, A124762, A238130, A238343, A272919, A285981, A333381, A333382, A333627, A373952, A373954.

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

a(n) = A029837(A373948(n)).

A351013 Number of integer compositions of n with all distinct runs.

Original entry on oeis.org

1, 1, 2, 4, 7, 14, 26, 48, 88, 161, 294, 512, 970, 1634, 2954, 5156, 9119, 15618, 27354, 46674, 80130, 138078, 232286, 394966, 665552, 1123231, 1869714, 3146410, 5186556, 8620936, 14324366, 23529274, 38564554, 63246744, 103578914, 167860584, 274465845

Offset: 0

Gus Wiseman, Feb 09 2022

nonn

			The a(1) = 1 through a(5) = 14 compositions:
  (1)  (2)    (3)      (4)        (5)
       (1,1)  (1,2)    (1,3)      (1,4)
              (2,1)    (2,2)      (2,3)
              (1,1,1)  (3,1)      (3,2)
                       (1,1,2)    (4,1)
                       (2,1,1)    (1,1,3)
                       (1,1,1,1)  (1,2,2)
                                  (2,2,1)
                                  (3,1,1)
                                  (1,1,1,2)
                                  (1,1,2,1)
                                  (1,2,1,1)
                                  (2,1,1,1)
                                  (1,1,1,1,1)
For example, the composition c = (3,1,1,1,1,2,1,1,3,4,1,1) has runs (3), (1,1,1,1), (2), (1,1), (3), (4), (1,1), and since (3) and (1,1) both appear twice, c is not counted under a(20).

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Mathematics Stack Exchange, What is a sequence run? (answered 2011-12-01)

The version for run-lengths instead of runs is A329739, normal A329740.
These compositions are ranked by A351290, complement A351291.
A000005 counts constant compositions, ranked by A272919.
A005811 counts runs in binary expansion.
A011782 counts integer compositions.
A059966 counts binary Lyndon compositions, necklaces A008965, aperiodic A000740.
A116608 counts compositions by number of distinct parts.
A238130 and A238279 count compositions by number of runs.
A242882 counts compositions with distinct multiplicities.
A297770 counts distinct runs in binary expansion.
A325545 counts compositions with distinct differences.
A329744 counts compositions by runs-resistance.
A351014 counts distinct runs in standard compositions.
Counting words with all distinct runs:
- A351016 = binary words, for run-lengths A351017.
- A351018 = binary expansions, for run-lengths A032020, ranked by A175413.
- A351200 = patterns, for run-lengths A351292.
- A351202 = permutations of prime factors.
Cf. A003242, A025047, A044813, A098504, A098859, A106356, A329738, A328592, A334028, A351015, A351201, A351204.

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

\\ here LahI is A111596 as row polynomials.
LahI(n,y) = {sum(k=1, n, y^k*(-1)^(n-k)*(n!/k!)*binomial(n-1, k-1))}
S(n) = {my(p=prod(k=1, n, 1 + y*x^k + O(x*x^n))); 1 + sum(i=1, (sqrtint(8*n+1)-1)\2, polcoef(p,i,y)*LahI(i,y))}
seq(n)={my(q=S(n)); [subst(serlaplace(p),y,1) | p<-Vec(prod(k=1, n, subst(q + O(x*x^(n\k)), x, x^k)))]} \\ Andrew Howroyd, Feb 12 2022

Terms a(26) and beyond from Andrew Howroyd, Feb 12 2022

A037201 Differences between consecutive primes (A001223) but with repeats omitted.

Original entry on oeis.org

1, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 2, 6, 4, 2, 6, 4, 6, 8, 4, 2, 4, 2, 4, 14, 4, 6, 2, 10, 2, 6, 4, 6, 2, 10, 2, 4, 2, 12, 4, 2, 4, 6, 2, 10, 6, 2, 6, 4, 2, 10, 14, 4, 2, 4, 14, 6, 10, 2, 4, 6, 8, 6, 4, 6, 8, 4, 8, 10, 2, 10, 2, 6, 4, 6, 8, 4

Offset: 1

Naohiro Nomoto

Also the run-compression of the sequence of first differences of prime numbers, where 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, we can remove all parts equal to the part immediately to their left. For example, (1,1,2,2,1) has run-compression (1,2,1). - Gus Wiseman, Sep 16 2024

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for primes, gaps between

This is the run-compression of A001223 = first differences of A000040.
The repeats were at positions A064113 before being omitted.
Adding up runs instead of compressing them gives A373822.
The even terms halved are A373947.
For prime-powers instead of prime numbers we have A376308.
Positions of first appearances are A376520, sorted A376521.
A003242 counts compressed compositions.
A333254 lists run-lengths of differences between consecutive primes.
A373948 encodes compression using compositions in standard order.
Cf. A007921, A030173, A053289, A106356, A114901, A116608, A116861, A124767, A238130, A333755, A335406, A373954.

a037201 n = a037201_list !! (n-1)
a037201_list = f a001223_list where
   f (x:xs@(x':_)) | x == x'   = f xs
                   | otherwise = x : f xs
-- Reinhard Zumkeller, Feb 27 2012

Flatten[Split[Differences[Prime[Range[150]]]]/.{(k_)..}:>k] (* based on a program by Harvey P. Dale, Jun 21 2012 *)

t=0;p=2;forprime(q=3,1e3,if(q-p!=t,print1(q-p", "));t=q-p;p=q) \\ Charles R Greathouse IV, Feb 27 2012

a(n>1) = 2*A373947(n-1). - Gus Wiseman, Sep 16 2024

Offset corrected by Reinhard Zumkeller, Feb 27 2012

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

A175413 Those positive integers n that when written in binary, the lengths of the runs of 1 are distinct and the lengths of the runs of 0's are distinct.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 8, 11, 12, 13, 14, 15, 16, 19, 23, 24, 25, 28, 29, 30, 31, 32, 35, 38, 39, 44, 47, 48, 49, 50, 52, 55, 56, 57, 59, 60, 61, 62, 63, 64, 67, 70, 71, 78, 79, 88, 92, 95, 96, 97, 98, 103, 104, 111, 112, 113, 114, 115, 116, 120, 121, 123, 124, 125

Offset: 1

Leroy Quet, May 07 2010

A044813 contains those positive integers that when written in binary, have all run-lengths (of both 0's and 1's) distinct.
A175414 contains those positive integers in A175413 that are not in A044813. (A175414 contains those positive integers that when written in binary, at least one run of 0's is the same length as one run of 1's, even though all run of 0 are of distinct length and all runs of 1's are of distinct length.)
Also numbers whose binary expansion has all distinct runs (not necessarily run-lengths). - Gus Wiseman, Feb 21 2022

Alois P. Heinz, Table of n, a(n) for n = 1..20000

Cf. A044813, A175414.
Runs in binary expansion are counted by A005811, distinct A297770.
The complement is A351205.
The version for standard compositions is A351290, complement A351291.
A000120 counts binary weight.
A242882 counts compositions with distinct multiplicities.
A318928 gives runs-resistance of binary expansion.
A325545 counts compositions with distinct differences.
A333489 ranks anti-runs, complement A348612, counted by A003242.
A334028 counts distinct parts in standard compositions.
A351014 counts distinct runs in standard compositions.
Counting words with all distinct runs:
- A351013 = compositions, for run-lengths A329739.
- A351016 = binary words, for run-lengths A351017.
- A351018 = binary expansions, for run-lengths A032020.
- A351200 = patterns, for run-lengths A351292.
- A351202 = permutations of prime factors.
Cf. A070939, A085207, A098859, A233564, A238130 or A238279, A283353, A328592, A350952, A351015, A351203.

q:= proc(n) uses ListTools; (l-> is(nops(l)=add(
      nops(i), i={Split(`=`, l, 1)}) +add(
      nops(i), i={Split(`=`, l, 0)})))(Bits[Split](n))
    end:
select(q, [$1..200])[];  # Alois P. Heinz, Mar 14 2022

f[n_] := And@@Unequal@@@Transpose[Partition[Length/@Split[IntegerDigits[n, 2]], 2, 2, {1,1}, 0]]; Select[Range[125], f] (* Ray Chandler, Oct 21 2011 *)
Select[Range[0,100],UnsameQ@@Split[IntegerDigits[#,2]]&] (* Gus Wiseman, Feb 21 2022 *)

from itertools import groupby, product
def ok(n):
    runs = [(k, len(list(g))) for k, g in groupby(bin(n)[2:])]
    return len(runs) == len(set(runs))
print([k for k in range(1, 125) if ok(k)]) # Michael S. Branicky, Feb 22 2022

Extended by Ray Chandler, Oct 21 2011

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

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

A114901 Number of compositions of n such that each part is adjacent to an equal part.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A373948 Run-compression encoded as a transformation of compositions in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A373953 Sum of run-compression of the n-th integer composition in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A351013 Number of integer compositions of n with all distinct runs.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A037201 Differences between consecutive primes (A001223) but with repeats omitted.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs