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

%I A129176 #48 Jan 23 2024 08:50:32
%S A129176 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 A129176 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 A129176 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 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).
%C A129176 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 A129176 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 A129176 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 A129176 This triangle is A129182 (area under Dyck paths), reflected and compressed (0's removed). Equivalently, A239927 rotated by Pi/2 clockwise and compressed.
%C A129176 This is also the number of Catalan paths of length n and area k. - _N. J. A. Sloane_, Nov 28 2011
%C A129176 From _Alford Arnold_, Jan 29 2008:
%C A129176 This triangle gives the partial sums of the following triangle A136624:
%C A129176 1
%C A129176 .1
%C A129176 ....2...1
%C A129176 ........2...3...3...1
%C A129176 ............2...2...6...7...6...4...1
%C A129176 ................2...2...4...8..12..15..17..14..10...5...1
%C A129176 etc.
%H A129176 Alois P. Heinz, <a href="/A129176/b129176.txt">Rows n = 0..40, flattened</a>
%H A129176 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 A129176 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 A129176 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 A129176 The row generating polynomials P[n] = P[n](t) satisfy P[0] = 1 and
%F A129176 P[n+1] = Sum_{i=0..n} P[i] P[n-i] t^((i+1)*(n-i)).
%e A129176 T(4,5) = 3 because we have 01010011, 01001101 and 00110101.
%e A129176 Triangle starts:
%e A129176 [0] 1;
%e A129176 [1] 1;
%e A129176 [2] 1, 1;
%e A129176 [3] 1, 1, 2, 1;
%e A129176 [4] 1, 1, 2, 3, 3, 3, 1;
%e A129176 [5] 1, 1, 2, 3, 5, 5, 7,  7,  6,  4,  1;
%e A129176 [6] 1, 1, 2, 3, 5, 7, 9, 11, 14, 16, 16, 17, 14, 10, 5, 1;
%e A129176 ...
%p A129176 P[0]:=1: for n from 0 to 8 do
%p A129176 P[n+1]:=sort(expand(sum(t^((i+1)*(n-i))*P[i]*P[n-i],i=0..n))) od:
%p A129176 for n from 1 to 9 do seq(coeff(P[n],t,j),j=0..n*(n-1)/2) od;
%p A129176 # yields sequence in triangular form
%p A129176 # second Maple program:
%p A129176 b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
%p A129176       `if`(x=0, 1, expand(b(x-1, y+1, t)*z^t+b(x-1, y-1, t+1))))
%p A129176     end:
%p A129176 T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0$2)):
%p A129176 seq(T(n), n=0..10);  # _Alois P. Heinz_, Jun 10 2014
%t A129176 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 A129176 (SageMath)
%o A129176 from sage.combinat.q_analogues import qt_catalan_number
%o A129176 for n in (0..9): print(qt_catalan_number(n).substitute(q=1).coefficients())
%o A129176 # _Peter Luschny_, Mar 10 2020
%o A129176 (PARI)
%o A129176 P(x, n) =
%o A129176 {
%o A129176     if ( n<=1, return(1) );
%o A129176     return( sum( i=0, n-1, P(x, i) * P(x, n-1 -i) * x^((i+1)*(n-1 -i)) ) );
%o A129176 }
%o A129176 for (n=0, 10, print( Vecrev( P(x,n) ) ) ); \\ _Joerg Arndt_, Jan 23 2024
%o A129176 (PARI) \\ faster with memoization:
%o A129176 N=11;
%o A129176 VP=vector(N+1);  VP[1] =VP[2] = 1;  \\ one-based; memoization
%o A129176 P(n) = VP[n+1];
%o A129176 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 A129176 for (n=0, N, print( Vecrev( P(n) ) ) ); \\ _Joerg Arndt_, Jan 23 2024
%Y A129176 Cf. A000108, A097331, A029760, A129182, A239927.
%Y A129176 Cf. A136624, A136625.
%Y A129176 Mirror image of A227543.
%K A129176 nonn,tabf,look
%O A129176 0,7
%A A129176 _Emeric Deutsch_, Apr 11 2007