%I #48 Jan 23 2024 08:50:32
%S 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,
%T 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,
%U 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
%N Irregular triangle read by rows: T(n,k) is the number of Dyck words of length 2n having k inversions (n >= 0, k >= 0).
%C 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.
%C 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.
%C 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).
%C This triangle is A129182 (area under Dyck paths), reflected and compressed (0's removed). Equivalently, A239927 rotated by Pi/2 clockwise and compressed.
%C This is also the number of Catalan paths of length n and area k. - _N. J. A. Sloane_, Nov 28 2011
%C From _Alford Arnold_, Jan 29 2008:
%C This triangle gives the partial sums of the following triangle A136624:
%C 1
%C .1
%C ....2...1
%C ........2...3...3...1
%C ............2...2...6...7...6...4...1
%C ................2...2...4...8..12..15..17..14..10...5...1
%C etc.
%H Alois P. Heinz, <a href="/A129176/b129176.txt">Rows n = 0..40, flattened</a>
%H Brian Drake, <a href="https://doi.org/10.1016/j.disc.2008.11.020">Limits of areas under lattice paths</a>, Discrete Math. 309 (2009), no. 12, 3936-3953.
%H J. Furlinger and J. Hofbauer, <a href="https://doi.org/10.1016/0097-3165(85)90089-5">q-Catalan numbers</a>, J. Comb. Theory, A, 40, 248-264, 1985.
%H M. Shattuck, <a href="https://www.emis.de/journals/INTEGERS/papers/f7/f7.Abstract.html">Parity theorems for statistics on permutations and Catalan words</a>, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 5, Paper A07, 2005.
%F The row generating polynomials P[n] = P[n](t) satisfy P[0] = 1 and
%F P[n+1] = Sum_{i=0..n} P[i] P[n-i] t^((i+1)*(n-i)).
%e T(4,5) = 3 because we have 01010011, 01001101 and 00110101.
%e Triangle starts:
%e [0] 1;
%e [1] 1;
%e [2] 1, 1;
%e [3] 1, 1, 2, 1;
%e [4] 1, 1, 2, 3, 3, 3, 1;
%e [5] 1, 1, 2, 3, 5, 5, 7, 7, 6, 4, 1;
%e [6] 1, 1, 2, 3, 5, 7, 9, 11, 14, 16, 16, 17, 14, 10, 5, 1;
%e ...
%p P[0]:=1: for n from 0 to 8 do
%p P[n+1]:=sort(expand(sum(t^((i+1)*(n-i))*P[i]*P[n-i],i=0..n))) od:
%p for n from 1 to 9 do seq(coeff(P[n],t,j),j=0..n*(n-1)/2) od;
%p # yields sequence in triangular form
%p # second Maple program:
%p b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
%p `if`(x=0, 1, expand(b(x-1, y+1, t)*z^t+b(x-1, y-1, t+1))))
%p end:
%p T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0$2)):
%p seq(T(n), n=0..10); # _Alois P. Heinz_, Jun 10 2014
%t 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_ *)
%o (SageMath)
%o from sage.combinat.q_analogues import qt_catalan_number
%o for n in (0..9): print(qt_catalan_number(n).substitute(q=1).coefficients())
%o # _Peter Luschny_, Mar 10 2020
%o (PARI)
%o P(x, n) =
%o {
%o if ( n<=1, return(1) );
%o return( sum( i=0, n-1, P(x, i) * P(x, n-1 -i) * x^((i+1)*(n-1 -i)) ) );
%o }
%o for (n=0, 10, print( Vecrev( P(x,n) ) ) ); \\ _Joerg Arndt_, Jan 23 2024
%o (PARI) \\ faster with memoization:
%o N=11;
%o VP=vector(N+1); VP[1] =VP[2] = 1; \\ one-based; memoization
%o P(n) = VP[n+1];
%o for (n=2, N, VP[n+1] = sum( i=0, n-1, P(i) * P(n-1 -i) * x^((i+1)*(n-1-i)) ) );
%o for (n=0, N, print( Vecrev( P(n) ) ) ); \\ _Joerg Arndt_, Jan 23 2024
%Y Cf. A000108, A097331, A029760, A129182, A239927.
%Y Cf. A136624, A136625.
%Y Mirror image of A227543.
%K nonn,tabf,look
%O 0,7
%A _Emeric Deutsch_, Apr 11 2007