Probablity homework help.

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.

-
Why do you think the answer to 1. is 1/6? –  Did Mar 31 '12 at 11:31
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

• 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$$

-
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}$

-
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