A221058 Number of inversions in all Dyck prefixes of length n.
0, 0, 0, 1, 4, 14, 42, 114, 304, 748, 1870, 4370, 10488, 23748, 55412, 122836, 280768, 613016, 1379286, 2977362, 6616360, 14156500, 31144300, 66168476, 144367584, 304960104, 660746892, 1389097684, 2991902704, 6264621608, 13424189160, 28011759720, 59758420736, 124325484592, 264191654758, 548218962386
Offset: 0
Keywords
Examples
a(4) = 4 because the Dyck prefixes of length 4 are 0101, 0100, 0011, 0010, 0001, and 0000 having a total of 1+2+0+1+0+0 = 4 inversions.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..1000
- 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: seq(subs({q = 1, s = 1, t = 1}, diff(R[n], q)), n = 0 .. 35); # second Maple program: a:= proc(n) option remember; `if`(n<5, [0$3, 1, 4][n+1], (4*(n-3)*(n-4) *a(n-1) +4*(n-4)*(2*n^2-9*n+8) *a(n-2) -8*(n-2)*(2*n-7) *a(n-3) -16*(n-2)*(n-3)^2 *a(n-4))/ ((n-2)*(n-3)*(n-4))) end: seq(a(n), n=0..40); # Alois P. Heinz, Jan 22 2013 -
Mathematica
CoefficientList[Series[x^2*(1+x-Sqrt[1-4*x^2])/((1-2*x)*Sqrt[(1-4*x^2)^3]),{x,0,20}],x] (* Vaclav Kotesovec, Jan 28 2013 *)
Formula
a(n) = Sum_{k>=0} k*A221057(n,k).
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)). Then a(n) = dR/dq, evaluated at t=s=q=1.
G.f.: x^2*(1+x-sqrt(1-4*x^2))/((1-2*x)*sqrt((1-4*x^2)^3)). - Vaclav Kotesovec, Jan 28 2013
a(n) ~ 2^(n-3)*n^(3/2)*sqrt(2/Pi) * (1-sqrt(Pi/(2*n))). - Vaclav Kotesovec, Jan 28 2013
D-finite with recurrence +(-n+2)*a(n) +n*a(n-1) +2*(5*n-14)*a(n-2) +4*(-2*n+1)*a(n-3) +8*(-4*n+15)*a(n-4) +16*(n-1)*a(n-5) +32*(n-5)*a(n-6)=0. - R. J. Mathar, Jul 24 2022
Comments