1
$\begingroup$

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.

  • 0
    typotypotypotypo2012-03-31

2 Answers 2

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

  • 0
    that's why I checked it two ways :) at first I wasn't sure. The answer is also on the Wikipedia page for Derangements.2012-03-31
2

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

  • 0
    @SidharthIyer thanks!2012-03-31