# [seqfan] Excess permutation left moves over right moves

Ron Hardin rhhardin at att.net
Sat Jul 17 23:53:08 CEST 2010

```Counting permutations of 1..n with the number of moves left compared to the
number of moves right (current state):

%S A000001 1,2,4,14,46,282,1394,12658,83122,985730,8012962,116597538,1127575970,
%T A000001
19410377378,217492266658,4320408974978,55023200887938,1238467679662722
%N A000001 Number of permutations of 1..n with equal numbers moved left and
moved right
%O A000001 1,2

%S A000002 0,0,1,4,31,146,1289,7736,85831,641302,8732989,78432212,1270475155,
%T A000002 13338831858,250740220345,3013809363056,64512904742895,873589792390382
%N A000002 Number of permutations of 1..n with the number moved left exceeding
the number moved right by 1
%O A000002 1,4

%S A000003 0,0,0,1,5,66,392,4859,34659,482272,4099634,65762489,653977909,
%T A000003 12026621478,137361430156,2862534403223,36968414699239,862935261673212
%N A000003 Number of permutations of 1..n with the number moved left exceeding
the number moved right by 2
%O A000003 1,5

%S A000004
0,0,0,0,1,6,134,960,16615,138022,2425600,23279224,444500577,4880181294,
%T A000004 102914967458,1277238809792,29767443364523,412889949481670
%N A000004 Number of permutations of 1..n with the number moved left exceeding
the number moved right by 3
%O A000004 1,6

%S A000005 0,0,0,0,0,1,7,267,2235,53830,511412,11370998,122063526,2787148807,
%T A000005 33618432005,817366315013,10992904020133,288039183533356
%N A000005 Number of permutations of 1..n with the number moved left exceeding
the number moved right by 4
%O A000005 1,7

%S A000006
1,2,5,19,83,501,3217,26489,223001,2307265,23964881,297799569,3677298385,
%T A000006 53294334289,762583317329,12621599431489,205355314491969,
%U A000006 3820420692695361
%N A000006 Number of permutations of 1..n with the number moved left exceeding
the number moved right by 0 or more
%O A000006 1,2

%S A000007
0,0,1,5,37,219,1823,13831,139879,1321535,15951919,181202031,2549722415,
%T A000007
33883956911,545091050671,8301190456511,150332113604031,2581953013032639
%N A000007 Number of permutations of 1..n with the number moved left exceeding
the number moved right by 1 or more
%O A000007 1,4

%S A000008 0,0,0,1,6,73,534,6095,54048,680233,7218930,102769819,1279247260,
%T A000008
20545125053,294350830326,5287381093455,85819208861136,1708363220642257
%N A000008 Number of permutations of 1..n with the number moved left exceeding
the number moved right by 2 or more
%O A000008 1,5

%S A000009
0,0,0,0,1,7,142,1236,19389,197961,3119296,37007330,625269351,8518503575,
%T A000009 156989400170,2424846690232,48850794161897,845427958969045
%N A000009 Number of permutations of 1..n with the number moved left exceeding
the number moved right by 3 or more
%O A000009 1,6

%S A000010 0,0,0,0,0,1,8,276,2774,59939,693696,13728106,180768774,3638322281,
%T A000010 54074432712,1147607880440,19083350797374,432538009487375
%N A000010 Number of permutations of 1..n with the number moved left exceeding
the number moved right by 4 or more
%O A000010 1,7

%S A000011
31,66,134,267,529,1048,2080,4137,8243,16446,32842,65623,131173,262260,
%T A000011 524420,1048725,2097319,4194490,8388814,16777443,33554681,67109136,
%U A000011 134218024,268435777,536871259,1073742198,2147484050,4294967727
%N A000011 Number of permutations of 1..n+4 with the number moved left exceeding
the number moved right by n
%F A000011 Empirical fit from a(1..8), then matches a(9..99):
a(n)=5*a(n-1)-9*a(n-2)+7*a(n-3)-2*a(n-4)
%H A000011 R. H. Hardin, <a href="b000011.txt">Table of n, a(n) for n=1..99</a>
%O A000011 1,1

%S A000012 146,392,960,2235,5050,11198,24520,53209,114674,245780,524352,1114231,
%T A000012
2359482,4981002,10486120,22020565,46137938,96469728,201327488,419431475,
%U A000012 872416506,1811940822,3758098120,7784630225,16106129650,33285999148
%N A000012 Number of permutations of 1..n+5 with the number moved left exceeding
the number moved right by n
%F A000012 Empirical fit from a(1..12), then matches a(13..93):
a(n)=8*a(n-1)-26*a(n-2)+44*a(n-3)-41*a(n-4)+20*a(n-5)-4*a(n-6)
%H A000012 R. H. Hardin, <a href="b000012.txt">Table of n, a(n) for n=1..93</a>
%O A000012 1,1

%S A000013
1289,4859,16615,53830,168994,520598,1585390,4794375,14437999,43373253,
%T A000013 130121945,390106124,1169206896,3504084520,10502294920,31480673141,
%U A000013 94375961733,282966406751,848513346011,2544634069346,7631805056014
%N A000013 Number of permutations of 1..n+6 with the number moved left exceeding
the number moved right by n
%F A000013 Empirical fit from a(1..18), then matches a(19..30):
a(n)=14*a(n-1)-85*a(n-2)+294*a(n-3)-639*a(n-4)+906*a(n-5)-839*a(n-6)+490*a(n-7)-164*a(n-8)+24*a(n-9)

%H A000013 R. H. Hardin, <a href="b000013.txt">Table of n, a(n) for n=1..30</a>
%O A000013 1,1

A000001 is  http://www.research.att.com/~njas/sequences/A062868

Ignoring that, the series start at successive terms 1,4,31 1,5,66 1,6,143
1,7,267  in A000002-5

Forming series from those shifting columns gives A000011-13 (at the moment),
which have linear recurrence relations.

Remarks:
1.  This seems strange, since you'd think the even and odd n would screw up the
series, when it comes to counting excess left over right moves.
2.  A000001 doesn't seem to fit the recurrences for n=0, for no reason that's
obvious, unless I've made a hand calculation error.  The definition seems to
suggest it would fit.

rhhardin at mindspring.com
rhhardin at att.net (either)

```