A2 Q3

[Chris Jones]

Hello again,

I am confused about the notation for an inversion.

Are we saying:

a) An inversion is a pair of indices (i,j) where i < j and A[i] > A[j]

or

b) A pair of indices is (i,j) where i < j. An inversion is a pair that
also has the property A[i] > A[j]

[cs240]

An inversion is a pair of indices (i, j) such that i and j satisfy both of
the following conditions:
1) i<j
2) A[i] > A[j]


Vivan
CS240 Tutor

Post by Chris Jones
Hello again,
I am confused about the notation for an inversion.
a) An inversion is a pair of indices (i,j) where i < j and A[i] > A[j]
or
b) A pair of indices is (i,j) where i < j. An inversion is a pair that
also has the property A[i] > A[j]

[Tim Liang]

So for the pairs, can they be repetitive such that (i, j) and (j, i),
would be considered different or are they essentially the same for the
counting purpose?
and is it correct that (i, i) would not be considered as it is not
distinct?

I am asking because for simple n=2 and n=3 cases, the probability is
1/4 not 1/2. If we are to believe 1/2 is correct, I have an error in
counting inversions.

Example:
Such as the case for n = 2:
there are two arrays of size 2:
(1, 2)
(2, 1)
and if we consider pair (i, j) different from (j, i), then we will
have 4 different pairs, and we only have 1 inversion in this case. So
the prob is only 1/4

[cs240]

(i, i) is not considered as an inversion since it violates the definition.

The problem clearly states that the probability is computed over all n!
permutations of n distinct integers. So how can you have 4 pairs for n=2?

Vivian
CS240 Tutor

Post by Tim Liang
So for the pairs, can they be repetitive such that (i, j) and (j, i),
would be considered different or are they essentially the same for the
counting purpose?
and is it correct that (i, i) would not be considered as it is not
distinct?
I am asking because for simple n=2 and n=3 cases, the probability is
1/4 not 1/2. If we are to believe 1/2 is correct, I have an error in
counting inversions.
(1, 2)
(2, 1)
and if we consider pair (i, j) different from (j, i), then we will
have 4 different pairs, and we only have 1 inversion in this case. So
the prob is only 1/4

[Doug Stinson]

There are 6 arrays on elements 1,2,3:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Now consider the ordered pair of indices (1,2).

There are three of the arrays for which (1,2) is an inversion:

2 1 3
3 1 2
3 2 1

Therefore the probability that (1,2) is an inversion is 3/6 = 1/2.

Doug Stinson

Post by cs240
(i, i) is not considered as an inversion since it violates the definition.
The problem clearly states that the probability is computed over all n!
permutations of n distinct integers. So how can you have 4 pairs for n=2?
Vivian
CS240 Tutor

Post by Tim Liang
So for the pairs, can they be repetitive such that (i, j) and (j, i),
would be considered different or are they essentially the same for the
counting purpose?
and is it correct that (i, i) would not be considered as it is not
distinct?
I am asking because for simple n=2 and n=3 cases, the probability is
1/4 not 1/2. If we are to believe 1/2 is correct, I have an error in
counting inversions.
(1, 2)
(2, 1)
and if we consider pair (i, j) different from (j, i), then we will
have 4 different pairs, and we only have 1 inversion in this case. So
the prob is only 1/4