------------------------- Explicit Expressions for the first 12 moments of Spearman's Footrule and a p\ artial (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) 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 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, 17.271, seconds. to produce