|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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)). 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:
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
