login
A221058
Number of inversions in all Dyck prefixes of length n.
2
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,5
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.
LINKS
M. Shattuck, Parity theorems for statistics on permutations and Catalan words, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 5, Paper A07, 2005.
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
EXAMPLE
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.
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 *)
CROSSREFS
Sequence in context: A309296 A124616 A335514 * A347583 A124617 A124618
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jan 22 2013
STATUS
approved