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
Math Forum Home || Math Library || Quick Reference || Math Forum Search