Explicit Expressions for the first, 18, moments of Spearman's Footrule and a \ partial (elementary!) proof of its Asymptotic Normality By Shalosh B. Ekhad Let's define the following "measure of disarray" on permutations of length n\ , let's call it A(pi) n ----- \ A(pi) = ) | -pi[i] + i | / ----- i = 1 The expectation of A is (n - 1) (n + 1) --------------- 3 and in Maple notation 1/3*(n-1)*(n+1) The variance of A is 2 (n + 1) (2 n + 7) ------------------ 45 and in Maple notation 1/45*(n+1)*(2*n^2+7) The, 3, -th moment about the mean of A is 2 2 (n + 2) (n + 1) (2 n + 31) - ----------------------------- 945 and in Maple notation -2/945*(n+2)*(n+1)*(2*n^2+31) The, 4, -th moment about the mean of A is 5 3 2 (n + 1) (28 n + 180 n + 160 n + 887 n + 1265) ------------------------------------------------ 4725 and in Maple notation 1/4725*(n+1)*(28*n^5+180*n^3+160*n^2+887*n+1265) The, 5, -th moment about the mean of A is 5 4 3 2 4 (n + 2) (n + 1) (44 n - 10 n + 788 n + 86 n + 3587 n + 8555) - ------------------------------------------------------------------ 93555 and in Maple notation -4/93555*(n+2)*(n+1)*(44*n^5-10*n^4+788*n^3+86*n^2+3587*n+8555) The, 6, -th moment about the mean of A is 8 7 6 5 4 (n + 1) (168168 n - 145288 n + 1800148 n + 2180892 n + 18508182 n 3 2 + 32547228 n + 112117257 n + 385870348 n + 368963105)/127702575 and in Maple notation 1/127702575*(n+1)*(168168*n^8-145288*n^7+1800148*n^6+2180892*n^5+18508182*n^4+ 32547228*n^3+112117257*n^2+385870348*n+368963105) The, 7, -th moment about the mean of A is 8 7 6 5 4 - 2 (n + 2) (n + 1) (8008 n - 11648 n + 171164 n - 88560 n + 1645002 n 3 2 + 2988888 n + 4890161 n + 46078520 n + 73541545)/18243225 and in Maple notation -2/18243225*(n+2)*(n+1)*(8008*n^8-11648*n^7+171164*n^6-88560*n^5+1645002*n^4+ 2988888*n^3+4890161*n^2+46078520*n+73541545) The, 8, -th moment about the mean of A is 11 10 9 8 (n + 1) (5717712 n - 14041456 n + 111237120 n + 63288800 n 7 6 5 4 + 1347724536 n + 1996817312 n + 17098013040 n + 53375545600 n 3 2 + 125630091477 n + 758605059019 n + 2016696623115 n + 1690532291725)/ 13956067125 and in Maple notation 1/13956067125*(n+1)*(5717712*n^11-14041456*n^10+111237120*n^9+63288800*n^8+ 1347724536*n^7+1996817312*n^6+17098013040*n^5+53375545600*n^4+125630091477*n^3+ 758605059019*n^2+2016696623115*n+1690532291725) The, 9, -th moment about the mean of A is 11 10 9 - 8 (n + 2) (n + 1) (325909584 n - 1185159352 n + 9805807128 n 8 7 6 5 - 16336808896 n + 137996736504 n + 46247875310 n + 758421298152 n 4 3 2 + 6095266855096 n + 6075969746037 n + 57909124031467 n + 310708670730195 n + 412170672282775)/5568470782875 and in Maple notation -8/5568470782875*(n+2)*(n+1)*(325909584*n^11-1185159352*n^10+9805807128*n^9-\ 16336808896*n^8+137996736504*n^7+46247875310*n^6+758421298152*n^5+6095266855096 *n^4+6075969746037*n^3+57909124031467*n^2+310708670730195*n+412170672282775) The, 10, -th moment about the mean of A is 14 13 12 (n + 1) (16730025312 n - 77618212672 n + 613234099632 n 11 10 9 - 579463689632 n + 7657390179296 n + 4566116902864 n 8 7 6 + 146567796905816 n + 264922488779784 n + 1660374425319302 n 5 4 3 + 11150634041788208 n + 25328167884268777 n + 156189484242864248 n 2 + 877883775625389940 n + 1953357983931868000 n + 1484183419415591125)/ 102088631019375 and in Maple notation 1/102088631019375*(n+1)*(16730025312*n^14-77618212672*n^13+613234099632*n^12-\ 579463689632*n^11+7657390179296*n^10+4566116902864*n^9+146567796905816*n^8+ 264922488779784*n^7+1660374425319302*n^6+11150634041788208*n^5+ 25328167884268777*n^4+156189484242864248*n^3+877883775625389940*n^2+ 1953357983931868000*n+1484183419415591125) The, 11, -th moment about the mean of A is 14 13 12 - 2 (n + 2) (n + 1) (164910249504 n - 1109464214144 n + 8370043078672 n 11 10 9 - 25751449518528 n + 147736685187168 n - 233209438306272 n 8 7 6 + 1401213332279736 n + 5054820945342736 n - 239641999825958 n 5 4 3 + 153223555779363936 n + 437783312650259667 n + 1127558386069441992 n 2 + 14546767596974857836 n + 55349216195607176680 n + 62918965273617289375) /1152673452055125 and in Maple notation -2/1152673452055125*(n+2)*(n+1)*(164910249504*n^14-1109464214144*n^13+ 8370043078672*n^12-25751449518528*n^11+147736685187168*n^10-233209438306272*n^9 +1401213332279736*n^8+5054820945342736*n^7-239641999825958*n^6+ 153223555779363936*n^5+437783312650259667*n^4+1127558386069441992*n^3+ 14546767596974857836*n^2+55349216195607176680*n+62918965273617289375) The, 12, -th moment about the mean of A is 17 16 15 (n + 1) (630286973604288 n - 4587803141201280 n + 41490610779574528 n 14 13 12 - 121537834976646400 n + 693899509395747536 n - 569631402030782000 n 11 10 + 13267658973097781616 n - 4727800684317350640 n 9 8 + 247762156313623294564 n + 967190710075660559840 n 7 6 + 2232743539438550658884 n + 37931516754466359868480 n 5 4 + 144423980180862942383187 n + 566284059362434848409065 n 3 2 + 5218420201406733448141222 n + 23349960033038734660186310 n + 44614282739339475367534175 n + 30910149914294298623964625)/ 7866996310276228125 and in Maple notation 1/7866996310276228125*(n+1)*(630286973604288*n^17-4587803141201280*n^16+ 41490610779574528*n^15-121537834976646400*n^14+693899509395747536*n^13-\ 569631402030782000*n^12+13267658973097781616*n^11-4727800684317350640*n^10+ 247762156313623294564*n^9+967190710075660559840*n^8+2232743539438550658884*n^7+ 37931516754466359868480*n^6+144423980180862942383187*n^5+ 566284059362434848409065*n^4+5218420201406733448141222*n^3+ 23349960033038734660186310*n^2+44614282739339475367534175*n+ 30910149914294298623964625) The, 13, -th moment about the mean of A is 17 16 - 4 (n + 2) (n + 1) (30013665409728 n - 320631452421280 n 15 14 13 + 2765546787907904 n - 12975721868574400 n + 65861252373298576 n 12 11 10 - 205623213769012000 n + 945177411045640128 n - 336696405594869920 n 9 8 + 337102024604167364 n + 88208812941229726190 n 7 6 - 15641836046451497468 n + 1268098670377959554690 n 5 4 + 12368049439985433951807 n + 24527455379512376607965 n 3 2 + 253127980781587818546686 n + 2144082379078624724170880 n + 6344155088392481577695275 n + 6306057216658003432593875)/ 605153562328940625 and in Maple notation -4/605153562328940625*(n+2)*(n+1)*(30013665409728*n^17-320631452421280*n^16+ 2765546787907904*n^15-12975721868574400*n^14+65861252373298576*n^13-\ 205623213769012000*n^12+945177411045640128*n^11-336696405594869920*n^10+ 337102024604167364*n^9+88208812941229726190*n^8-15641836046451497468*n^7+ 1268098670377959554690*n^6+12368049439985433951807*n^5+24527455379512376607965* n^4+253127980781587818546686*n^3+2144082379078624724170880*n^2+ 6344155088392481577695275*n+6306057216658003432593875) The, 14, -th moment about the mean of A is 20 19 18 (n + 1) (5222377781292672 n - 53467201094186880 n + 568252355975761600 n 17 16 - 2910619369445686080 n + 16240399684224410592 n 15 14 - 39556643830936578240 n + 265622171313324675600 n 13 12 - 685499406641656136160 n + 7794281123984819955192 n 11 10 - 933748100246656188600 n + 74394190104692822469900 n 9 8 + 1129907569789722516387060 n + 1261371992814884079691902 n 7 6 + 30633006976385773149989940 n + 254360895531730006950917625 n 5 4 + 857312906603211474145450680 n + 7581361379779479840463886517 n 3 2 + 59594008411886192132856738780 n + 216542892109305292050288122775 n + 363873321281031483900954769500 n + 232236148189948798919827855625)/ 112817914119895359375 and in Maple notation 1/112817914119895359375*(n+1)*(5222377781292672*n^20-53467201094186880*n^19+ 568252355975761600*n^18-2910619369445686080*n^17+16240399684224410592*n^16-\ 39556643830936578240*n^15+265622171313324675600*n^14-685499406641656136160*n^13 +7794281123984819955192*n^12-933748100246656188600*n^11+74394190104692822469900 *n^10+1129907569789722516387060*n^9+1261371992814884079691902*n^8+ 30633006976385773149989940*n^7+254360895531730006950917625*n^6+ 857312906603211474145450680*n^5+7581361379779479840463886517*n^4+ 59594008411886192132856738780*n^3+216542892109305292050288122775*n^2+ 363873321281031483900954769500*n+232236148189948798919827855625) The, 15, -th moment about the mean of A is 20 19 - 2 (n + 2) (n + 1) (12465815763945608064 n - 192679213766366046720 n 18 17 + 2052316442727432426688 n - 13477912523363713860864 n 16 15 + 75285694339635219562080 n - 315292696252870168650240 n 14 13 + 1423251234545239570368816 n - 4016151458766672742516608 n 12 11 + 10715263580950195873506216 n + 66465583070204167091269920 n 10 9 - 301656625762452829380092196 n + 3041307788119924663676812608 n 8 7 + 7587123517483961581586627622 n + 8523244654101660223249268760 n 6 5 + 745976376419625214625455244967 n + 3213970814653533365091564762864 n 4 + 13020135347555134636994492122143 n 3 + 183112499399233038412705397900280 n 2 + 1086945387261633335459029516677225 n + 2659931093482712374723833829044000 n + 2363800180002987643438613102924375)/161577816602514133696875 and in Maple notation -2/161577816602514133696875*(n+2)*(n+1)*(12465815763945608064*n^20-\ 192679213766366046720*n^19+2052316442727432426688*n^18-13477912523363713860864* n^17+75285694339635219562080*n^16-315292696252870168650240*n^15+ 1423251234545239570368816*n^14-4016151458766672742516608*n^13+ 10715263580950195873506216*n^12+66465583070204167091269920*n^11-\ 301656625762452829380092196*n^10+3041307788119924663676812608*n^9+ 7587123517483961581586627622*n^8+8523244654101660223249268760*n^7+ 745976376419625214625455244967*n^6+3213970814653533365091564762864*n^5+ 13020135347555134636994492122143*n^4+183112499399233038412705397900280*n^3+ 1086945387261633335459029516677225*n^2+2659931093482712374723833829044000*n+ 2363800180002987643438613102924375) The, 16, -th moment about the mean of A is 23 22 (n + 1) (423837735974150674176 n - 5671352562320778068736 n 21 20 + 69753445930917236423936 n - 512167138776107483725056 n 19 18 + 3464292937539684538762496 n - 14457503785273070066576896 n 17 16 + 68012402267830184451207936 n - 239703833035265438442364416 n 15 14 + 2073728258794139339012331936 n - 7676891024843401632452380896 n 13 12 + 46201354387869519975007747776 n + 140236740228477031253470637184 n 11 - 368027233894590183663602299344 n 10 + 13872437454476600462673921405024 n 9 + 38294765208587475835849132624896 n 8 + 226527976367498963381443521223104 n 7 + 4734267436385491833576886884338391 n 6 + 23813518998475304409168147114413529 n 5 + 136942590800833244788154719236284331 n 4 + 1527369118300809152967091477946982309 n 3 + 9426174034386926559344802656500349845 n 2 + 28986560620941201396296959387271570475 n + 43812040367415770828724496403813793625 n + 26060087576309929501650068898306484375)/13734114411213701364234375 and in Maple notation 1/13734114411213701364234375*(n+1)*(423837735974150674176*n^23-\ 5671352562320778068736*n^22+69753445930917236423936*n^21-\ 512167138776107483725056*n^20+3464292937539684538762496*n^19-\ 14457503785273070066576896*n^18+68012402267830184451207936*n^17-\ 239703833035265438442364416*n^16+2073728258794139339012331936*n^15-\ 7676891024843401632452380896*n^14+46201354387869519975007747776*n^13+ 140236740228477031253470637184*n^12-368027233894590183663602299344*n^11+ 13872437454476600462673921405024*n^10+38294765208587475835849132624896*n^9+ 226527976367498963381443521223104*n^8+4734267436385491833576886884338391*n^7+ 23813518998475304409168147114413529*n^6+136942590800833244788154719236284331*n^ 5+1527369118300809152967091477946982309*n^4+ 9426174034386926559344802656500349845*n^3+ 28986560620941201396296959387271570475*n^2+ 43812040367415770828724496403813793625*n+26060087576309929501650068898306484375 ) The, 17, -th moment about the mean of A is 23 22 - 16 (n + 2) (n + 1) (60548247996307239168 n - 1271731635945526723968 n 21 20 + 16941867099605729167744 n - 147860220961447778875520 n 19 18 + 1008066859607043094322048 n - 5315904263967255960326368 n 17 16 + 25628556430543217373705024 n - 104720598926467273087031520 n 15 14 + 401232421311224694411252768 n - 452380657196746803792214488 n 13 12 - 3543313431228197054365864536 n + 60329841643073877442753698480 n 11 10 - 158644940032988291500374022272 n + 748503683828848660507546286502 n 9 8 + 12750213822876018812343852429024 n - 3448561886759919748416683684820 n 7 + 459652071601707097981882718539833 n 6 + 5152370971257542326925845246955397 n 5 + 17718667945581749163999199048192869 n 4 + 192023783195821527804861732370099005 n 3 + 2007542995249343455286575875329200955 n 2 + 9238758486634459747718331467910885425 n + 19528348772903793233488968597797437375 n + 15817865958191777967693213374020451875)/7271001747113136016359375 and in Maple notation -16/7271001747113136016359375*(n+2)*(n+1)*(60548247996307239168*n^23-\ 1271731635945526723968*n^22+16941867099605729167744*n^21-\ 147860220961447778875520*n^20+1008066859607043094322048*n^19-\ 5315904263967255960326368*n^18+25628556430543217373705024*n^17-\ 104720598926467273087031520*n^16+401232421311224694411252768*n^15-\ 452380657196746803792214488*n^14-3543313431228197054365864536*n^13+ 60329841643073877442753698480*n^12-158644940032988291500374022272*n^11+ 748503683828848660507546286502*n^10+12750213822876018812343852429024*n^9-\ 3448561886759919748416683684820*n^8+459652071601707097981882718539833*n^7+ 5152370971257542326925845246955397*n^6+17718667945581749163999199048192869*n^5+ 192023783195821527804861732370099005*n^4+2007542995249343455286575875329200955* n^3+9238758486634459747718331467910885425*n^2+ 19528348772903793233488968597797437375*n+15817865958191777967693213374020451875 ) The, 18, -th moment about the mean of A is 26 25 (n + 1) (162685028900846046474367488 n - 2695923336071163055860946944 n 24 23 + 37111316888816215569090927360 n - 347326305333689652285754250240 n 22 + 2915498953535724896921766648320 n 21 - 17738642086016167486287551582720 n 20 + 93981511925082868773310820887040 n 19 - 381809473009660029923796667792640 n 18 + 2396032703335747527196824904648640 n 17 - 14636789292690738002484559432490880 n 16 + 104474676167756376463475353756604640 n 15 - 272266801379336404496796289769144640 n 14 + 369785267975666997375493470662225280 n 13 + 19523464284676526119307372409055154400 n 12 - 53748759509446248109578269970056855760 n 11 + 682921487205376647424791958883045426160 n 10 + 6541919832468075809932183686541605496050 n 9 + 10603572991080442073661007920618721129440 n 8 + 407784195628610134987274848241481371907015 n 7 + 3891621537610462318364744331392987693043360 n 6 + 18986566425018200118731183400285150603953472 n 5 + 199743491269070942109474171295913810775996704 n 4 + 1902741595612688469244768222262331161842045330 n 3 + 9580963595007706851802131588495955518413918000 n 2 + 25811610584182424189519765532911959819704235750 n + 35745755606523176883363290792449029118998740000 n + 20019782571645055961691989339253189350668909375)/ 6977216921521029755618374453125 and in Maple notation 1/6977216921521029755618374453125*(n+1)*(162685028900846046474367488*n^26-\ 2695923336071163055860946944*n^25+37111316888816215569090927360*n^24-\ 347326305333689652285754250240*n^23+2915498953535724896921766648320*n^22-\ 17738642086016167486287551582720*n^21+93981511925082868773310820887040*n^20-\ 381809473009660029923796667792640*n^19+2396032703335747527196824904648640*n^18-\ 14636789292690738002484559432490880*n^17+104474676167756376463475353756604640*n ^16-272266801379336404496796289769144640*n^15+ 369785267975666997375493470662225280*n^14+ 19523464284676526119307372409055154400*n^13-\ 53748759509446248109578269970056855760*n^12+ 682921487205376647424791958883045426160*n^11+ 6541919832468075809932183686541605496050*n^10+ 10603572991080442073661007920618721129440*n^9+ 407784195628610134987274848241481371907015*n^8+ 3891621537610462318364744331392987693043360*n^7+ 18986566425018200118731183400285150603953472*n^6+ 199743491269070942109474171295913810775996704*n^5+ 1902741595612688469244768222262331161842045330*n^4+ 9580963595007706851802131588495955518413918000*n^3+ 25811610584182424189519765532911959819704235750*n^2+ 35745755606523176883363290792449029118998740000*n+ 20019782571645055961691989339253189350668909375) Let's now look at the scaled moments The limit of the, 3, -th scaled moment about the mean of A is 0 The limit of the, 4, -th scaled moment about the mean of A is 3 The limit of the, 5, -th scaled moment about the mean of A is 0 The limit of the, 6, -th scaled moment about the mean of A is 15 The limit of the, 7, -th scaled moment about the mean of A is 0 The limit of the, 8, -th scaled moment about the mean of A is 105 The limit of the, 9, -th scaled moment about the mean of A is 0 The limit of the, 10, -th scaled moment about the mean of A is 945 The limit of the, 11, -th scaled moment about the mean of A is 0 The limit of the, 12, -th scaled moment about the mean of A is 10395 The limit of the, 13, -th scaled moment about the mean of A is 0 The limit of the, 14, -th scaled moment about the mean of A is 135135 The limit of the, 15, -th scaled moment about the mean of A is 0 The limit of the, 16, -th scaled moment about the mean of A is 2027025 The limit of the, 17, -th scaled moment about the mean of A is 0 The limit of the, 18, -th scaled moment about the mean of A is 34459425 This proves asymptotic normality up to the 10th moment by fully elementary w\ ay, confirming the fact that A is asymptotically normal proved (using fancy methods) by Persi Diaconis and Ron Graham in the following pap\ er: Spearman's Footrule as a measure of disarray, J. Royal Stat. Soc., Sectio\ n B, vol. 39, No. 2 (1977), pp. 262-268 . See Theorem 1 ------------------------------------- This ends this article that took, 3467.869, seconds. to produce