Factorial probability

Printable View

January 26th 2013, 05:30 AM
RobertEagle

Factorial probability

Hi,

I have a number. For example !3. What is the probability of a specific number from the permutations to be in front of another number? Like 3 in front of 1?

Thank you,
RobertEagle
January 26th 2013, 05:45 AM
Plato

Re: Factorial probability

Quote:

Originally Posted by RobertEagle

I have a number. For example !3. What is the probability of a specific number from the permutations to be in front of another number? Like 3 in front of 1?

Please expand on what the question means.
For example, what if the number were 1123?
January 26th 2013, 06:17 AM
RobertEagle

Re: Factorial probability

Okay.

This are the combinations for !3.
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

What's the probability of a specific digit to be in front of another specific digit? Like 1 in front of 3 or in front of 2?
In this situation the probability is 50%.
i.e: for !4 the probability is 46,15% and so on..

Thank you,
RobertEagle
January 26th 2013, 06:53 AM
Plato

Re: Factorial probability

Quote:

Originally Posted by RobertEagle

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
What's the probability of a specific digit to be in front of another specific digit? Like 1 in front of 3 or in front of 2?
In this situation the probability is 50%.

I still must be missing your idea here.
The above seems to be asking about randomly rearranging $123$ , what is the probability that the 1 comes before the 2 or the 3.
I have indicated in BLUE the four cases in which that happens. So the answer is $\frac{2}{3}$ .

So tell us what do you really mean.
Please use a number like $2342$ .
January 26th 2013, 06:57 AM
Hartlw

Re: Factorial probability

50%. For ex, 13 occurrs 3 times & 31 occurrs 3 times, 3/6.
January 26th 2013, 07:04 AM
ILikeSerena

Re: Factorial probability

Suppose you have n digits, and you want a specific digit, say 1, to be in front of another specific digit, say 2.

Now let's leave out 1.
That leaves us with (n-1)! permutations of the other (n-1) digits.
If we put 1 in front of 2, we get n digits with (n-1)! permutations.

The total number of permutations is n!.

So the probability of a specific digit to be in front of another specific digit is ${(n-1)! \over n!} = {1 \over n}$ .

If you look again, you'll see that in the case of 3 digits, this is 33% instead of 50%.
January 26th 2013, 07:11 AM
Hartlw

Re: Factorial probability

It's a matter of interpretation. I considered 1 to be in front of 3 in 123.
January 26th 2013, 07:38 AM
RobertEagle

Re: Factorial probability

I'm sorry for my misunderstanding and for my bad calculus.
Actually, it doesn't matter what !n is.The percentage will always be 50%. From what I see, it's a constant.

I've made a program which calculates this percentage and it always shows me 50%, in any n!. The problem is that I don't know how to prove it mathematically.

The digit doesn't have to be next to the other comparing digit.
January 26th 2013, 07:42 AM
Hartlw

Re: Factorial probability

Quote:

Originally Posted by ILikeSerena

Suppose you have n digits, and you want a specific digit, say 1, to be in front of another specific digit, say 2.

Now let's leave out 1.
That leaves us with (n-1)! permutations of the other (n-1) digits.
If we put 1 in front of 2, we get n digits with (n-1)! permutations.

The total number of permutations is n!.

So the probability of a specific digit to be in front of another specific digit is ${(n-1)! \over n!} = {1 \over n}$ .

If you look again, you'll see that in the case of 3 digits, this is 33% instead of 50%.

If you do all permutations of 1234 you find any particular digit comes directly in front of another particular digit 8 out of 24 times which is 33%. 1/n = 1/4 = 25% is wrong.
January 26th 2013, 07:48 AM
RobertEagle

Re: Factorial probability

It doesn't have to be directly in front of another digit.
If it would have been directly in front of that particular digit, than yes. The formula would have been 1/n.
January 26th 2013, 08:05 AM
Plato

Re: Factorial probability

Quote:

Originally Posted by RobertEagle

I'm sorry for my misunderstanding and for my bad calculus. Actually, it doesn't matter what !n is.The percentage will always be 50%. From what I see, it's a constant.
I've made a program which calculates this percentage and it always shows me 50%, in any n!.The problem is that I don't know how to prove it mathematically.
The digit doesn't have to be next to the other comparing digit.

Ok. Thank you for the clarification. You are asking about two particular digits in a string of n different digits. Is that correct?

For example: $123456$ . Say the digits of particular interest are $3~\&~6$ . There $6!=720$ possible rearrangements of that string. Think about it: in any of those arrangements either the 3 come before the 6 or the 6 comes before the 3. So $50\%$ or one half is correct.

If digits can be repeated, then that is different matter.
January 26th 2013, 08:12 AM
Hartlw

Re: Factorial probability

Quote:

Originally Posted by RobertEagle

It doesn't have to be directly in front of another digit.
If it would have been directly in front of that particular digit, than yes. The formula would have been 1/n.

You are correct RobertEagle. My apologies!

1234, 1243, 1324, 1342, 1423, 1432
2134, 2143, 2314, 2341, 2413, 2431
3124, 3142, 3214, 3241, 3412, 3421

For the case of any number in front of another, any pair occurrs in every permutation and in half of those one occurrs in front of another, so 50%. If, it didn't it would be a missing permutation.

EDIT: Whoops! ILikeSerena came up with correct answer of 1/n for neighboring numbers.
January 26th 2013, 08:19 AM
RobertEagle

Re: Factorial probability

Yes, that's right Plato and Hartlw.
You're words speak truth.

If you think we can go further on this topic, this problem was given at the National Informatics Olympiad. If I were there (now I'm just preparing myself) the teachers would have expected to see a program which permutates and then calculates, right? What would be said if I write that it's a property and it's a constant? Would I be considered that I have failed or pass?
I don't know what to say..

Thank you,
RobertEagle
January 26th 2013, 11:42 AM
ILikeSerena

Re: Factorial probability

Quote:

Originally Posted by RobertEagle

If you think we can go further on this topic, this problem was given at the National Informatics Olympiad. If I were there (now I'm just preparing myself) the teachers would have expected to see a program which permutates and then calculates, right? What would be said if I write that it's a property and it's a constant? Would I be considered that I have failed or pass?
I don't know what to say..

When I participated in that contest (in my own country), we wrote a program that contained only a single output command.
According to the rules (and we asked for a clarification during the contest), we needed to have a program that accepted the proper input (if any), and that spit out the proper output.
Our program did and it was accepted.