Home » Ask & Discuss » Mathematics. » Algebra « Back to Discussion

Algebra

Forum Expert

Joined:	28 Feb 2007
Post:	2173

20 Nov 2008 20:50:32 IST

0 People liked this

927

Permutations and moduli-not sure of difficulty level. So IIT aspirants first

None

Consider the numbers 1,2,3,...,n where n is an even integerConsider a permutation of these numbers Now for each permutation, construct the sum What is the average of these sums over all permutations?

Share this article on:

Comments (9)

rohan ghosh

Cool goIITian

Joined: 24 Oct 2007

Posts: 90

25 Nov 2008 14:10:56 IST

Like 1 people liked this

i think the answer should be =

n(n+1)/6

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

25 Nov 2008 14:15:48 IST

Like 0 people liked this

perfect! working please. preferably latexed

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

25 Nov 2008 14:20:44 IST

Like 0 people liked this

ok drop the latex requirement

Do post ur solution

rohan ghosh

Cool goIITian

Joined: 24 Oct 2007

Posts: 90

25 Nov 2008 14:28:13 IST

Like 2 people liked this

ok actually i dont know much about latex

here is the short form of my working

we can see that if we consider any pair in the sum

ak and ak+1

let us take the cases where ak = p (any integer in(123...n)

then ak+1 can have the values from 1 to n except p

so we can calulate the sum

which comes out to be p²/2-p/2+(n-p)²/2+(n-p)/2

now p will be varying over all integers from

1 to n

so summing up this expression again by varying p from 1 to n

we get the sum as = n/6(2n²+1)-n/2

now this covers all possible pairs for ak and ak+1 but for each pair

there will be n-2 factorial permutations of the rest terms

thus each pair will come in n-2 factorial permutations

hence the above sum must be multiplied by n-2 fac.

but then we have considered only ak and ak+1

there are a total of n/2 expressions

hence the above sum must be multiplied by n/2 again to get our final result

but as the average is reqd we divide the above by n fac. and simplify to get

n(n+1)/6

rohan ghosh

Cool goIITian

Joined: 24 Oct 2007

Posts: 90

25 Nov 2008 15:27:17 IST

Like 0 people liked this

is there a shorter method?

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

25 Nov 2008 15:43:30 IST

Like 2 people liked this

Yeah. the basic thing is to recognise that each term will vary from 1 to n-1 and our job is to count the number of times each one of these numbers occurs. Suppose you list all these sums and sum up the $\frac{n}{2}$ columns. You can also easily see that the sum should be the same for each column.

Hence all we need to do is to sum one column and multiply the sum obtained by $\frac{n}{2}$ .

Now consider in a column how many times will the number k appear where $1 \le k \le n-1$

You can see this happens for 2(n-k) ordered pairs

For an ordered pair, the number of permutations in which it occurs is (n-2)!

Hence the average we are looking for is $\frac{n}{2} \times \frac{2 (n-2)! [\sum_{k=1}^{n-1} k(n-k)]}{n!}$

Writing $\sum_{k=1}^{n-1} k(n-k)$ as $n\sum_{k=1}^{n-1} k - \sum_{k=1}^{n-1} k^2$ and simplifying, we get the average as

$\frac{n(n+1)}{6}$

Incidentally, this is from the problem Art and Craft of Problem Solving by Paul Zeitz gifted by someone to me recently. They had given for the case n = 10 (Good problems but no answers in that dratted book!)

Hari Shankar

Forum Expert

Joined: 28 Feb 2007

Posts: 2173

25 Nov 2008 15:45:04 IST

Like 0 people liked this

That yeah wasnt to say that I have a shorter method. But it looks to be a counting problem. There is one more guy who could post the solution sometime soon. Lets see what he comes up with

mag

Cool goIITian

Joined: 15 Nov 2008

Posts: 73

25 Nov 2008 21:51:53 IST

Like 0 people liked this

i think this one is the rite answer....

even i tried it out the answer ws the same....

even i couldn't find a surer short method...after tryng out a lot.

RyuAmakusa

Blazing goIITian

Joined: 21 Mar 2008

Posts: 776

26 Nov 2008 17:39:53 IST

Like 0 people liked this

well what i am going to tell is not a solution ...but i it comes in jee then we can use this method....in lot of cases it works....SUBSTITUTION ...there will be 4 options....now take the no.s as 1,2 then the avj is 1...which is satisfying the given ans now take 1,2,3,4 ----this has 8 cases in it 1,2 permute 3,4 permute ,the above 2 occur simultaneously and for 3,4,1,2 also 4 so all these 8 cases will have same ans.so we have only 3 cases the avg is 10/3 which the formula also gives....with this itself we will be able to eliminate the remaining 4 options.....any way....i will try to find a proper sol..

Quick Reply

Reply

	Some HTML allowed.
	Keep your comments above the belt or risk having them deleted.
	Signup for a avatar to have your pictures show up by your comment
	If Members see a thread that violates the Posting Rules, bring it to the attention of the Moderator Team