A221057 - OEIS

%I #22 Mar 27 2021 08:07:39

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

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

%U 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

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

%C 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.

%C Sum of entries in row n = binomial(n, floor(n/2)) = A001405(n).

%C Sum_{k>=0} k*T(n,k) = A221058(n).

%H Alois P. Heinz, <a href="/A221057/b221057.txt">Rows n = 0..60, flattened</a>

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

%e 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.

%e Triangle begins:

%e   1;

%e   1;

%e   2;

%e   2,  1;

%e   3,  2,  1;

%e   3,  2,  3,  2;

%e   4,  3,  5,  4,  3,  1;

%e   4,  3,  5,  6,  7,  6,  3,  1;

%e   5,  4,  7,  9, 11, 11, 10,  6,  5,  2;

%p 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

%t For[n = 0, n <= 30, n++, Q[2n+1] = {0}]; Q[0] = {1};

%t 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}]]]];

%t R[0] = {1};

%t 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])]]];

%t P[n_] := Sort[ReplaceAll[R[n], {s -> 1, t -> 1}]];

%t Table[CoefficientList[P[n][[1]], q], {n, 0, 12}] // Flatten (* _Jean-François Alcover_, Mar 27 2021, after Maple program *)

%Y Cf. A221058, A129176, A001405.

%K nonn,tabf

%O 0,3

%A _Emeric Deutsch_, Jan 22 2013