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

[Richard Mathar]

Grabbing http://list.seqfan.eu/pipermail/seqfan/2010-July/005317.html we have

rh> For the fourth and probably last recurrences the current actual elements (off 
rh> the end of the %STU lines) are
rh> A000014
rh> 1 7736
rh> 2 34659
rh> 3 138022
rh> 4 511412

That's  (as already said)
a(n)= +20*a(n-1) -180*a(n-2) +964*a(n-3) -3422*a(n-4) +8484*a(n-5) -15068*a(n-6) +19324*a(n-7) -17769*a(n-8) +11432*a(n-9) -4888*a(n-10) +1248*a(n-11) -144*a(n-12)

G.f.: 
-x*(-7736 +120061*x -837322*x^2 +3467912*x^3 -9484876*x^4 +17996064*x^5 -24175460*x^6 +22995433*x^7 -15176808*x^8 +6618712*x^9 -1716576*x^10 +200592*x^11) ) / ( (-1+3*x)^2*(2*x-1)^4*(x-1)^6 )
=

-1393 +6/(x-1)^5 +729/(-1+3*x)^2 -864/(2*x-1)^2 +1/(x-1)^6 +16/(2*x-1)^4 -10/(x-1)^4 +55/(x-1)^2 -4/(x-1)^3-166 /(x-1) +128/(2*x-1)^3 +2944/(2*x-1) -4374/(-1+3*x)

a(n) = -1/8*n^4-83/24*n^3-119/8*n^2+649/20*n+210+1/120*n^5
       +(-3080/3*n-3920+8/3*n^3-48*n^2)*2^n
       +(729*n+5103)*3^n

rh> A000022
rh> 1 13831
rh> 2 54048
rh> 3 197961
rh> 4 693696

Same recurrence as above,
G.f.:

-x*(-13831 +222572*x -1606581*x^2 +6869968*x^3 -19343578*x^4 +37665466*x^5 -51764756*x^6 +50222224*x^7 -33717440*x^8 +14922528*x^9 -3919680*x^10 +463104*x^11) / ( (-1+3*x)^2*(2*x-1)^4*(x-1)^6 )

=
-3216 +15/(x-1)^2 -6561/(-1+3*x) -832/(2*x-1)^2 +1/(x-1)^6 +729/(-1+3*x)^2 +10/(x-1)^3 -12/(x-1)^4 +96/(2*x-1)^3 -81/(x-1) +5/(x-1)^5 +3232/(2*x-1) +16/(2*x-1)^4

a(n) = -452/15*n+70+1/120*n^5-1/12*n^4-27/8*n^3-269/12*n^2
       +(-2840/3*n-4144-32*n^2+8/3*n^3)*2^n
       +(7290+729*n)*3^n

Generically speaking, once a linear recurrence is known, the g.f. is easily
obtained as explained in

http://en.wikipedia.org/wiki/Linear_recurrence
http://www.jjj.de/fxt/fxtpage.html fxtbook.pdf (chapter 35.1.5)
http://www.strw.leidenuniv.nl/~mathar/public/mathar20071126.pdf

The step from the partial fractions to the polynomial expression is also simple,
because each term c/(d*x-1)^e of the partial fraction with some constants c, d
and e has a binomial expansion
  c*sum_{k>=0} C(-e,k) (d*x)^k*(-1)^(e+k).
The sequence is a(n) = sum over all [x^n] c/(d*x-1)^e = c*C(-e,n)*d^n*(-1)^(e+n),
where C(.,.) are the binomial coefficients, extended to negative "numerator"
as usual, representing a polynomial of e-th order in n.

RJM