A221058 - OEIS

%I #23 Jul 24 2022 13:05:11

%S 0,0,0,1,4,14,42,114,304,748,1870,4370,10488,23748,55412,122836,

%T 280768,613016,1379286,2977362,6616360,14156500,31144300,66168476,

%U 144367584,304960104,660746892,1389097684,2991902704,6264621608,13424189160,28011759720,59758420736,124325484592,264191654758,548218962386

%N Number of inversions in all Dyck prefixes of length n.

%C 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.

%H Alois P. Heinz, <a href="/A221058/b221058.txt">Table of n, a(n) for n = 0..1000</a>

%H M. Shattuck, <a href="https://www.emis.de/journals/INTEGERS/papers/f7/f7.Abstract.html">Parity theorems for statistics on permutations and Catalan words</a>, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 5, Paper A07, 2005.

%F a(n) = Sum_{k>=0} k*A221057(n,k).

%F 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.

%F 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

%F a(n) ~ 2^(n-3)*n^(3/2)*sqrt(2/Pi) * (1-sqrt(Pi/(2*n))). - _Vaclav Kotesovec_, Jan 28 2013

%F 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

%e 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.

%p 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);

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n<5, [0$3, 1, 4][n+1],

%p       (4*(n-3)*(n-4) *a(n-1) +4*(n-4)*(2*n^2-9*n+8) *a(n-2)

%p       -8*(n-2)*(2*n-7) *a(n-3) -16*(n-2)*(n-3)^2 *a(n-4))/

%p       ((n-2)*(n-3)*(n-4)))

%p     end:

%p seq(a(n), n=0..40);  # _Alois P. Heinz_, Jan 22 2013

%t 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 *)

%Y Cf. A221057, A129176.

%K nonn

%O 0,5

%A _Emeric Deutsch_, Jan 22 2013