GATE CSE 2023 | Question: 38

Question

Let $U=\{1,2, \ldots, n\},$ where $n$ is a large positive integer greater than $1000.$ Let $k$ be a positive integer less than $n$. Let $A, B$ be subsets of $U$ with $|A|=|B|=k$ and $A \cap B=\emptyset$. We say that a permutation of $U$ separates $A$ from $B$ if one of the following is true.

• All members of $A$ appear in the permutation before any of the members of $B$.
• All members of $B$ appear in the permutation before any of the members of $A$.

How many permutations of $U$ separate $A$ from $B?$ 

• A. $n!$ 
• B. $\left(\begin{array}{c}n \\ 2 k\end{array}\right)(n-2 k)$ !
• C. $\left(\begin{array}{c}n \\ 2 k\end{array}\right)(n-2 k) !(k !)^{2}$
• D. $2\left(\begin{array}{c}n \\ 2 k\end{array}\right)(n-2 k) !(k !)^{2}$

Comments

Detailed Video Solution: Permutation question, Separating Permutations of A,B (Click HERE)  

---

@Deepak Poonia Sir .. ! I don't know if anyone has said this or not .. but after watching the video solution of this question(though I've got the ans before)... I don't think anyone other than you sir, is present on this earth, who can make anyone understand this question better .! 

So grateful for the your videos! #bestteacher

Answer 1

Option D

|A|=|B|=k

elements of A followed by elements of B => k!k!

elements of B followed by elements of A => k!k!

1 → number of permutations of 2k elements of A and B = 2k!k! ways

this will create 2k+1 positions for the rest of n-2k elements.

p objects can be placed in q places such that each place can have 0 to p objects in C(p+q-1, q-1) ways

2 → there for n-2k elements can be placed in 2k+1 positions in C(n-2k+2k+1-1, 2k+1-1) = C(n, 2k) ways.

3 → Also these n-2k elements can also be permuted => (n-2k)!

So total number of permutations of U which separates A from B = 2(k!)(k!)C(n, 2k)(n-2k)!, which is option D

Comments

p objects can be placed in q places such that each place can have 0 to p objects in C(p+q-1, q-1) ways

Can someone explain this? 

Answer 2

Instead of taking variables lets take a small example to first understand the question, once that’s done, the solutions would seem pretty intuitive!

Let n = 6

U = {1,2,3,4,5,6}

A = {1,2} and B = {4,5}

Here k = 2 and A ^ B = phi

Now, coming to the solution,

Step 1 : We first select 2k elements from n elements for creating A and B i.e $nC2k$

Step 2 : Elements in A and B can permute amongst themselves respectively so $k! * k!$ i.e $nC2k * k! * k!$

Step 3 : Now there can be two cases – AB and BA i.e $nC2k * k! * k! * 2$

Step 4 : The remaining elements (n-2k) can arrange in any way so $(n-2k)!$ i.e $nC2k * k! * k! * 2 * (n-2k)!$

Thus, our solution becomes Option D.

Comments

it is already mentioned in the question that n is large positive integer, so is it fine to take such a small value of n?

---

$\textbf{For example is not a proof 🙃}$ 

Standard Resource 👇

 

 

---

Shouldnt there be 6 cases…

Say A and B are sets as per question, let's take C as a set representing what is left out of U, as in C = U - ( A + B ), here + is union…

So the cases would be ABC, ACB, BAC, BCA, CAB, CBA ...

I know this is dumb, pls crt where I m wrong...

---

Louder !!

Answer 3

$$\text{initial perumutation : 1 2 3 4 } \dots \text{ n-1 n}$$

Construction

1. Select $n \ –\  2k$ elements out of the initial permutation lets call them separator elements (elements which dont belong to either A or B)
2. Now out of remaining $2k$ elements
   1. we will select the first k remaining elements to belong to set A (due to condition all Ai must be before Bi)
   2. we will select the last k remaining elements to belong to set B
   3. we will do the vice versa also
3. permute the the separator elements
4. permute the elements of A(within A) and B(within B)

Ans becomes $$\text{doing the construction for A,B and B,A}$$

=$$2 \times \binom{n}{n-2k} \times 1 \times 1 \times (n-2k)! \times k! \times k!$$

the factors 1,1 are because there is only way to pick the elements which are supposed belong to A,B respectively as shown in construction