Permutations and Arithmetic Means
Date: 01/24/2003 at 11:53:11 From: Giuseppe Giordano Subject: Permutation, integer number, polynomials Writing the (n!) permutation of the first n integers in a table of dimension n! rows and n columns, I can see that: i) the arithmetic mean of the squares of each column terms (a sum having n! elements) is equal to: (n+1)(4n+2)/12. ii) the arithmetic mean of the crossproduct between any two columns is equal to: (n+1)(3n+2)/12. How can I demonstrate that? I've found these results by induction... but I can't explain! For example, if n=3 the table is (6,3) 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 Now the sum of squares is 1^2 + 1^2 + 2^2 + 2^2 + 3^2 + 3^2 = 1 + 1 + 4 + 4 + 9 + 9 = 28 The average is 28/6 = 4.66(6) The sum of crossproduct (take the first two columns) is: (1 x 2)+(1 x 3)+(2 x 1)+(2 x 3)+(3 x 1)+(3 x 2) = 2 + 3 + 2 + 6 + 3 + 6 = 22 The average is 22/6 = 3.66(6) The two formulas show that: (3+1)(12+2)/12 = 56/12 (3+1)(9+2)/12 = 44/12 Thanks for any helpful comments or suggestions you may have. Regards, Giuseppe Giordano
Date: 01/24/2003 at 19:30:08 From: Doctor Tom Subject: Re: Permutation, integer number, polynomials Ciao Giuseppe! If you think about it, in your list of permutations, every possible arrangement is there, and all the objects in the permutation are equivalent, so all will be in the same number of spots in each column. Let's look at the squares of one column. How many times will a 1 appear? Well, if there is a 1 in that column, the other n-1 numbers can be rearranged (n-1)! ways, and all will be there, so there are (n-1)! 1s in the column. But there is nothing special about 1. If you are counting the number of occurrences of any number, there are n-1 others and all of the rearrangements of those appear, and there are again (n-1)! of those. So the sum of the squares is equal to: (n-1)!(1^2 + 2^2 + 3^2 + ... + n^2) The second factor (the sum of the squares from 1 to n) is: n(n+1)(2n+1)/6, so the sum of the squares in a column is: (n-1)!n(n+1)(2n+1)/6 = n!(n+1)(2n+1)/6. Divide that by n! to obtain your result. A similar argument can be made for the dot product of two columns. For every possible pair of numbers that can appear in those columns, there are (n-2)! ways to arrange the missing numbers, and all of those will appear. So the dot product will look like this: (n-2)!(1x2 + 1x3 + ... + 1xn + 2x1 + ... + 2xn + ....... nx1 + nx2 + ...) If we just add 1x1 to the first row, 2x2 to the second, 3x3 to the third, and so on, we get the complete: 1x1 + 1x2 + ... + 1xn + 2x1 + 2x2 + ... + 2xn + .... nx1 + nx2 + ... + nxn This is just: (1+2+...+n)(1+2+... + n) Do you see why? But 1+2+...+n = n(n+1)/2, so the second term in the original equation for the dot product is: n^2(n+1)^2/4 - n(n+1)(2n+1)/6 = n(n+1)(n(n+1)/4 - (2n+1)/6) = n(n+1)(3n^2 + 3n - 4n - 2)/12 = n(n+1)(3n^2 - n - 2)/12 = n(n+1)(3n+2)(n-1)/12. Thus the dot product is: (n-2)!n(n+1)(3n+2)(n-1)/12 = n!(n+1)(3n+2)/12. Divide this by n! to obtain your result. - Doctor Tom, The Math Forum http://mathforum.org/dr.math/
Date: 01/28/2003 at 04:57:53 From: Giuseppe Giordano Subject: Thank you (permutation, integer number, polynomials) Thank you very much, Dr. Tom! Best regards, Giuseppe Giordano.
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.