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?


*

*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.
 A: Clearly, the sample space has $6!$ events

*

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

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

A: *

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