wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Expecto Inversio!
        
(Message started by: TenaliRaman on Jul 1^st, 2004, 8:47pm)

Title: Expecto Inversio!
Post by TenaliRaman on Jul 1^st, 2004, 8:47pm

In a permutation a₁..a_n of n distinct integers, an inversion is a pair(a_i,a_j) such tht i<j and a_i>a_j.

If all permutations are equally likely , what is the expected no. of inversions in a randomly chosen permutation of 1..n?

Title: Re: Expecto Inversio!
Post by pedronunezmd on Jul 2^nd, 2004, 7:28am

Sounds like another way of asking "[hide]How many combinations of the n integers taken 2 at a time are there?[/hide]"

Title: Re: Expecto Inversio!
Post by Barukh on Jul 2^nd, 2004, 7:46am

What is [hide]E(n) - E(n-1)[/hide]?

Title: Re: Expecto Inversio!
Post by Grimbal on Jul 2^nd, 2004, 12:08pm

I would just [hide]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[/hide].

Title: Re: Expecto Inversio!
Post by towr on Jul 2^nd, 2004, 1:57pm

::[hide]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..[/hide]::

Title: Re: Expecto Inversio!
Post by TenaliRaman on Jul 2^nd, 2004, 2:22pm

gee i knew this was too easy even for easy :-/

Title: Re: Expecto Inversio!
Post by towr on Jul 2^nd, 2004, 2:39pm

I wouldn't say it's too easy for easy. We're just too smart for the easy section, really :P

Title: Re: Expecto Inversio!
Post by Grimbal on Jul 2^nd, 2004, 2:57pm

Expecto Inversio! sounds like a Harry Potter spell.

Title: Re: Expecto Inversio!
Post by Barukh on Jul 3^rd, 2004, 4:31am

I like that, Grimbal and towr. Here's another approach: [hide]E(n) - E(n-1) = (n-1)/2[/hide].

Title: Re: Expecto Inversio!
Post by TenaliRaman on Jul 3^rd, 2004, 9:31am

Grimbal,
yes i am a harry potter fun obviously excited abt the 6th book. ;D

Barukh,
Nice approach! It never hit me though i think it should have been obvious!