# Probability question

1. Feb 23, 2009

### 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.

Last edited: Feb 23, 2009
2. Feb 23, 2009

### tiny-tim

Hi dabd!

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

So how many possiblities are there for the second sequence?

3. Feb 23, 2009

### dabd

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!

4. Feb 23, 2009

### CRGreathouse

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

5. Feb 25, 2009

### 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!).