Author |
Topic: Expecto Inversio! (Read 507 times) |
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender: 
Posts: 1001
|
 |
Expecto Inversio!
« on: Jul 1st, 2004, 8:47pm » |
 Quote  Modify
|
In a permutation a1..an of n distinct integers, an inversion is a pair(ai,aj) such tht i<j and ai>aj.
If all permutations are equally likely , what is the expected no. of inversions in a randomly chosen permutation of 1..n?
|
|
 IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
pedronunezmd
Junior Member
Gender:
Posts: 115
|
|
Re: Expecto Inversio!
« Reply #1 on: Jul 2nd, 2004, 7:28am » |
Quote Modify
|
Sounds like another way of asking "How many combinations of the n integers taken 2 at a time are there?"
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Expecto Inversio!
« Reply #2 on: Jul 2nd, 2004, 7:46am » |
Quote Modify
|
What is E(n) - E(n-1)?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Expecto Inversio!
« Reply #3 on: Jul 2nd, 2004, 12:08pm » |
Quote Modify
|
I would just compare the expected number of inversions and the expected number of non-inversions. (a non-inversion being a pair(ai,aj) such tht i<j and ai<aj). They should be equal and the sum is the number of pairs.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Expecto Inversio!
« Reply #4 on: Jul 2nd, 2004, 1:57pm » |
Quote Modify
|
::And of course the non-inversion change to inversions and vice versa if you take the mirror image of the permutation, which is itself another permutation.
So on average there must be half of each..::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Expecto Inversio!
« Reply #5 on: Jul 2nd, 2004, 2:22pm » |
Quote Modify
|
gee i knew this was too easy even for easy 
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Expecto Inversio!
« Reply #6 on: Jul 2nd, 2004, 2:39pm » |
Quote Modify
|
I wouldn't say it's too easy for easy. We're just too smart for the easy section, really 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Expecto Inversio!
« Reply #7 on: Jul 2nd, 2004, 2:57pm » |
Quote Modify
|
Expecto Inversio! sounds like a Harry Potter spell.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Expecto Inversio!
« Reply #8 on: Jul 3rd, 2004, 4:31am » |
Quote Modify
|
I like that, Grimbal and towr. Here's another approach: E(n) - E(n-1) = (n-1)/2.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Expecto Inversio!
« Reply #9 on: Jul 3rd, 2004, 9:31am » |
Quote Modify
|
Grimbal,
yes i am a harry potter fun obviously excited abt the 6th book. 
Barukh,
Nice approach! It never hit me though i think it should have been obvious!
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print