Explicit Expressions for Many mixed moments of the Number of Inversions and \ Spearman's Footrule and a partial (elementary!) proof that they are Join\ tly asymptotically normal with Correlation 3/sqrt(10) By Shalosh B. Ekhad Let's define two "measures of disarray" on permutations of length n, let's \ call them inv(pi) and A(pi) inv(pi) is the familiar number of inversions, the number of pairs 1<=ipi[j] , and the less natural one, called Spearman's foot\ rule n ----- \ A(pi) = ) | -pi[i] + i | / ----- i = 1 The variance of inv is famously 2 (n + 1) (2 n + 7) ------------------ 45 and in Maple notation 1/45*(n+1)*(2*n^2+7) The variance of A, less famously (first found by Diaconis and Graham) is n (2 n + 5) (n - 1) ------------------- 72 and in Maple notation 1/72*n*(2*n+5)*(n-1) The covariance is 2 (n + 1) (n + 1) ---------------- 30 and in Maple notation 1/30*(n+1)*(n^2+1) hence the asymptotic correlation is 1/2 3 10 ------- 10 -------------------------------- The mixed , 1, 1, moment (about the means) of The number of inveresions and S\ pearman's footrule is 2 (n + 1) (n + 1) ---------------- 30 and in Maple notation 1/30*(n+1)*(n^2+1) The mixed , 1, 2, moment (about the means) of The number of inveresions and S\ pearman's footrule is 2 (n + 2) (n + 1) (2 n + 17) - --------------------------- 630 and in Maple notation -1/630*(n+2)*(n+1)*(2*n^2+17) The mixed , 1, 3, moment (about the means) of The number of inveresions and S\ pearman's footrule is 5 3 2 (n + 1) (14 n + 55 n + 55 n + 231 n + 395) --------------------------------------------- 3150 and in Maple notation 1/3150*(n+1)*(14*n^5+55*n^3+55*n^2+231*n+395) The mixed , 1, 4, moment (about the means) of The number of inveresions and S\ pearman's footrule is 5 4 3 2 (n + 2) (n + 1) (220 n - 50 n + 2796 n + 342 n + 9707 n + 31115) - -------------------------------------------------------------------- 155925 and in Maple notation -1/155925*(n+2)*(n+1)*(220*n^5-50*n^4+2796*n^3+342*n^2+9707*n+31115) -------------------------------- The mixed , 2, 1, moment (about the means) of The number of inveresions and S\ pearman's footrule is 2 (n + 2) (n + 1) (n + 5) - ------------------------ 630 and in Maple notation -1/630*(n+2)*(n+1)*(n^2+5) The mixed , 2, 2, moment (about the means) of The number of inveresions and S\ pearman's footrule is 5 4 3 2 (n + 1) (392 n + 90 n + 380 n + 1155 n + 1703 n + 6000) ----------------------------------------------------------- 113400 and in Maple notation 1/113400*(n+1)*(392*n^5+90*n^4+380*n^3+1155*n^2+1703*n+6000) The mixed , 2, 3, moment (about the means) of The number of inveresions and S\ pearman's footrule is 5 4 3 2 - (n + 2) (n + 1) (1804 n - 270 n + 15424 n + 4203 n + 33379 n + 189900)/ 1871100 and in Maple notation -1/1871100*(n+2)*(n+1)*(1804*n^5-270*n^4+15424*n^3+4203*n^2+33379*n+189900) The mixed , 2, 4, moment (about the means) of The number of inveresions and S\ pearman's footrule is 8 7 6 5 4 (n + 1) (1289288 n - 920348 n + 6729828 n + 12232052 n + 57839362 n 3 2 + 112856303 n + 299424692 n + 1446621703 n + 1681765120)/1702701000 and in Maple notation 1/1702701000*(n+1)*(1289288*n^8-920348*n^7+6729828*n^6+12232052*n^5+57839362*n^ 4+112856303*n^3+299424692*n^2+1446621703*n+1681765120) -------------------------------- The mixed , 3, 1, moment (about the means) of The number of inveresions and S\ pearman's footrule is 5 4 3 2 (n + 1) (14 n + 9 n - 33 n + 21 n + n + 84) ----------------------------------------------- 5040 and in Maple notation 1/5040*(n+1)*(14*n^5+9*n^4-33*n^3+21*n^2+n+84) The mixed , 3, 2, moment (about the means) of The number of inveresions and S\ pearman's footrule is 5 4 3 2 (n + 2) (n + 1) (484 n + 30 n + 2256 n + 1557 n + 833 n + 37860) - -------------------------------------------------------------------- 831600 and in Maple notation -1/831600*(n+2)*(n+1)*(484*n^5+30*n^4+2256*n^3+1557*n^2+833*n+37860) The mixed , 3, 3, moment (about the means) of The number of inveresions and S\ pearman's footrule is 8 7 6 5 4 (n + 1) (224224 n - 96954 n + 406084 n + 1779911 n + 4930576 n 3 2 + 11406164 n + 25523106 n + 150493949 n + 198087540)/378378000 and in Maple notation 1/378378000*(n+1)*(224224*n^8-96954*n^7+406084*n^6+1779911*n^5+4930576*n^4+ 11406164*n^3+25523106*n^2+150493949*n+198087540) The mixed , 3, 4, moment (about the means) of The number of inveresions and S\ pearman's footrule is 8 7 6 5 4 - (n + 2) (n + 1) (560560 n - 659360 n + 4995326 n - 5122 n + 27772760 n 3 2 + 120508115 n + 5964334 n + 1340518327 n + 3106600140)/1702701000 and in Maple notation -1/1702701000*(n+2)*(n+1)*(560560*n^8-659360*n^7+4995326*n^6-5122*n^5+27772760* n^4+120508115*n^3+5964334*n^2+1340518327*n+3106600140) -------------------------------- The mixed , 4, 1, moment (about the means) of The number of inveresions and S\ pearman's footrule is 5 4 3 2 (n + 2) (n + 1) (22 n + 9 n + 19 n + 81 n - 167 n + 1260) - ------------------------------------------------------------- 83160 and in Maple notation -1/83160*(n+2)*(n+1)*(22*n^5+9*n^4+19*n^3+81*n^2-167*n+1260) The mixed , 4, 2, moment (about the means) of The number of inveresions and S\ pearman's footrule is 8 7 6 5 4 (n + 1) (6446440 n - 82368 n - 11985750 n + 33565392 n + 66314535 n 3 2 + 146271258 n + 336035945 n + 2204607348 n + 3324827520)/13621608000 and in Maple notation 1/13621608000*(n+1)*(6446440*n^8-82368*n^7-11985750*n^6+33565392*n^5+66314535*n ^4+146271258*n^3+336035945*n^2+2204607348*n+3324827520) The mixed , 4, 3, moment (about the means) of The number of inveresions and S\ pearman's footrule is 8 7 6 5 - (n + 2) (n + 1) (4380376 n - 3814200 n + 21293790 n + 14423784 n 4 3 2 + 92764569 n + 766906350 n - 103586305 n + 7305979236 n + 20179983600)/ 20432412000 and in Maple notation -1/20432412000*(n+2)*(n+1)*(4380376*n^8-3814200*n^7+21293790*n^6+14423784*n^5+ 92764569*n^4+766906350*n^3-103586305*n^2+7305979236*n+20179983600) The mixed , 4, 4, moment (about the means) of The number of inveresions and S\ pearman's footrule is 11 10 9 8 (n + 1) (493629136 n - 925530320 n + 2847632940 n + 6071639640 n 7 6 5 4 + 18325935628 n + 39174467640 n + 270446041895 n + 1331971412135 n 3 2 + 2202855668961 n + 17979024108405 n + 65216298539540 n + 64518734534400 )/3473510040000 and in Maple notation 1/3473510040000*(n+1)*(493629136*n^11-925530320*n^10+2847632940*n^9+6071639640* n^8+18325935628*n^7+39174467640*n^6+270446041895*n^5+1331971412135*n^4+ 2202855668961*n^3+17979024108405*n^2+65216298539540*n+64518734534400) hence the limit of the scaled mixed moments up to the, 4, are [ 1/2 1/2 ] [3 10 36 10 ] [------- 0 -------- 0 ] [ 10 25 ] [ ] [ 552 ] [ 0 14/5 0 --- ] [ 25 ] [ ] [ 1/2 1/2 ] [9 10 108 10 ] [------- 0 --------- 0 ] [ 16 25 ] [ ] [ 2331] [ 0 69/8 0 ----] [ 25 ] and this happens to be EXACTLY the same as those of the joint normal distibu\ tion with correlation 3/sqrt(10), whose pdf is 1/2 2 2 1/2 10 exp(-1/2 x - 1/2 y + 3/10 10 x y) 1/20 -------------------------------------------- Pi that happen to be [ 1/2 1/2 ] [3 10 9 10 ] [------- 0 ------- 0 ] [ 10 10 ] [ ] [ 0 14/5 0 69/5] [ ] [ 1/2 1/2 ] [9 10 108 10 ] [------- 0 --------- 0 ] [ 10 25 ] [ ] [ 2331] [ 0 69/5 0 ----] [ 25 ] as you can see, they are indeed the same! This gives a partial (elementary!) proof of the joint asymptotic normality o\ f (inv,Spearman) with correlattion 3/sqrt(10)