[seqfan] Re: Excess permutation left moves over right moves

[Richard Mathar]

Observation on the recurrences devlopped in the URL quoted in
http://list.seqfan.eu/pipermail/seqfan/2010-July/005313.html :

There is a pattern in the factored denominators of the empirical g.f.'s:
A000011:
 -x*(-31+89*x-83*x^2+26*x^3) / ( (2*x-1)*(x-1)^3 ).

A000012:
 -x*(-146+776*x-1620*x^2+1677*x^3-868*x^4+180*x^5) / ( (2*x-1)^2*(x-1)^4 ).

A000013:
 -x*(1289-13187*x+58154*x^2-144731*x^3+222774*x^4-217511*x^5+131690*x^6-45220*x^7+6744*x^8) / ( (-1+3*x)*(2*x-1)^3*(x-1)^5 ).

A000019:
 -x*(-37+112*x-110*x^2+36*x^3) / ( (2*x-1)*(x-1)^3 ).

A000020:
 -x*(-219+1218*x-2658*x^2+2866*x^3-1536*x^4+328*x^5) / ( (2*x-1)^2*(x-1)^4 ).

A000021:
 -x*(1823-19427*x+89014*x^2-229394*x^3+364170*x^4-365192*x^5+226176*x^6-79168*x^7+12000*x^8) / ( (-1+3*x)*(2*x-1)^3*(x-1)^5 ).

In all these cases a decomposition of the g.f. into partial
fractions leads to closed forms as polynomials in n multiplied by 1^n, 2^n or
3^n, because the denominators split into factors linear in x.  Example A000021:
-500 +12/(x-1)^3 -26/(x-1)^2 -729/(-1+3*x) +160/(2*x-1) -16/(2*x-1)^3 +45/(x-1) -3/(x-1)^4 -1/(x-1)^5
is --besides the constant which doesn't matter with offset 1-- the sum of
12/(x-1)^3-26/(x-1)^2+45/(x-1)-3/(x-1)^4-1/(x-1)^5
  representing -181/24*n^2-569/12*n-85-1/12*n^3+1/24*n^4
and
-729/(-1+3*x)
  representing 729*3^n
and
160/(2*x-1)-16/(2*x-1)^3
  representing (-144+8*n^2+24*n)*2^n. Total:
A000021(n) = -181/24*n^2-569/12*n-85-1/12*n^3+1/24*n^4+729*3^n+(-144+8*n^2+24*n)*2^n

Richard Mathar