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
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.
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
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Jan 22 2013
STATUS
approved