5
$\begingroup$

Suppose we uniformly and randomly select a permutation from the 20! Permutations of 1,2,3,...,20. What is the probability that 2 appears at an earlier position than any other even number in the selected permutation?

My approach :

2 in first position ==> 1*19! (1 is the position of 2)
2 in second position ==> 10 *1 *18!
2 in third position ==> 10*9 *1 *17!
. . .
2 in 11th position ==> 10*9*8*7*6*5*4*3*2*1*1*9!

But this was asked as a multiple choice question in GATE 2007 and the options were
(A) 1/2 (B) 1/10 (C) 9!/20! (D) None of these

I am not able to reduce this analysis to a given option.

$\endgroup$

5 Answers 5

10
$\begingroup$

The odd numbers do not matter here. The probability 2 comes before the other 9 evens is

$$\dfrac{(\text{# of ways to pick 2})(\text{# of ways to pick remaining evens})}{(\text{# of ways to order 10 evens})} = \dfrac{1\cdot 9!}{10!} = \dfrac{1}{10}$$

$\endgroup$
4
  • 2
    $\begingroup$ One of my guiding principles for combinitoric problems is "forget what you don't need to know." This is a good example. $\endgroup$ Feb 8, 2014 at 4:13
  • $\begingroup$ Wow. That answer is elegant. Thanks !! $\endgroup$
    – Unni
    Feb 8, 2014 at 5:29
  • $\begingroup$ Well, my friend I guess unni's approach is quite right. He just have to add all the cases. $\endgroup$ Feb 21, 2014 at 21:21
  • $\begingroup$ Even this answer is needlessly complicated $-$ see my answer. $\endgroup$
    – TonyK
    Jan 24, 2015 at 16:00
6
$\begingroup$

All even numbers have the same probability of being first. And there are $10$ of them. So the probability is $\dfrac{1}{10}$.

$\endgroup$
2
$\begingroup$

Let $\Omega$ be the sample space which discribes all possible permutations of the $20$ numbers. Clearly, $|\Omega|=20!$ and we let each permutation be equally likely. To find all permutations where $2$ appears before all elements of the set $E=\{k\in \mathbb{N} \mid 4\le k\le 20 \land k \text{ even} \} $. The idea now is to consider all possible positions where the elements of $E \cup \{2\} $ could appear and for each possible positioning of those elements there are $9!$ permutations of them where 2 comes before all of them. The remaining $10$ elements can be permuted in $10!$ ways, so we obtain \begin{align*} P(\text{"2 appears before all elements of }S\text{"}) =\frac{\displaystyle \binom{20}{10} \cdot 9!\cdot 10!}{|\Omega|} = \frac{\displaystyle \frac{20!}{10!\cdot 10!}\cdot 9!\cdot 10!}{20!} = \frac{9!}{10!}=\frac{1}{10} .\end{align*}

$\endgroup$
1
$\begingroup$

I took the trouble of calculating the long expression (1*19!+10*1*18!+10*9*1*17!+10*9*8*1*16!+..........+10*9*8*7*6*5*4*3*2*1*1*9!)/20! and it is = 1/10. Stay happy! Although David's approach is elegant, I just wanted to be absolutely sure about it

$\endgroup$
0
$\begingroup$

Well my approach goes like this: As question is asked about 2 comes before any other even no., only restriction is imposed on 2 not on any other no. So considering when 2 is at first place: To keep 2 at first place=1 way and rest 19 numbers can be arranged in 19! ways Since only condition is to be satisfied is that 2 comes from other even numbers So,permutation of numbers 2,4,6,8,...........is different from 2,4,8,6........ as permutation means set of different ordering. Therefore, when 2 is at first place total no. of ways rest numbers can be arranged is 19! Now, when 2 is at second place Any odd number can take place at first position, so total no. of ways are 10 now 2 is at second lace, so only way is desired to hold up then rest 9 odd numbers and even numbers other 2 will be following and these numbers can be arranged in 18! so total no. of ways=10*1*18! When 2 is at3rd position No. of ways=10*9*1*17! (No repetition is allowed since permutation means different ordering) When 2 is at 4th position No. of ways=10*9*8*1*16! Similarly all odd numbers can be placed before 2 and maximum position up-to which 2 can be placed is 11th Any odd numbers can take places from 1 to 10 Again, the fact is to be considered since permutation demands different ordering therefore ordering of different set of numbers is counted as one single permutation So, total no. of ways when 2 is at 11th position is: 10*9*8*7*6*5*4*3*2*1*1*9! so total no. of ways when 2 can be shifted holding the condition all even number comes after 2 are: 1*19!+10*1*18!+10*9*1*17!+10*9*8*1*16!+............+10*9*8*7*6*5*4*3*2*1*1*9!

Total no ways in which 20 numbers can be permuted are 20! So, required probability:(1*19!+10*1*18!+10*9*1*17!+10*9*8*1*16!+..........+10*9*8*7*6*5*4*3*2*1*1*9!)/20!

$\endgroup$
2
  • $\begingroup$ That too should give the correct answer. But isn't that a little complicated? $\endgroup$
    – Unni
    Feb 22, 2014 at 14:11
  • $\begingroup$ Yes it is, but the base form is this only,the form as suggest by David conclude from this only. $\endgroup$ Feb 22, 2014 at 18:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .