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
Offset: 0
Examples
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: 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;
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.
Programs
-
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 *)
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)).
Comments