A136625 -id:A136625 - cp's OEIS frontend

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

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 3, 3, 3, 1, 1, 1, 2, 3, 5, 5, 7, 7, 6, 4, 1, 1, 1, 2, 3, 5, 7, 9, 11, 14, 16, 16, 17, 14, 10, 5, 1, 1, 1, 2, 3, 5, 7, 11, 13, 18, 22, 28, 32, 37, 40, 44, 43, 40, 35, 25, 15, 6, 1, 1, 1, 2, 3, 5, 7, 11, 15, 20, 26, 34, 42, 53, 63, 73, 85, 96, 106, 113, 118, 118, 115, 102, 86, 65, 41, 21, 7, 1

Offset: 0

Emeric Deutsch, Apr 11 2007

A Dyck word of length 2n is a word of n 0's and n 1's for which no initial segment contains more 1's than 0's.
Representing a Dyck word p of length 2n as a superdiagonal Dyck path p', the number of inversions of p is equal to the area between p' and the path that corresponds to the Dyck word 0^n 1^n.
Row n has 1+n(n-1)/2 terms. Row sums are the Catalan numbers (A000108). Alternating row sums for n>=1 are the Catalan numbers alternated with 0's (A097331). Sum(k*T(n,k),k>=0) = A029760(n-2).
This triangle is A129182 (area under Dyck paths), reflected and compressed (0's removed). Equivalently, A239927 rotated by Pi/2 clockwise and compressed.
This is also the number of Catalan paths of length n and area k. - N. J. A. Sloane, Nov 28 2011
From Alford Arnold, Jan 29 2008:
This triangle gives the partial sums of the following triangle A136624:
1
.1
....2...1
........2...3...3...1
............2...2...6...7...6...4...1
................2...2...4...8..12..15..17..14..10...5...1
etc.

			T(4,5) = 3 because we have 01010011, 01001101 and 00110101.
Triangle starts:
[0] 1;
[1] 1;
[2] 1, 1;
[3] 1, 1, 2, 1;
[4] 1, 1, 2, 3, 3, 3, 1;
[5] 1, 1, 2, 3, 5, 5, 7,  7,  6,  4,  1;
[6] 1, 1, 2, 3, 5, 7, 9, 11, 14, 16, 16, 17, 14, 10, 5, 1;
...

Alois P. Heinz, Rows n = 0..40, flattened
Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953.
J. Furlinger and J. Hofbauer, q-Catalan numbers, J. Comb. Theory, A, 40, 248-264, 1985.
M. Shattuck, Parity theorems for statistics on permutations and Catalan words, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 5, Paper A07, 2005.

Cf. A000108, A097331, A029760, A129182, A239927.
Cf. A136624, A136625.
Mirror image of A227543.

P[0]:=1: for n from 0 to 8 do
P[n+1]:=sort(expand(sum(t^((i+1)*(n-i))*P[i]*P[n-i],i=0..n))) od:
for n from 1 to 9 do seq(coeff(P[n],t,j),j=0..n*(n-1)/2) od;
# yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
      `if`(x=0, 1, expand(b(x-1, y+1, t)*z^t+b(x-1, y-1, t+1))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0$2)):
seq(T(n), n=0..10);  # Alois P. Heinz, Jun 10 2014

b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x == 0, 1, Expand[b[x-1, y+1, t]*z^t + b[x-1, y-1, t+1]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 0]]; Table[T[n], {n, 0, 10}] // Flatten (* Jean-François Alcover, May 26 2015, after Alois P. Heinz *)

P(x, n) =
{
    if ( n<=1, return(1) );
    return( sum( i=0, n-1, P(x, i) * P(x, n-1 -i) * x^((i+1)*(n-1 -i)) ) );
}
for (n=0, 10, print( Vecrev( P(x,n) ) ) ); \\ Joerg Arndt, Jan 23 2024

\\ faster with memoization:
N=11;
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)) ) );
for (n=0, N, print( Vecrev( P(n) ) ) ); \\ Joerg Arndt, Jan 23 2024

from sage.combinat.q_analogues import qt_catalan_number
for n in (0..9): print(qt_catalan_number(n).substitute(q=1).coefficients())
# Peter Luschny, Mar 10 2020

The row generating polynomials P[n] = P[n](t) satisfy P[0] = 1 and

P[n+1] = Sum_{i=0..n} P[i] P[n-i] t^((i+1)*(n-i)).

A136624 Irregular triangle read by rows: classify each numeric partition by sum of its parts and by the size of the staircase Ferrers board required to contain it. The triangle gives the number of partitions in each class, cf. A136102 and A136103.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 3, 1, 2, 2, 6, 7, 6, 4, 1, 2, 2, 4, 8, 12, 15, 17, 14, 10, 5, 1, 2, 2, 4, 6, 12, 15, 23, 30, 39, 42, 40, 35, 25, 15, 6, 1, 2, 2, 4, 6, 10, 16, 23, 29, 42, 56, 71, 88, 103, 112, 114, 102, 86, 65, 41, 21, 7, 1, 2, 2, 4, 6, 10, 14, 24, 31, 43

Offset: 0

Alford Arnold, Jan 17 2008

Sequences A136102 and A136103 encode the numeric partitions by least prime signature and the Ferrers boards by 1 2 12 360 75600 174636000 ... A006939.

			Starting a new row each time we are required to use a larger Ferrer board the triangle begins:
  1
  ..1
  .....2...1
  .........2...3...3...1
  .............2...2...6...7...6...4...1
  .................2...2...4...8..12..15..17..14..10...5...1
  .....................2...2...4...6..12..15..23..30..39..42..40..35..25..15..6..1

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

Cf. A000041 (column sums), A000108, A006939, A025487, A071724 (row sums), A136102, A136103, A136625.

d(s,n) = {my(v = setminus([1..n],s), r=[], c=1); for(i=2, #v, if(v[i]==v[i-1]+1, c++ , r=concat(r, c); c=1)) ; return(concat(r, c))}
tri(n) = {n*(n+1)/2}
S(n) = {my(R = x^tri(n)); if(n<1, return(1), for(i=1,n-1, forsubset([n,i], s, my(u=d(vecextract([1..n],s),n)); R+=(x^(tri(n)-sum(j=1,#u, tri(u[j]))))*prod(j=1,#u, sum(z=0,u[j]-1, S(z))))); return(R))}
A136624(row_n) = {Vecrev(S(row_n)/x^(row_n))} \\ John Tyler Rascoe, Feb 25 2025

a(26) onwards from John Tyler Rascoe, Feb 25 2025

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

SageMath

Formula

A136624 Irregular triangle read by rows: classify each numeric partition by sum of its parts and by the size of the staircase Ferrers board required to contain it. The triangle gives the number of partitions in each class, cf. A136102 and A136103.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A136622 Partial sums of the irregular table A136624.

Views

Author

Keywords

Comments

Examples

Crossrefs