GATE CSE 2024 | Set 1 | Question: 4

Question

Consider a permutation sampled uniformly at random from the set of all permutations of $\{1,2,3, \cdots, n\}$ for some $n \geq 4$. Let $X$ be the event that $1$ occurs before $2$ in the permutation, and $Y$ the event that $3$ occurs before $4$. Which one of the following statements is TRUE?

• A. The events $X$ and $Y$ are mutually exclusive
• B. The events $X$ and $Y$ are independent
• C. Either event $X$ or $Y$ must occur
• D. Event $X$ is more likely than event $Y$

Comments

OPTION B -: 

P(X) = (n!/2!)/n!   //#permutations = (n!/2!) Because of 2 to 1 correspondence 

==> P(X) = 1/2

Also P(Y) = 1/2

P(X∩Y) = [n!/(2!×2!)]/n!     

i.e. P(X∩Y) = 1/4

==> Events X and Y are independent.

---

Guys look like probability and combinatorics will gonna be a big headache in gate exam

---

But by option elimination, this question becomes easy

---

option elimination doesnt help hou understand the beautiful concept behind this .

Answer 1

Just by reading the question, it is evident that -

A. Events X and Y are not mutually exclusive, both events can occur simultaneously.

C. It is also possible that both even can not occur.

D. Both events are symmetric, their probabilities are exactly same.

B. Occurring of either event doesn't affect occurring of another event. Thus, independent.

P(X) = P(Y) = 0.5, P(X,Y) = 0.25 = P(x) * P(Y). This shows that indeed events X and Y are independent.

Total number of permutations = n!

Number of permutations where 1 comes before 2 = ${n \choose 2} * (n-2)!$

Number of permutations where 3 comes before 4 = ${n \choose 2} * (n-2)!$

Number of permutations where 1 comes before 2 and 3 comes before 4 = ${n \choose 2} * {n-2 \choose 2} * (n-4)!$

Answer - B.

Comments

It took me a lot of time to understand but thank you so much Mr Shishir Roy

---

Good solution and Easy to understand !!

---

I think we can also calculate arrangement of  X ∩ Y $$\text{Arrangements for } X \cap Y = \binom{n}{4} \times \binom{4}{2} \times \binom{2}{2} \times (n-4)!$$

4C2 is for 1 before 2 and 2C2 is for 3 before 4

Answer 2

We have to consider random permutation from set {1, 2, 3, - - - - n} for some n $\geq$ 4.

Fast approach to solve this by putting n = 4. 

So, our set will be {1, 2, 3, 4}.

 

Let, X : 1 Occur before 2.

Y : 3 occur before 4.

 

---

 

All Possible Permutations will be :

(1234), (1243), (1324), (1342), (1423), (1432)

(2134), (2143), (2314), (2341), (2413), (2431)

(3124), (3142), (3214), (3241), (3412), (3421)

(4123), (4132), (4213), (4231), (4312), (4321).

 

Now, P(X) = 12/24 = 1/2

P(Y) = 12/24 = 1/2

P(X $\cap$ Y) = 6/24 = 1/4

 

From here, we can observe that P(X $\cap$ Y) = P(X) . P(Y).

So, X and Y are Independent Events.

So, Option B is Correct.

 

Let's not conclude here and try to observe all given options.

 

Option A : X and Y are Mutually Exclusive

X and Y will be Mutually Exclusive iff P(X $\cap$ Y) = 0, but this is not possible here. 

So, Option A is FALSE.

 

Option C : Either Event X or Y must Occur

This statement is FALSE as we have counter-example as : (4213)

So, Option C is FALSE.

 

Option D : Event X is more likely than Event Y.

This statement is clearly FALSE, as P(X) = P(Y).

Hence Event X and Event Y are equally Likely.

So, Option D is FALSE.

 

---

 

Correct Answer : B only

Comments

@Bhaskar_Saini but isn't it quite evident that the events are independent as for n numbers if 1 comes before 2 then it has nothing to do with 3 coming before 4. 

Answer 3

Let $n = 4$.

Therefore, the total number of permutations in the sample space is $|\Omega| = 4! = 24$.

1. Finding $P(X)$:

Event $X$ is the event that $1$ occurs before $2$.

• There are $\binom{4}{2}$ ways to choose places for $1$ and $2$ such that $1$ is before $2$.

• The remaining $2$ places can be arranged in $2!$ ways.

• Therefore, $|X| = \binom{4}{2} \times 2!$

$$P(X) = \frac{\binom{4}{2} \times 2!}{4!} = \frac{6 \times 2}{24} = \frac{1}{2}$$

2. Finding $P(Y)$:

Event $Y$ is the event that $3$ occurs before $4$.

• There are $\binom{4}{2}$ ways to choose places for $3$ and $4$ such that $3$ is before $4$.

• The remaining $2$ places can be arranged in $2!$ ways.

• Therefore, $|Y| = \binom{4}{2} \times 2!$

$$P(Y) = \frac{\binom{4}{2} \times 2!}{4!} = \frac{6 \times 2}{24} = \frac{1}{2}$$

3. Finding $P(X \cap Y)$:

This is the event where $1$ occurs before $2$, and $3$ occurs before $4$.

• $\binom{4}{2}$ ways to choose places for $1$ and $2$.

• $\binom{2}{2}$ ways to choose places for $3$ and $4$.

• Remaining $0$ places.

• Therefore, $|X \cap Y| = \binom{4}{2} \times \binom{2}{2}$

$$P(X \cap Y) = \frac{\binom{4}{2} \times \binom{2}{2}}{4!} = \frac{6 \times 1}{24} = \frac{1}{4}$$

Options Analysis:

Checking Option (B): To check for independence, we verify if $P(X \cap Y) = P(X) \cdot P(Y)$

$$\frac{1}{4} = \frac{1}{2} \cdot \frac{1}{2}$$

This is True. Therefore, events $X$ and $Y$ are independent.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Checking Option (D):

Since $P(X) = P(Y) = \frac{1}{2}$, event $X$ is not more likely than event $Y$.

$\therefore$ Option (D) is False.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Checking Option (A):

If they were mutually exclusive, then $X \cap Y = \emptyset$.

Let's check possible values for $X$ and $Y$:

• For $X$, a sequence like 1 2 _ _ is possible.

• For $Y$, a sequence like _ _ 3 4 is possible.

• Combining these, the permutation 1 2 3 4 is possible.

  Since $X \cap Y \neq \emptyset$, they are not mutually exclusive.

  $\therefore$ Option (A) is False.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Checking Option (C):

Let's consider the permutation 2 1 4 3.

This is a valid part of the $4!$ permutations, but it belongs to neither $X$ (since $2$ is before $1$) nor $Y$ (since $4$ is before $3$).

Since it is possible that neither occurs, it is not necessary that either $X$ or $Y$ must occur.

$\therefore$ Option (C) is False.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Correct Answer: (B)

Answer 4

Ans

Answer 5

• Event X is only about the relationship between {1, 2}.
• Event Y is only about the relationship between {3, 4}.
• Hence, There can be No Relationship between X and Y.
• Independent
• Option B = Correct