Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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.
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/