avg. value of a permuted sequence

5

5ugxr

New member
Joined
Jul 9, 2024
Messages
36
A permutation of the ordered 8-tuple π‘Ž=(1,2,3,4,5,6,7,8) is another 8-tuple that contains each of the integers from 1 through 8 exactly once. For example, (2,1,3,4,5,6,7,8), (8,7,6,5,4,3,2,1), and (5,2,3,8,1,6,7,4) are all permutations of π‘Ž.

For a permutation 𝜎=(π‘Ž1,π‘Ž2,π‘Ž3,π‘Ž4,π‘Ž5,π‘Ž6,π‘Ž7,π‘Ž8), define

𝑓(𝜎)=|π‘Ž1βˆ’π‘Ž2|+|π‘Ž3βˆ’π‘Ž4|+|π‘Ž5βˆ’π‘Ž6|+|π‘Ž7βˆ’π‘Ž8|

For example, 𝑓(3,5,1,4,2,6,8,7)=|3βˆ’5|+|1βˆ’4|+|2βˆ’6|+|8βˆ’7|=2+3+4+1=10.


Determine the average value of 𝑓(𝜎) as 𝜎 ranges over all possible permutations of π‘Ž.

I'm not sure how to find the average value... Surely its not adding up all of 40320 possibilities :(
Looking for any hints to get started
(Note: Im at gr 11 math level, I haven't learned summations or limits or anything like that, I know permutations tho)
(I don't have the answer)
 
5ugxr said:
Surely its not adding up all of 40320 possibilities :(
Click to expand...
I agree. Don't see a solution, but one approach would be to look for a way to arrange the permutations so that the sum is easy to calculate. Heard of this story? https://www.nctm.org/Publications/TCM-blog/Blog/The-Story-of-Gauss/
Another approach is to reduce the number of integers to, let's say, 4 and solve it by adding up all values. Then try to figure out whether there is a formula that can be generalized to larger size problems.
 
You might first consider the average value of just [imath]|a_1-a_2|[/imath] over all the permutations. Then think about the average value of [imath]|a_3-a_4|[/imath], and so on.
 
lev888 said:
I agree. Don't see a solution, but one approach would be to look for a way to arrange the permutations so that the sum is easy to calculate. Heard of this story? https://www.nctm.org/Publications/TCM-blog/Blog/The-Story-of-Gauss/
Another approach is to reduce the number of integers to, let's say, 4 and solve it by adding up all values. Then try to figure out whether there is a formula that can be generalized to larger size problems.
Click to expand...
For the 4-tuple with numbers 1 to 4 I got
|1-2| + |3-4| = 1 + 1 = 2
|1-2| + |4-3| = 1 + 1 = 2
|1-3| + |2-4| = 2 + 2 = 4
|1-3| + |4-2| = 2 + 2 = 4
|1-4| + |2-3| = 3 + 1 = 4
|1-4| + |3-2| = 3 + 1 = 4
Total is 20

|2-3| + |4-1| = 1 + 3 = 4
|2-3| + |1-4| = 1 + 3 = 4
|2-4| + |1-3| = 2 + 2 = 4
|2-4| + |3-1| = 2 + 2 = 4
|2-1} + |4-3| = 1 + 1 = 2
|2-1| + |3-4| = 1 + 1 = 2
Total is 20

|3-4| + |1-2| = 1 + 1 = 2
|3-4| + |2-1| = 1 + 1 = 2
|3-1| + |2-4} = 2 + 2 = 4
|3-1| + |4-2| = 2 + 2 = 4
|3-2| + |1-4} = 1 + 3 = 4
|3-4| + |4-1| = 1 + 3 = 4
Total is 20

|4-1| + |2-3| = 3 + 1 = 4
|4-1| + |3-2| = 3 + 1 = 4
|4-3| + |1-2| = 1 + 1 = 2
|4-3| + |2-1| = 1 + 1 = 2
|4-2| + |1-3| = 2 + 2 = 4
|4-2| + |3-1| = 2 + 2 = 4
Total is 20

20+20+20+20 = 80
There are 24 of these 4-tupes
80/24 = 10/3
So the average for the 4-tuples is 10/3.

I'm not seeing a formula tho,
Since we're doing permutations it feels like it gets very complex since I cant just append some digits to the end to create some recursive formula like last time, since I also have to permute those added digits to create new 6-tuples. Might just be a lack of understanding of permutations , just learned it recently from videos
 
I see a pattern (formula). Whether that pattern keep going for larger n-tuples needs to be verified.
The first thing I see is that you got the same results 4 times in a row (for a 4-tuple). Any idea what will happen with an 8-tuple? That is, will the TOTALs all be the same? Is there a way to determine the total? How many times will this total appear for an 8-tuple?(Do you even have to know this number?)

Note that if you just computed the average for your 1st set of numbers you would have gotten 20/6=10/3. This is the same result when you computed the average of all possible permutations--80/24=10/3.

Hint: Compute
|1-2|+|3-4|+...|7-8|
....
|8-1|+....

I noticed with 4 tuples that 4 and 2 only came up as sums. For 8-tuples will only 8 and 4 be the sums?

Find patterns!!!! And then investigate if they are valid in the long run.
 
Last edited:
5ugxr said:
For the 4-tuple with numbers 1 to 4 I got
|1-2| + |3-4| = 1 + 1 = 2
|1-2| + |4-3| = 1 + 1 = 2
|1-3| + |2-4| = 2 + 2 = 4
|1-3| + |4-2| = 2 + 2 = 4
|1-4| + |2-3| = 3 + 1 = 4
|1-4| + |3-2| = 3 + 1 = 4
Total is 20

|2-3| + |4-1| = 1 + 3 = 4
|2-3| + |1-4| = 1 + 3 = 4
|2-4| + |1-3| = 2 + 2 = 4
|2-4| + |3-1| = 2 + 2 = 4
|2-1} + |4-3| = 1 + 1 = 2
|2-1| + |3-4| = 1 + 1 = 2
Total is 20

|3-4| + |1-2| = 1 + 1 = 2
|3-4| + |2-1| = 1 + 1 = 2
|3-1| + |2-4} = 2 + 2 = 4
|3-1| + |4-2| = 2 + 2 = 4
|3-2| + |1-4} = 1 + 3 = 4
|3-2| + |4-1| = 1 + 3 = 4
Total is 20

|4-1| + |2-3| = 3 + 1 = 4
|4-1| + |3-2| = 3 + 1 = 4
|4-3| + |1-2| = 1 + 1 = 2
|4-3| + |2-1| = 1 + 1 = 2
|4-2| + |1-3| = 2 + 2 = 4
|4-2| + |3-1| = 2 + 2 = 4
Total is 20

20+20+20+20 = 80
There are 24 of these 4-tupes
80/24 = 10/3
So the average for the 4-tuples is 10/3.

I'm not seeing a formula tho,
Since we're doing permutations it feels like it gets very complex since I cant just append some digits to the end to create some recursive formula like last time, since I also have to permute those added digits to create new 6-tuples. Might just be a lack of understanding of permutations , just learned it recently from videos
Click to expand...
If you apply my little suggestion to this smaller example, the possibilities for the first term are

|1-2| = 1​
|1-3| = 2​
|1-4| = 3​
​
|2-1| = 1​
|2-3| = 1​
|2-4| = 2​
​
|3-1| = 2​
|3-2| = 1​
|3-4| = 1​
​
|4-1| = 3​
|4-2| = 2​
|4-3| = 1​
​
total = 20​
average = 20/12 = 5/3​

Do you see how you can get the average of the sums from that?

And do you see how you can get this average for one term without listing everything? (You might start by arranging these pairs into a grid like an addition table.)

As others are saying, there are lots of patterns to see in this small example; if you can see why they occur, and how they will extend, then you can use that as a tool for the real problem.
 
Dr.Peterson said:
If you apply my little suggestion to this smaller example, the possibilities for the first term are

|1-2| = 1​
|1-3| = 2​
|1-4| = 3​
​
|2-1| = 1​
|2-3| = 1​
|2-4| = 2​
​
|3-1| = 2​
|3-2| = 1​
|3-4| = 1​
​
|4-1| = 3​
|4-2| = 2​
|4-3| = 1​
​
total = 20​
average = 20/12 = 5/3​

Do you see how you can get the average of the sums from that?

And do you see how you can get this average for one term without listing everything? (You might start by arranging these pairs into a grid like an addition table.)

As others are saying, there are lots of patterns to see in this small example; if you can see why they occur, and how they will extend, then you can use that as a tool for the real problem.
Click to expand...
I dont really understand, 5/3 is not the average I found... Or do you have to multiply by 2 since you only used half of the possibilities ( instead of 24 that I used, you only had to use 12)? Sorry I'm not quite following
 
5ugxr said:
I dont really understand, 5/3 is not the average I found... Or do you have to multiply by 2 since you only used half of the possibilities ( instead of 24 that I used, you only had to use 12)? Sorry I'm not quite following
Click to expand...
Yes, as I showed, the average of the numbers I listed is 5/3, but since the sums consist of two terms, each from the same list, you double that to get the answer -- but not because there are twice as many as in my list, but because there are two terms in each of your sums.

Try comparing the list I averaged with your own. Do you see that rather than add the sums, as you did, you can add each column first; and each column consists of exactly what I added up (twice, which doesn't change the average since you also divide by twice as much). So the average of your sums is the sum of two of my little sums:

|1-2| + |3-4| = 1 + 1 = 2 |1-2| + |4-3| = 1 + 1 = 2 |1-3| + |2-4| = 2 + 2 = 4 |1-3| + |4-2| = 2 + 2 = 4 |1-4| + |2-3| = 3 + 1 = 4 |1-4| + |3-2| = 3 + 1 = 4 |2-3| + |4-1| = 1 + 3 = 4 |2-3| + |1-4| = 1 + 3 = 4 |2-4| + |1-3| = 2 + 2 = 4 |2-4| + |3-1| = 2 + 2 = 4 |2-1} + |4-3| = 1 + 1 = 2 |2-1| + |3-4| = 1 + 1 = 2 |3-4| + |1-2| = 1 + 1 = 2 |3-4| + |2-1| = 1 + 1 = 2 |3-1| + |2-4} = 2 + 2 = 4 |3-1| + |4-2| = 2 + 2 = 4 |3-2| + |1-4} = 1 + 3 = 4 |3-2| + |4-1| = 1 + 3 = 4 |4-1| + |2-3| = 3 + 1 = 4 |4-1| + |3-2| = 3 + 1 = 4 |4-3| + |1-2| = 1 + 1 = 2 |4-3| + |2-1| = 1 + 1 = 2 |4-2| + |1-3| = 2 + 2 = 4 |4-2| + |3-1| = 2 + 2 = 4 --- --- 40 + 40 = 80

This is closely related to the Gauss trick that was mentioned.

But don't necessarily try to understand what we are doing, because that may not be what makes most sense to you. Look for any sort of pattern you can recognize, based on what you have learned from class or from experience. Until you see an idea for yourself, you aren't really learning to solve this sort of problem.
 
Dr.Peterson said:
Yes, as I showed, the average of the numbers I listed is 5/3, but since the sums consist of two terms, each from the same list, you double that to get the answer -- but not because there are twice as many as in my list, but because there are two terms in each of your sums.

Try comparing the list I averaged with your own. Do you see that rather than add the sums, as you did, you can add each column first; and each column consists of exactly what I added up (twice, which doesn't change the average since you also divide by twice as much). So the average of your sums is the sum of two of my little sums:

|1-2| + |3-4| = 1 + 1 = 2 |1-2| + |4-3| = 1 + 1 = 2 |1-3| + |2-4| = 2 + 2 = 4 |1-3| + |4-2| = 2 + 2 = 4 |1-4| + |2-3| = 3 + 1 = 4 |1-4| + |3-2| = 3 + 1 = 4 |2-3| + |4-1| = 1 + 3 = 4 |2-3| + |1-4| = 1 + 3 = 4 |2-4| + |1-3| = 2 + 2 = 4 |2-4| + |3-1| = 2 + 2 = 4 |2-1} + |4-3| = 1 + 1 = 2 |2-1| + |3-4| = 1 + 1 = 2 |3-4| + |1-2| = 1 + 1 = 2 |3-4| + |2-1| = 1 + 1 = 2 |3-1| + |2-4} = 2 + 2 = 4 |3-1| + |4-2| = 2 + 2 = 4 |3-2| + |1-4} = 1 + 3 = 4 |3-2| + |4-1| = 1 + 3 = 4 |4-1| + |2-3| = 3 + 1 = 4 |4-1| + |3-2| = 3 + 1 = 4 |4-3| + |1-2| = 1 + 1 = 2 |4-3| + |2-1| = 1 + 1 = 2 |4-2| + |1-3| = 2 + 2 = 4 |4-2| + |3-1| = 2 + 2 = 4 --- --- 40 + 40 = 80

This is closely related to the Gauss trick that was mentioned.

But don't necessarily try to understand what we are doing, because that may not be what makes most sense to you. Look for any sort of pattern you can recognize, based on what you have learned from class or from experience. Until you see an idea for yourself, you aren't really learning to solve this sort of problem.
Click to expand...
I just rewatched every video my teacher posted on this unit and I did not see any topics that are remotely connected to this question haha...
My teacher from day school has talked about the story of gauss so I can see the idea, it was just a bit confusing to me since there were absolute values in this question :<

I calculated the first term of each term with numbers 1 to 8, so 56 terms, and found an avg. of 3, so since there are four terms in the 8-tuple ( |a-b| + |c-d| + |e-f| + |g-h| ) we quadruple it to get an average of 12?
 
Yes, the average difference between any two numbers in the set is 3, so the average sum of four such differences is 12.

I believe that's the correct answer. (If it isn't, someone else will correct me.)

As for applying the Gauss idea, the important thing isn't whether there are parentheses, but the basic idea of rearranging a list of sums to make it easy to add up.

(By the way, for those who wonder if the Gauss story as they've heard it is just a little too neat, check this out:
 
You must log in or register to reply here.
Top