A129176 -id:A129176 - cp's OEIS frontend

A238875 Subdiagonal partitions: number of partitions (p1, p2, p3, ...) of n with pi <= i.

1, 1, 1, 2, 2, 4, 5, 7, 10, 15, 18, 26, 35, 47, 61, 80, 103, 138, 175, 224, 283, 362, 455, 577, 721, 898, 1111, 1380, 1701, 2106, 2577, 3156, 3844, 4680, 5671, 6879, 8312, 10034, 12060, 14478, 17319, 20715, 24703, 29442, 35004, 41578, 49247, 58278, 68796, 81132, 95502, 112320, 131877, 154705, 181158, 211908, 247475

Offset: 0

Joerg Arndt, Mar 24 2014

nonn

The partitions are represented as weakly increasing lists of parts.

Partitions with subdiagonal growth (A238876) with first part = 1.

			The a(11) = 26 such partitions of 11 are:
  01:  [ 1 1 1 1 1 1 1 1 1 1 1 ]
  02:  [ 1 1 1 1 1 1 1 1 1 2 ]
  03:  [ 1 1 1 1 1 1 1 1 3 ]
  04:  [ 1 1 1 1 1 1 1 2 2 ]
  05:  [ 1 1 1 1 1 1 1 4 ]
  06:  [ 1 1 1 1 1 1 2 3 ]
  07:  [ 1 1 1 1 1 1 5 ]
  08:  [ 1 1 1 1 1 2 2 2 ]
  09:  [ 1 1 1 1 1 2 4 ]
  10:  [ 1 1 1 1 1 3 3 ]
  11:  [ 1 1 1 1 1 6 ]
  12:  [ 1 1 1 1 2 2 3 ]
  13:  [ 1 1 1 1 2 5 ]
  14:  [ 1 1 1 1 3 4 ]
  15:  [ 1 1 1 2 2 2 2 ]
  16:  [ 1 1 1 2 2 4 ]
  17:  [ 1 1 1 2 3 3 ]
  18:  [ 1 1 1 3 5 ]
  19:  [ 1 1 1 4 4 ]
  20:  [ 1 1 2 2 2 3 ]
  21:  [ 1 1 2 2 5 ]
  22:  [ 1 1 2 3 4 ]
  23:  [ 1 1 3 3 3 ]
  24:  [ 1 2 2 2 2 2 ]
  25:  [ 1 2 2 2 4 ]
  26:  [ 1 2 2 3 3 ]

Andrew Howroyd, Table of n, a(n) for n = 0..1000
M. Archibald, A. Blecher, S. Elizalde, and A. Knopfmacher, Subdiagonal and superdiagonal partitions, Afr. Mat. 36, 77 (2025). See p. 9.

Cf. A008930 (subdiagonal compositions), A010054 (subdiagonal partitions into distinct parts).
Cf. A219282 (superdiagonal compositions), A238873 (superdiagonal partitions), A238394 (strictly superdiagonal partitions), A238874 (strictly superdiagonal compositions), A025147 (strictly superdiagonal partitions into distinct parts).
Cf. A238859 (compositions of n with subdiagonal growth), A238876 (partitions with subdiagonal growth), A001227 (partitions into distinct parts with subdiagonal growth).
Cf. A238860 (partitions with superdiagonal growth), A238861 (compositions with superdiagonal growth), A000009 (partitions into distinct parts have superdiagonal growth by definition).
Cf. A129176 and A227543.

\\ here b: nr parts; k: max part, b+w-1: partition sum.
seq(n)={my(M=matrix(n,1), v=vector(n+1)); M[1,1]=v[1]=v[2]=1; for(b=2, n, M=matrix(n-b+1,b,w,k, if(w>=k, sum(j=1, min(b-1,k), M[w+1-k,j]))); v+=concat(vector(b),vecsum(Vec(M))~)); v} \\ Andrew Howroyd, Jan 19 2024

N=55;
VP=vector(N+1);  VP[1] =VP[2] = 1;  \\ one-based; memoization
P(n) = VP[n+1];
for (n=2, N, VP[n+1] = sum( i=0, n-1, P(i) * P(n-1 -i) * x^((i+1)*(n-1-i)) ) );
x='x+O('x^N);
A(x) = sum(n=0, N, x^n * P(n) );
Vec(A(x)) \\ Joerg Arndt, Jan 23 2024

G.f.: Sum_{n>=0} x^n * P(n) where P(n) is the row polynomial of the n-th row of A129176. This works because A129176(j,k) is also the number of subdiagonal partitions of j+k with j parts. - John Tyler Rascoe, Jan 20 2024

A201075 Irregular triangle read by rows: number of Schroeder paths of length n and weighted area n^2-k.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 3, 4, 3, 3, 3, 1, 1, 1, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 10, 7, 6, 4, 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 13, 14, 17, 22, 25, 27, 31, 34, 34, 33, 31, 28, 21, 14, 10, 5, 1, 1, 1, 1, 2, 3, 4, 5, 7, 10, 13, 16, 21, 26, 31, 37, 45, 54

Offset: 0

N. J. A. Sloane, Nov 26 2011

0 <= k <= n^2.

			Triangle begins:
1
1 1
1 1 1 2 1
1 1 1 2 3 4 3 3 3 1
1 1 1 2 3 4 5 7 8 9 10 11 10 7 6 4 1
...

Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953.

Mirror image of A129179.

Cf. A129176, A201076, A201079, A201080, A201159.

gf = Expand /@ FixedPoint[1 + x # (1 + q Normal@# /. {x :> q^2 x}) + O[x]^7 &, 0];
Flatten[Reverse[CoefficientList[#, q]] & /@ CoefficientList[gf, x]] (* Andrey Zabolotskiy, Jan 03 2024 *)

More terms from Andrey Zabolotskiy, Jan 03 2024

A221057 Irregular triangle read by rows: T(n,k) is the number of Dyck prefixes of length n having k inversions (n >= 0, k >= 0).

Original entry on oeis.org

1, 1, 2, 2, 1, 3, 2, 1, 3, 2, 3, 2, 4, 3, 5, 4, 3, 1, 4, 3, 5, 6, 7, 6, 3, 1, 5, 4, 7, 9, 11, 11, 10, 6, 5, 2, 5, 4, 7, 9, 13, 14, 18, 17, 15, 12, 7, 4, 1, 6, 5, 9, 12, 18, 20, 27, 28, 30, 26, 23, 19, 15, 9, 4, 1, 6, 5, 9, 12, 18, 22, 30, 34, 42, 45, 46, 46, 44, 36, 28, 19, 11, 7, 2, 7, 6, 11, 15, 23, 29, 40, 47, 60, 68, 76, 78, 82, 77, 73, 63, 56, 44, 32, 20, 11, 5, 1

Offset: 0

Emeric Deutsch, Jan 22 2013

A Dyck prefix of length n is a binary word of a total of n 0's and 1's in which no initial segment contains more 1's than 0's.
Sum of entries in row n = binomial(n, floor(n/2)) = A001405(n).
Sum_{k>=0} k*T(n,k) = A221058(n).

			Row 4 is 3,2,1 because the Dyck prefixes of length 4 are 0101, 0100, 0011, 0010, 0001, and 0000 having 1, 2, 0, 1, 0, and 0 inversions, respectively.
Triangle begins:
  1;
  1;
  2;
  2,  1;
  3,  2,  1;
  3,  2,  3,  2;
  4,  3,  5,  4,  3,  1;
  4,  3,  5,  6,  7,  6,  3,  1;
  5,  4,  7,  9, 11, 11, 10,  6,  5,  2;

Alois P. Heinz, Rows n = 0..60, flattened
M. Shattuck, Parity theorems for statistics on permutations and Catalan words, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 5, Paper A07, 2005.

Cf. A221058, A129176, A001405.

for n from 0 to 30 do Q[2*n+1] := 0 end do: Q[0] := 1: for n from 0 to 30 do Q[2*n+2] := sort(expand(sum(q^(((i+1)*(1/2))*(2*n-2*i))* Q[2*i]* Q[2*n-2*i], i = 0 .. n))) end do: R[0] := 1: for n to 50 do R[n] := sort(expand(t*subs(s = q*s, R[n-1])+s*(R[n-1]-t^((n-1)*(1/2))*s^((n-1)* (1/2))*Q[n-1]))) end do: P := proc (n) options operator, arrow: sort(subs({s = 1, t = 1}, R[n])) end proc: for n from 0 to 12 do seq(coeff(P(n), q, j), j = 0 .. degree(P(n))) end do; # yields sequence in triangular form

For[n = 0, n <= 30, n++, Q[2n+1] = {0}]; Q[0] = {1};
For[n = 0, n <= 30, n++, Q[2n+2] = Sort[Expand[Sum[q^(((i+1)/2)(2n-2i))*  Q[2i] Q[2n-2i], {i, 0, n}]]]];
R[0] = {1};
For[n = 1, n <= 50, n++, R[n] = Sort[Expand[t ReplaceAll[R[n-1], s -> q s] + s(R[n-1] - t^((n-1)/2) s^((n-1)/2) Q[n-1])]]];
P[n_] := Sort[ReplaceAll[R[n], {s -> 1, t -> 1}]];
Table[CoefficientList[P[n][[1]], q], {n, 0, 12}] // Flatten (* Jean-François Alcover, Mar 27 2021, after Maple program *)

Let R_n(t,s,q) be the trivariate generating polynomial of the Dyck prefixes of length n with respect to number of 0's (t), number of 1's (s), and number of inversions (q). Then R_1 = t and R_n(t,s,q) = tR_{n-1}(t,qs,q) + s[R_{n-1}(t,s,q) - (ts)^{(n-1)/2} Q_{n-1}(q)], where Q_n(q) is the generating polynomial of the Dyck words of length n with respect to number of inversions. Notice that Q_{2n+1}=0 and Q_{2n} = Ctilde_q(n), given in the Shattuck reference (Eq. (4.6)).

A221058 Number of inversions in all Dyck prefixes of length n.

Original entry on oeis.org

0, 0, 0, 1, 4, 14, 42, 114, 304, 748, 1870, 4370, 10488, 23748, 55412, 122836, 280768, 613016, 1379286, 2977362, 6616360, 14156500, 31144300, 66168476, 144367584, 304960104, 660746892, 1389097684, 2991902704, 6264621608, 13424189160, 28011759720, 59758420736, 124325484592, 264191654758, 548218962386

Offset: 0

Emeric Deutsch, Jan 22 2013

nonn

A Dyck prefix of length n is a binary word of a total of n 0's and 1's in which no initial segment contains more 1's than 0's.

			a(4) = 4 because the Dyck prefixes of length 4 are 0101, 0100, 0011, 0010, 0001, and 0000 having a total of 1+2+0+1+0+0 = 4 inversions.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
M. Shattuck, Parity theorems for statistics on permutations and Catalan words, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 5, Paper A07, 2005.

Cf. A221057, A129176.

for n from 0 to 30 do Q[2*n+1] := 0 end do: Q[0] := 1: for n from 0 to 30 do Q[2*n+2] := sort(expand(sum(q^(((i+1)*(1/2))*(2*n-2*i))* Q[2*i]* Q[2*n-2*i], i = 0 .. n))) end do: R[0] := 1: for n to 50 do R[n] := sort(expand(t*subs(s = q*s, R[n-1])+s*(R[n-1]-t^((n-1)*(1/2))*s^((n-1)* (1/2))*Q[n-1]))) end do: seq(subs({q = 1, s = 1, t = 1}, diff(R[n], q)), n = 0 .. 35);
# second Maple program:
a:= proc(n) option remember; `if`(n<5, [0$3, 1, 4][n+1],
      (4*(n-3)*(n-4) *a(n-1) +4*(n-4)*(2*n^2-9*n+8) *a(n-2)
      -8*(n-2)*(2*n-7) *a(n-3) -16*(n-2)*(n-3)^2 *a(n-4))/
      ((n-2)*(n-3)*(n-4)))
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Jan 22 2013

CoefficientList[Series[x^2*(1+x-Sqrt[1-4*x^2])/((1-2*x)*Sqrt[(1-4*x^2)^3]),{x,0,20}],x] (* Vaclav Kotesovec, Jan 28 2013 *)

a(n) = Sum_{k>=0} k*A221057(n,k).
Let R_n(t,s,q) be the trivariate generating polynomial of the Dyck prefixes of length n with respect to number of 0's (t), number of 1's (s), and number of inversions (q). Then R_1 = t and R_n(t,s,q) = tR_{n-1}(t,qs,q) + s[R_{n-1}(t,s,q) - (ts)^{(n-1)/2} Q_{n-1}(q)], where Q_n(q) is the generating polynomial of the Dyck words of length n with respect to number of inversions. Notice  that Q_{2n+1}=0 and Q_{2n} = Ctilde_q(n) given in the Shattuck reference (Eq. (4.6)). Then a(n) = dR/dq, evaluated at t=s=q=1.
G.f.: x^2*(1+x-sqrt(1-4*x^2))/((1-2*x)*sqrt((1-4*x^2)^3)). - Vaclav Kotesovec, Jan 28 2013
a(n) ~ 2^(n-3)*n^(3/2)*sqrt(2/Pi) * (1-sqrt(Pi/(2*n))). - Vaclav Kotesovec, Jan 28 2013
D-finite with recurrence +(-n+2)*a(n) +n*a(n-1) +2*(5*n-14)*a(n-2) +4*(-2*n+1)*a(n-3) +8*(-4*n+15)*a(n-4) +16*(n-1)*a(n-5) +32*(n-5)*a(n-6)=0. - R. J. Mathar, Jul 24 2022

A136622 Partial sums of the irregular table A136624.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 3, 2, 1, 1, 3, 5, 2, 1, 1, 3, 8, 4, 2, 1, 1, 3, 9, 10, 4, 2, 1, 1, 3, 9, 17, 8, 4, 2, 1, 1, 3, 9, 23, 16, 8, 4, 2, 1, 1, 3, 9, 27, 28, 14, 8, 4, 2, 1, 1, 3, 9, 28, 43, 26, 14, 8, 4, 2, 1, 1, 3, 9, 28, 60, 41, 24, 14, 8, 4, 2

Offset: 1

Alford Arnold, Jan 29 2008

A129176 can also be viewed as partial sums, but are perpendicular to the sequences of A136622.

			A136624 begins
  1
  ...1
  ......2...1
  ..........2...3...3...1
  ..............2...2...6...7
  ..................2...2...4
  ......................2...2
  ..........................2
therefore this sequence begins
  1...1...1...1...1...1...1...1
  ....1...1...1...1...1...1...1
  ........2...3...3...3...3...3
  ............2...5...8...9...9
  ................2...4..10..17
  ....................2...4...8
  ........................2...4
  ............................2

Cf. A129176, A136621, A136624, A136625.

cp's OEIS Frontend

A238875 Subdiagonal partitions: number of partitions (p1, p2, p3, ...) of n with pi <= i.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

A201075 Irregular triangle read by rows: number of Schroeder paths of length n and weighted area n^2-k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A221057 Irregular triangle read by rows: T(n,k) is the number of Dyck prefixes of length n having k inversions (n >= 0, k >= 0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A221058 Number of inversions in all Dyck prefixes of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A136622 Partial sums of the irregular table A136624.

Views

Author

Keywords

Comments

Examples

Crossrefs