Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Assuming we have the group: $$\{1,2,3,4,5,6\}$$ we will create strings where each number will appear once, for example: $$123465$$ the number $i$ is "in order" if it is in place $i$. In the string above 5,6 are out of order.

1) What is the probability that exactly 3 numbers are out of order?

2) What is the probability that all the numbers in such a string are out of order?

  1. was (not so easy) the answer is $$1/18$$

(6 choose 3) ways to put 3 numbers right. Only 2 ways to put the other 3 numbers wrong. that's 10/720

I'm stuck in 2, can this be done without using Inclusion–exclusion principle? It seems too complex.

share|improve this question
1  
Why do you think the answer to 1. is 1/6? –  Did Mar 31 '12 at 11:31
2  
the numbe $2$ apears twice in your example string. Is this ok or is this a typo? –  miracle173 Mar 31 '12 at 11:55
    
typotypotypotypo –  Nahum Litvin Mar 31 '12 at 15:31

2 Answers 2

up vote 1 down vote accepted
  • Total strings = 6!
  • Strings with (at least) digit i in correct place = 5! (6 such cases)
  • Strings with digits i,j in correct place = 4! (6C2 such cases)
  • Strings with digits i,j,k in correct place = 3! (6C3 such cases)
  • and so on

By inclusion-exclusion, the number of strings with no digits in the correct place will be $$6! - 5!*6 + 4!*6C2 - 3!*6C3 + 2!*6C4 - 1!*6C5 + 0!*6C6 = 265$$

So, I believe the answer is 265/720

Alternative method: partition the group into "subgroups" or "cycles".

A derangement consists of a number of cycles length >= 2, where each number maps onto the next number in a cycle.

Your example $123465$ has the cycle $(56)$ of length 2, but is not a derangement because 1, 2, 3, and 4 each form their own cycle of length 1.

We can partition the 6 digits, then, into:

  • a cycle of 6 (one way)
  • a cycle of 2 and 4 (6C2 = 15 ways)
  • a cycle of 3 and 3 (6C3/2 = 10 ways)
  • cycles of 2, 2 and 2 (15 ways)

Each cycle of size n has (n-1)! valid permutations

So, our number of derangements is $$1*5! + 6C2 * 1 * 3! + 6C3 / 2 * 2! * 2! + 15 * 1! * 1! * 1! = 265$$

share|improve this answer
1  
It may be worthwhile to point out that this is a famous problem, counting the number of Derangements. Already unpleasant without "theory" at $n=6$. Correctly counted. –  André Nicolas Mar 31 '12 at 13:57
    
the other guy gave diffrent answer and both seem legit to me :( –  Nahum Litvin Mar 31 '12 at 15:50
    
that's why I checked it two ways :) at first I wasn't sure. The answer is also on the Wikipedia page for Derangements. –  Ronald Mar 31 '12 at 15:56

Clearly, the sample space has $6!$ events

  1. For every triplet there are $2$ ways in which the numbers can be out of order. So, the probability would be $\frac{{6 \choose 3}\cdot2}{6!}=\frac{1}{18}$
  2. This one's a bit tricky.

    a) The number of ways to put $2$ numbers in $2$ places so that all are out of order is $1$.
    b) The number of ways to put $3$ numbers in $3$ places so that all are out of order is:
    (the number of ways without restrictions )$-$(the number of ways in which all are in order)$-$(the number of ways in which $1$ is in order)$=3!-1-{3\choose 1}\cdot1=2$
    c) The number of ways to put $4$ numbers in $4$ places so that all are out of order is $=$(the number of wayswithout restriction)$-$(the number of ways in which all are in order)$-$(the number of ways in which $1$ is in order)$-$(the number of ways in which $2$ are in order)$=4!-1-{4\choose 1}\cdot2-{4\choose 2}\cdot1=9$
    d) The number of ways to put $5$ numbers in $5$ places so that all are out of order is (as above): $5!-1- {5\choose 1}\cdot9-{5\choose 2}\cdot2-{5\choose 3}\cdot1=44$.

The number of ways to put $6$ numbers in $6$ places so that all are out of order is: $6!-1- {6\choose 1}\cdot44-{6\choose 2}\cdot9-{6\choose 3}\cdot2-{6\choose 4}\cdot1=265$. Hence, the probability should be $\frac{265}{6!}=\frac{53}{144}$

share|improve this answer
    
Welcome to the league. Happy to see you writing answers on the site! –  user21436 Mar 31 '12 at 15:15
    
1 is seems legit (me stupid) but what about 2? the other guy gave diffrent answer and both seem legit to me :( –  Nahum Litvin Mar 31 '12 at 15:50
    
@Nahum I miscounted. I've now edited the answer. –  Sidharth Iyer Mar 31 '12 at 15:53
    
@Kannappan Thanks! –  Sidharth Iyer Mar 31 '12 at 15:53
    
@SidharthIyer thanks! –  Nahum Litvin Mar 31 '12 at 15:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.