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,7

Comments

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.

Links

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.

Formula

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

Example

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

Maple

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

Mathematica

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

Prog

(SageMath)
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
(PARI)
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
(PARI) \\ 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

Crossrefs

Cf. A000108, A097331, A029760, A129182, A239927.

Cf. A136624, A136625.

Mirror image of A227543.

Sequence in context: A323670 A114731 A035389 * A134132 A308121 A030424

Adjacent sequences: A129173 A129174 A129175 * A129177 A129178 A129179

Keyword

nonn,tabf,look

Author

Emeric Deutsch, Apr 11 2007

Status

approved