Imagine a movie show is sold out. The viewers don't sit in the seats indicated by the tickets, but chose their seats randomly. What is the probability that atleast one guy sits on the correct seat?
For that we need to first know what is the total number of permutations possible ( which is N! ), and what is the total number of permutations where none of the viewers take their designated seats, i.e. the number of derangements.
A derangement is a permutation of the elements of a set such that none of the elements appear in their original position. For example, the derangements for set { 1, 2, 3 } are { 3, 1, 2 } and { 2, 3, 1 }. Number of derangements is called subfactorials. Subfactorial of N is represented as !N.
We start with counting the number of derangements. Suppose there are 'n' seats, the viewer with ticket number i takes seat j. There are (n-1) ways of doing it. Now, the viewer with ticket j has two options - he can either take seat i or leave it. If he takes seat i the case reduces to solving the problem for (n-2) people with (n-2) seats, where each has a forbidden choice. If he does not take the seat, the case reduces the problem of (n-1) people with (n-1) seats. Therefore, we get a recurring equation:-
!n = ( n - 1 ) ( !( n - 1 ) + !( n - 2 ) )
Thus, the probability is !n/n!
Now, imagine some of the viewers sat in their allotted seat. Such a configuration can be referred to as partial derangement. Let the number of viewers who take their correct place be k. Therefore, the number of such permutations can be given by R( n, k ) where,
Now, imagine some of the viewers sat in their allotted seat. Such a configuration can be referred to as partial derangement. Let the number of viewers who take their correct place be k. Therefore, the number of such permutations can be given by R( n, k ) where,
R( n, n ) = 1
R ( n, n-1 ) = 0
R ( n, k ) = nCk.!(n-k)
No comments:
Post a Comment