A221057 - OEIS

A221057

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

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

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.

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

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

LINKS

Alois P. Heinz, Rows n = 0..60, flattened

M. Shattuck, Parity theorems for statistics on permutations and Catalan words, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 5, Paper A07, 2005.

FORMULA

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

EXAMPLE

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.

Triangle begins:

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, 6, 5, 2;

MAPLE

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

MATHEMATICA

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

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

R[0] = {1};

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

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

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

CROSSREFS

Cf. A221058, A129176, A001405.

Sequence in context: A237578 A026146 A325519 * A094366 A341372 A363193

Adjacent sequences: A221054 A221055 A221056 * A221058 A221059 A221060

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Jan 22 2013

STATUS

approved