Probability of Same Relative Order of n Elements

[dabd]

Hi,

Given two arrays (or sequences) of size n. What is the probability that they are in the same relative order?

Ex: s = [5, 10, 18, 3, 7] and t = [6, 9, 20, 1, 7] are in the same relative order.

Note: The elements of the sequence are drawn from a set with a total order defined, say the natural numbers.

Thanks.

 

[tiny-tim]

Hi dabd!

Hint: the first sequence can be anything, in any order.

So how many possiblities are there for the second sequence?

 

[dabd]

Hi dabd!

Hint: the first sequence can be anything, in any order.

So how many possiblities are there for the second sequence?

Of course there infinitely many possibilities for the second sequence.

Putting it in other way, two sequences of length n are in the same relative order if we sort them and their elements positions (in the original sequences) are the same.

s = [5, 10, 18, 3, 7] positions = [1, 2, 3, 4, 5]

and t = [6, 9, 20, 1, 7] positions = [1, 2, 3, 4, 5]


s'= [3, 5, 7, 10, 18] positions = [4, 1, 5, 2, 3]
and t' = [1, 6, 7, 9, 20] positions = [4, 1, 5, 2, 3]

Given the first sequence just sort it and note the positions (4, 1, 5, 2, 3) in the example.
For the second sequence any sorted sequence will do, and of course there are infinitely many different sorted sequences, and to get the same relative order sequence just "unshuffle" its positions.

But, I don't get how can I compute the probability!

 

[CRGreathouse]

The problem simplifies dramatically if the elements are assumed to be distinct.

 

[ToxicBug]

I think that for an array of n numbers, there are n! possible permutations... so I guess that for your example the prob would be 1/(5!).