A333213 -id:A333213 - cp's OEIS frontend

A238279 Triangle read by rows: T(n,k) is the number of compositions of n into nonzero parts with k parts directly followed by a different part, n>=0, 0<=k<=A004523(n-1).

1, 1, 2, 2, 2, 3, 4, 1, 2, 10, 4, 4, 12, 14, 2, 2, 22, 29, 10, 1, 4, 26, 56, 36, 6, 3, 34, 100, 86, 31, 2, 4, 44, 148, 200, 99, 16, 1, 2, 54, 230, 374, 278, 78, 8, 6, 58, 322, 680, 654, 274, 52, 2, 2, 74, 446, 1122, 1390, 814, 225, 22, 1, 4, 88, 573, 1796, 2714, 2058, 813, 136, 10, 4, 88, 778, 2694, 4927

Offset: 0

Joerg Arndt and Alois P. Heinz, Feb 22 2014

Same as A238130, with zeros omitted.
Last elements in rows are 1, 1, 2, 2, 1, 4, 2, 1, 6, 2, 1, 8, ... with g.f. -(x^6+x^4-2*x^2-x-1)/(x^6-2*x^3+1).
For n > 0, also the number of compositions of n with k + 1 runs. - Gus Wiseman, Apr 10 2020

			Triangle starts:
  00:  1;
  01:  1;
  02:  2;
  03:  2,   2;
  04:  3,   4,   1;
  05:  2,  10,   4;
  06:  4,  12,  14,    2;
  07:  2,  22,  29,   10,    1;
  08:  4,  26,  56,   36,    6;
  09:  3,  34, 100,   86,   31,    2;
  10:  4,  44, 148,  200,   99,   16,    1;
  11:  2,  54, 230,  374,  278,   78,    8;
  12:  6,  58, 322,  680,  654,  274,   52,    2;
  13:  2,  74, 446, 1122, 1390,  814,  225,   22,   1;
  14:  4,  88, 573, 1796, 2714, 2058,  813,  136,  10;
  15:  4,  88, 778, 2694, 4927, 4752, 2444,  618,  77,  2;
  16:  5, 110, 953, 3954, 8531, 9930, 6563, 2278, 415, 28, 1;
  ...
Row n=5 is 2, 10, 4 because in the 16 compositions of 5
  ##:  [composition]  no. of changes
  01:  [ 1 1 1 1 1 ]   0
  02:  [ 1 1 1 2 ]   1
  03:  [ 1 1 2 1 ]   2
  04:  [ 1 1 3 ]   1
  05:  [ 1 2 1 1 ]   2
  06:  [ 1 2 2 ]   1
  07:  [ 1 3 1 ]   2
  08:  [ 1 4 ]   1
  09:  [ 2 1 1 1 ]   1
  10:  [ 2 1 2 ]   2
  11:  [ 2 2 1 ]   1
  12:  [ 2 3 ]   1
  13:  [ 3 1 1 ]   1
  14:  [ 3 2 ]   1
  15:  [ 4 1 ]   1
  16:  [ 5 ]   0
there are 2 with no changes, 10 with one change, and 4 with two changes.

Joerg Arndt and Alois P. Heinz, Rows n = 0..180, flattened

Columns k=0-10 give: A000005 (for n>0), 2*A002133, A244714, A244715, A244716, A244717, A244718, A244719, A244720, A244721, A244722.
Row lengths are A004523.
Row sums are A011782.
The version counting adjacent equal parts is A106356.
The version for ascents/descents is A238343.
The version for weak ascents/descents is A333213.
The k-th composition in standard-order has A124762(k) adjacent equal parts, A124767(k) maximal runs, A333382(k) adjacent unequal parts, and A333381(k) maximal anti-runs.
Cf. A064113, A333214, A333216.

b:= proc(n, v) option remember; `if`(n=0, 1, expand(
      add(b(n-i, i)*`if`(v=0 or v=i, 1, x), i=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..14);

b[n_, v_] := b[n, v] = If[n == 0, 1, Expand[Sum[b[n-i, i]*If[v == 0 || v == i, 1, x], {i, 1, n}]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0]]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Feb 11 2015, after Maple *)
Table[If[n==0,1,Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[Split[#]]==k+1&]]],{n,0,12},{k,0,If[n==0,0,Floor[2*(n-1)/3]]}] (* Gus Wiseman, Apr 10 2020 *)

T_xy(max_row) = {my(N=max_row+1, x='x+O('x^N),h=(1+ sum(i=1,N,(x^i-y*x^i)/(1+y*x^i-x^i)))/(1-sum(i=1,N, y*x^i/(1+y*x^i-x^i)))); for(n=0,N-1, print(Vecrev(polcoeff(h,n))))}
T_xy(16) \\ John Tyler Rascoe, Jul 10 2024

G.f.: A(x,y) = ( 1 + Sum_{i>0} ((x^i)*(1 - y)/(1 + y*x^i - x^i)) )/( 1 - Sum_{i>0} ((y*x^i)/(1 + y*x^i - x^i)) ). - John Tyler Rascoe, Jul 10 2024

A088218 Total number of leaves in all rooted ordered trees with n edges.

Original entry on oeis.org

1, 1, 3, 10, 35, 126, 462, 1716, 6435, 24310, 92378, 352716, 1352078, 5200300, 20058300, 77558760, 300540195, 1166803110, 4537567650, 17672631900, 68923264410, 269128937220, 1052049481860, 4116715363800, 16123801841550, 63205303218876, 247959266474052

Offset: 0

Michael Somos, Sep 24 2003

Essentially the same as A001700, which has more information.
Note that the unique rooted tree with no edges has no leaves, so a(0)=1 is by convention. - Michael Somos, Jul 30 2011
Number of ordered partitions of n into n parts, allowing zeros (cf. A097070) is binomial(2*n-1,n) = a(n) = essentially A001700. - Vladeta Jovovic, Sep 15 2004
Hankel transform is A000027; example: Det([1,1,3,10;1,3,10,35;3,10,35,126; 10,35,126,462]) = 4. - Philippe Deléham, Apr 13 2007
a(n) is the number of functions f:[n]->[n] such that for all x,y in [n] if xA045992(n). - Geoffrey Critzer, Apr 02 2009
Hankel transform of the aeration of this sequence is A000027 doubled: 1,1,2,2,3,3,... - Paul Barry, Sep 26 2009
The Fi1 and Fi2 triangle sums of A039599 are given by the terms of this sequence. For the definitions of these triangle sums see A180662. - Johannes W. Meijer, Apr 20 2011
Alternating row sums of Riordan triangle A094527. See the Philippe Deléham formula. - Wolfdieter Lang, Nov 22 2012
(-2)*a(n) is the Z-sequence for the Riordan triangle A110162. For the notion of Z- and A-sequences for Riordan arrays see the W. Lang link under A006232 with details and references. - Wolfdieter Lang, Nov 22 2012
From Gus Wiseman, Jun 27 2021: (Start)
Also the number of integer compositions of 2n with alternating (or reverse-alternating) sum 0 (ranked by A344619). This is equivalent to Ran Pan's comment at A001700. For example, the a(0) = 1 through a(3) = 10 compositions are:
  ()  (11)  (22)    (33)
            (121)   (132)
            (1111)  (231)
                    (1122)
                    (1221)
                    (2112)
                    (2211)
                    (11121)
                    (12111)
                    (111111)
For n > 0, a(n) is also the number of integer compositions of 2n with alternating sum 2.
(End)
Number of terms in the expansion of (x_1+x_2+...+x_n)^n. - César Eliud Lozada, Jan 08 2022

			G.f. = 1 + x + 3*x^2 + 10*x^3 + 35*x^4 + 126*x^5 + 462*x^6 + 1716*x^7 + ...
The five rooted ordered trees with 3 edges have 10 leaves.
..x........................
..o..x.x..x......x.........
..o...o...o.x..x.o..x.x.x..
..r...r....r....r.....r....

L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Anwar Al Ghabra, K. Gopala Krishna, Patrick Labelle, and Vasilisa Shramchenko, Enumeration of multi-rooted plane trees, arXiv:2301.09765 [math.CO], 2023.
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
B. Dasarathy and C. Yang, A transformation on ordered trees, Comput. J. 23 (1980) 161-164. - _Nachum Dershowitz_, Sep 01 2016
Toufik Mansour and Mark Shattuck, A statistic on n-color compositions and related sequences, Proc. Indian Acad. Sci. (Math. Sci.) Vol. 124, No. 2, May 2014, pp. 127-140.
Anthony Mansuy, Preordered forests, packed words and contraction algebras, J. Algebra 411 (2014) 259-311.
Mircea Merca, A Note on Cosine Power Sums, J. Integer Sequences, Vol. 15 (2012), Article 12.5.3.
A. Vogt, Resummation of small-x double logarithms in QCD: semi-inclusive electron-positron annihilation, arXiv preprint arXiv:1108.2993 [hep-ph], 2011.

Same as A001700 modulo initial term and offset.
First differences are A024718.
Main diagonal of A071919 and of A305161.
A signed version is A110556.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
A003242 counts anti-run compositions.
A025047 counts wiggly compositions (ascend: A025048, descend: A025049).
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A106356 counts compositions by number of maximal anti-runs.
A124754 gives the alternating sum of standard compositions.
A345197 counts compositions by sum, length, and alternating sum.
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
- k = 0:  counted by A088218 (this sequence), ranked by A344619/A344619.
- k = 1:  counted by A000984, ranked by A345909/A345911.
- k = -1: counted by A001791, ranked by A345910/A345912.
- k = 2:  counted by A088218 (this sequence), ranked by A345925/A345922.
- k = -2: counted by A002054, ranked by A345924/A345923.
- k >= 0: counted by A116406, ranked by A345913/A345914.
- k <= 0: counted by A058622(n-1), ranked by A345915/A345916.
- k > 0:  counted by A027306, ranked by A345917/A345918.
- k < 0:  counted by A294175, ranked by A345919/A345920.
- k != 0: counted by A058622, ranked by A345921/A345921.
- k even: counted by A081294, ranked by A053754/A053754.
- k odd:  counted by A000302, ranked by A053738/A053738.
Cf. A000027, A000070, A000097, A000108, A001622, A006232, A008965, A039599, A045992, A058696, A094527, A097070, A110162, A110555, A180662, A238279, A239830, A325534, A325535, A333213, A344607, A344611, A344617.

[Binomial(2*n-1, n): n in [0..30]]; // Vincenzo Librandi, Aug 07 2014

seq(binomial(2*n-1, n),n=0..24); # Peter Luschny, Sep 22 2014

a[ n_] := SeriesCoefficient[(1 - x)^-n, {x, 0, n}];
c = (1 - (1 - 4 x)^(1/2))/(2 x);CoefficientList[Series[1/(1-(c-1)),{x,0,20}],x] (* Geoffrey Critzer, Dec 02 2010 *)
Table[Binomial[2 n - 1, n], {n, 0, 20}] (* Vincenzo Librandi, Aug 07 2014 *)
a[ n_] := If[ n < 0, 0, With[ {m = 2 n}, m! SeriesCoefficient[ (1 + BesselI[0, 2 x]) / 2, {x, 0, m}]]]; (* Michael Somos, Nov 22 2014 *)

{a(n) = sum( i=0, n, binomial(n+i-2,i))};

{a(n) = if( n<0, 0, polcoeff( (1 + 1 / sqrt(1 - 4*x + x * O(x^n))) / 2, n))};

{a(n) = if( n<0, 0, polcoeff( 1 / (1 - x + x * O(x^n))^n, n))};

{a(n) = if( n<0, 0, binomial( 2*n - 1, n))};

{a(n) = if( n<1, n==0, polcoeff( subst((1 - x) / (1 - 2*x), x, serreverse( x - x^2 + x * O(x^n))), n))};

def A088218(n):
    return rising_factorial(n,n)/falling_factorial(n,n)
[A088218(n) for n in (0..24)]  # Peter Luschny, Nov 21 2012

G.f.: (1 + 1 / sqrt(1 - 4*x)) / 2.
a(n) = binomial(2*n - 1, n).
a(n) = (n+1)*A000108(n)/2, n>=1. - B. Dubalski (dubalski(AT)atr.bydgoszcz.pl), Feb 05 2002 (in A060150)
a(n) = (0^n + C(2n, n))/2. - Paul Barry, May 21 2004
a(n) is the coefficient of x^n in 1 / (1 - x)^n and also the sum of the first n coefficients of 1 / (1 - x)^n. Given B(x) with the property that the coefficient of x^n in B(x)^n equals the sum of the first n coefficients of B(x)^n, then B(x) = B(0) / (1 - x).
G.f.: 1 / (2 - C(x)) = (1 - x*C(x))/sqrt(1-4*x) where C(x) is g.f. for Catalan numbers A000108. Second equation added by Wolfdieter Lang, Nov 22 2012.
From Paul Barry, Nov 02 2004: (Start)
a(n) = Sum_{k=0..n} binomial(2*n, k)*cos((n-k)*Pi);
a(n) = Sum_{k=0..n} binomial(n, (n-k)/2)*(1+(-1)^(n-k))*cos(k*Pi/2)/2 (with interpolated zeros);
a(n) = Sum_{k=0..floor(n/2)} binomial(n, k)*cos((n-2*k)*Pi/2) (with interpolated zeros); (End)
a(n) = A110556(n)*(-1)^n, central terms in triangle A110555. - Reinhard Zumkeller, Jul 27 2005
a(n) = Sum_{0<=k<=n} A094527(n,k)*(-1)^k. - Philippe Deléham, Mar 14 2007
From Paul Barry, Mar 29 2010: (Start)
G.f.: 1/(1-x/(1-2x/(1-(1/2)x/(1-(3/2)x/(1-(2/3)x/(1-(4/3)x/(1-(3/4)x/(1-(5/4)x/(1-... (continued fraction);
E.g.f.: (of aerated sequence) (1 + Bessel_I(0, 2*x))/2. (End)
a(n + 1) = A001700(n). a(n) = A024718(n) - A024718(n - 1).
E.g.f.: E(x) = 1+x/(G(0)-2*x) ; G(k) = (k+1)^2+2*x*(2*k+1)-2*x*(2*k+3)*((k+1)^2)/G(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 21 2011
a(n) = Sum_{k=0..n}(-1)^k*binomial(2*n,n+k). - Mircea Merca, Jan 28 2012
a(n) = rf(n,n)/ff(n,n), where rf is the rising factorial and ff the falling factorial. - Peter Luschny, Nov 21 2012
D-finite with recurrence: n*a(n) +2*(-2*n+1)*a(n-1) = 0. - R. J. Mathar, Dec 04 2012
a(n) = hypergeom([1-n,-n],[1],1). - Peter Luschny, Sep 22 2014
G.f.: 1 + x/W(0), where W(k) = 4*k+1 - (4*k+3)*x/(1 - (4*k+1)*x/(4*k+3 - (4*k+5)*x/(1 - (4*k+3)*x/W(k+1)  ))) ; (continued fraction). - Sergei N. Gladkovskii, Nov 13 2014
a(n) = A000984(n) + A001791(n). - Gus Wiseman, Jun 28 2021
E.g.f.: (1 + exp(2*x) * BesselI(0,2*x)) / 2. - Ilya Gutkovskiy, Nov 03 2021
From Amiram Eldar, Mar 12 2023: (Start)
Sum_{n>=0} 1/a(n) = 5/3 + 4*Pi/(9*sqrt(3)).
Sum_{n>=0} (-1)^n/a(n) = 3/5 - 8*log(phi)/(5*sqrt(5)), where phi is the golden ratio (A001622). (End)
a(n) ~ 2^(2*n-1)/sqrt(n*Pi). - Stefano Spezia, Apr 17 2024

A106356 Triangle T(n,k) 0<=k

Original entry on oeis.org

1, 1, 1, 3, 0, 1, 4, 3, 0, 1, 7, 6, 2, 0, 1, 14, 7, 8, 2, 0, 1, 23, 20, 10, 8, 2, 0, 1, 39, 42, 22, 13, 9, 2, 0, 1, 71, 72, 58, 28, 14, 10, 2, 0, 1, 124, 141, 112, 72, 33, 16, 11, 2, 0, 1, 214, 280, 219, 150, 92, 36, 18, 12, 2, 0, 1, 378, 516, 466, 311, 189, 112, 40, 20, 13, 2, 0, 1

Offset: 1

Christian G. Bower, Apr 29 2005

For n > 0, also the number of compositions of n with k + 1 maximal anti-runs (sequences without adjacent equal terms). - Gus Wiseman, Mar 23 2020

			T(4,1) = 3 because the compositions of 4 with 1 adjacent equal part are 1+1+2, 2+1+1, 2+2.
Triangle begins:
   1;
   1,  1;
   3,  0,  1;
   4,  3,  0, 1;
   7,  6,  2, 0, 1;
  14,  7,  8, 2, 0, 1;
  23, 20, 10, 8, 2, 0, 1;
  ...
From _Gus Wiseman_, Mar 23 2020 (Start)
Row n = 6 counts the following compositions (empty column shown by dot):
  (6)     (33)    (222)    (11112)  .  (111111)
  (15)    (114)   (1113)   (21111)
  (24)    (411)   (1122)
  (42)    (1131)  (2211)
  (51)    (1221)  (3111)
  (123)   (1311)  (11121)
  (132)   (2112)  (11211)
  (141)           (12111)
  (213)
  (231)
  (312)
  (321)
  (1212)
  (2121)
(End)

Alois P. Heinz, Rows n = 1..141, flattened
A. Knopfmacher and H. Prodinger, On Carlitz compositions, European Journal of Combinatorics, Vol. 19, 1998, pp. 579-589.

Row sums: 2^(n-1)=A000079(n-1). Columns 0-4: A003242, A106357-A106360.
The version counting adjacent unequal parts is A238279.
The k-th composition in standard-order has A124762(k) adjacent equal parts and A333382(k) adjacent unequal parts.
The k-th composition in standard-order has A124767(k) maximal runs and A333381(k) maximal anti-runs.
The version for ascents/descents is A238343.
The version for weak ascents/descents is A333213.
Cf. A064113, A066099, A233564, A333214, A333216.

b:= proc(n, h, t) option remember;
      if n=0 then `if`(t=0, 1, 0)
    elif t<0 then 0
    else add(b(n-j, j, `if`(j=h, t-1, t)), j=1..n)
      fi
    end:
T:= (n, k)-> b(n, -1, k):
seq(seq(T(n, k), k=0..n-1), n=1..15); # Alois P. Heinz, Oct 23 2011

b[n_, h_, t_] := b[n, h, t] = If[n == 0, If[t == 0, 1, 0], If[t<0, 0, Sum[b[n-j, j, If [j == h, t-1, t]], {j, 1, n}]]]; T[n_, k_] := b[n, -1, k]; Table[Table[T[n, k], {k, 0, n-1}], {n, 1, 15}] // Flatten (* Jean-François Alcover, Feb 20 2015, after Alois P. Heinz *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],n==0||Length[Split[#,#1!=#2&]]==k+1&]],{n,0,12},{k,0,n}] (* Gus Wiseman, Mar 23 2020 *)

A333755 Triangle read by rows where T(n,k) is the number of compositions of n with k runs, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 2, 0, 0, 2, 2, 0, 0, 3, 4, 1, 0, 0, 2, 10, 4, 0, 0, 0, 4, 12, 14, 2, 0, 0, 0, 2, 22, 29, 10, 1, 0, 0, 0, 4, 26, 56, 36, 6, 0, 0, 0, 0, 3, 34, 100, 86, 31, 2, 0, 0, 0, 0, 4, 44, 148, 200, 99, 16, 1, 0, 0, 0, 0, 2, 54, 230, 374, 278, 78, 8, 0, 0, 0, 0

Offset: 0

Gus Wiseman, Apr 10 2020

Except for a(1) = 0, the data is identical to A238130 shifted right once. However, in A238130, each row after the first ends with a zero, while here each row after the first starts with a zero.

			Triangle begins:
   1
   0   1
   0   2   0
   0   2   2   0
   0   3   4   1   0
   0   2  10   4   0   0
   0   4  12  14   2   0   0
   0   2  22  29  10   1   0   0
   0   4  26  56  36   6   0   0   0
   0   3  34 100  86  31   2   0   0   0
   0   4  44 148 200  99  16   1   0   0   0
   0   2  54 230 374 278  78   8   0   0   0   0
Row n = 6 counts the following compositions (empty column indicated by dot):
  .  (6)       (15)     (123)    (1212)
     (33)      (24)     (132)    (2121)
     (222)     (42)     (141)
     (111111)  (51)     (213)
               (114)    (231)
               (411)    (312)
               (1113)   (321)
               (1122)   (1131)
               (2211)   (1221)
               (3111)   (1311)
               (11112)  (2112)
               (21111)  (11121)
                        (11211)
                        (12111)

Removing all zeros gives A238279.
The version for anti-runs is A106356.
The k-th composition in standard-order has A124767(k) runs.
The version counting descents is A238343.
The version counting weak ascents is A333213.
Cf. A066099, A124762, A238130, A272919, A333381, A333382, A333489.

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

A238343 Triangle T(n,k) read by rows: T(n,k) is the number of compositions of n with k descents, n>=0, 0<=k<=n.

Original entry on oeis.org

1, 1, 0, 2, 0, 0, 3, 1, 0, 0, 5, 3, 0, 0, 0, 7, 9, 0, 0, 0, 0, 11, 19, 2, 0, 0, 0, 0, 15, 41, 8, 0, 0, 0, 0, 0, 22, 77, 29, 0, 0, 0, 0, 0, 0, 30, 142, 81, 3, 0, 0, 0, 0, 0, 0, 42, 247, 205, 18, 0, 0, 0, 0, 0, 0, 0, 56, 421, 469, 78, 0, 0, 0, 0, 0, 0, 0, 0, 77, 689, 1013, 264, 5, 0, 0, 0, 0, 0, 0, 0, 0, 101, 1113, 2059, 786, 37, 0, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Joerg Arndt and Alois P. Heinz, Feb 25 2014

Counting ascents gives the same triangle.

For n > 0, also the number of compositions of n with k + 1 maximal weakly increasing runs. - Gus Wiseman, Mar 23 2020

			Triangle starts:
00:    1;
01:    1,    0;
02:    2,    0,    0;
03:    3,    1,    0,    0;
04:    5,    3,    0,    0,   0;
05:    7,    9,    0,    0,   0, 0;
06:   11,   19,    2,    0,   0, 0, 0;
07:   15,   41,    8,    0,   0, 0, 0, 0;
08:   22,   77,   29,    0,   0, 0, 0, 0, 0;
09:   30,  142,   81,    3,   0, 0, 0, 0, 0, 0;
10:   42,  247,  205,   18,   0, 0, 0, 0, 0, 0, 0;
11:   56,  421,  469,   78,   0, 0, 0, 0, 0, 0, 0, 0;
12:   77,  689, 1013,  264,   5, 0, 0, 0, 0, 0, 0, 0, 0;
13:  101, 1113, 2059,  786,  37, 0, 0, 0, 0, 0, 0, 0, 0, 0;
14:  135, 1750, 4021, 2097, 189, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
15:  176, 2712, 7558, 5179, 751, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0;
...
From _Gus Wiseman_, Mar 23 2020: (Start)
Row n = 5 counts the following compositions:
  (5)          (3,2)
  (1,4)        (4,1)
  (2,3)        (1,3,1)
  (1,1,3)      (2,1,2)
  (1,2,2)      (2,2,1)
  (1,1,1,2)    (3,1,1)
  (1,1,1,1,1)  (1,1,2,1)
               (1,2,1,1)
               (2,1,1,1)
(End)

Joerg Arndt and Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-10 give: A000041, A241626, A241627, A241628, A241629, A241630, A241631, A241632, A241633, A241634, A241635.
T(3n,n) gives A000045(n+1).
T(3n+1,n) = A136376(n+1).
Row sums are A011782.
Compositions by length are A007318.
The version for co-runs or levels is A106356.
The case of partitions (instead of compositions) is A133121.
The version for runs is A238279.
The version without zeros is A238344.
The version for weak ascents is A333213.
Cf. A008284, A045883, A124765, A124766, A332875, A333215.

b:= proc(n, i) option remember; `if`(n=0, 1, expand(
       add(b(n-j, j)*`if`(j (p-> seq(coeff(p, x, i), i=0..n))(b(n, 0)):
seq(T(n), n=0..20);

b[n_, i_] := b[n, i] = If[n == 0, 1, Sum[b[n-j, j]*If[jJean-François Alcover, Jan 08 2015, translated from Maple *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],n==0||Length[Split[#,LessEqual]]==k+1&]],{n,0,9},{k,0,n}] (* Gus Wiseman, Mar 23 2020 *)

Sum_{k=0..n} k * T(n,k) = A045883(n-2) for n>=2.

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

A124766 Number of monotonically increasing runs for compositions in standard order.

Original entry on oeis.org

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

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 increasing runs in this composition. Alternatively, a(n) is one plus the number of strict descents in the same composition. For example, the weakly increasing runs of the 1234567th composition are ((3),(2),(1,2,2),(1,2,5),(1,1,1)), so a(1234567) = 5. The 4 strict descents together with the weak ascents 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 increasing runs are 2; 1,1; so a(11) = 2.
The table starts:
  0
  1
  1 1
  1 2 1 1
  1 2 1 2 1 2 1 1
  1 2 2 2 1 2 2 2 1 2 1 2 1 2 1 1
  1 2 2 2 1 3 2 2 1 2 1 2 2 3 2 2 1 2 2 2 1 2 2 2 1 2 1 2 1 2 1 1

Cf. A066099, A124761, A011782 (row lengths).
Compositions of n with k strict descents are A238343.
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 (this sequence).
- 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.
- Initial intervals are A246534.
- Constant compositions are A272919.
- Normal compositions are A333217.
- Permutations are A333218.
- Strictly decreasing compositions are A333255.
- Strictly increasing compositions are A333256.
- Runs-resistance is A333628.
Cf. A124760, A124763, A124764, A333213, A333220, A333379.

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

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

A124768 Number of strictly increasing runs for compositions in standard order.

Original entry on oeis.org

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

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 increasing runs in this composition. Alternatively, a(n) is one plus the number of weak descents in the same composition. For example, the strictly increasing runs of the 1234567th composition are ((3),(2),(1,2),(2),(1,2,5),(1),(1),(1)), so a(1234567) = 8. The 7 weak descents together with the strict ascents 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) = 3.
The table starts:
  0
  1
  1 2
  1 2 1 3
  1 2 2 3 1 2 2 4
  1 2 2 3 1 3 2 4 1 2 2 3 2 3 3 5
  1 2 2 3 2 3 2 4 1 2 3 4 2 3 3 5 1 2 2 3 1 3 2 4 2 3 3 4 3 4 4 6

Cf. A066099, A124763, A011782 (row lengths).
Compositions of n with k weak descents are A333213.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Partial sums from the right are A048793.
- 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.
- Strictly increasing runs are counted by A124768 (this sequence).
- Strictly decreasing runs are counted by A124769.
- Weakly increasing compositions are A225620.
- Reverse is A228351 (triangle).
- Strict compositions are A233564.
- Initial intervals are A246534.
- 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. A029931, A124760, A124761, A124764, A238343, A333220.

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

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

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

cp's OEIS Frontend

A238279 Triangle read by rows: T(n,k) is the number of compositions of n into nonzero parts with k parts directly followed by a different part, n>=0, 0<=k<=A004523(n-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A088218 Total number of leaves in all rooted ordered trees with n edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

PARI

Sage

Formula

A106356 Triangle T(n,k) 0<=k

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A333755 Triangle read by rows where T(n,k) is the number of compositions of n with k runs, n >= 0, 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A238343 Triangle T(n,k) read by rows: T(n,k) is the number of compositions of n with k descents, n>=0, 0<=k<=n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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