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

@Deepak Poonia Respected Sir, what are the possible variations that can be possibly created? Suppose if I say, two elements must appear consecutively . 

---

i create story for this ..first select 2k positions for A and B ..now (n-2k) for reaming in U so we can permutate any way i.e (n-2k)! now coming to A first permutate A elements i.e k! then B k!... symmetric also possible ...so 2( n  2k ​ )(n−2k)!(k!) 2

---

https://youtu.be/C1CjtxYEbeM?t=2198

Answer 1

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

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 !!

---

An imp advice.... If you start doing proof while in exam then blunder will happen

Answer 2

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

Comments

Yes only intuitive answer.
Selecting n-2k elements out of n seems more intuitive. SInce now you can say that rest k positions can be evenly split into A and B groups, so that first k elements are from A and last k elements are from B. This also helps in seeing how elements from A are kept before B. Same goes for first k elements for B and last k for A.

Rest of the answers miss this proper ordering intuiton.

---

To expand on why the factors 1 and 1:

- after choosing 2k elements out of n, usually we would assign those elements to A and B in 2kCk ways, but doing this will result in arrangements where the elements of A and B are mixed up. We do not want that.

So we simply say first k elements belong to A and the next k elements belong B, leading to only 1 arrangement.

If elements of A and B could mix, we would have the factor 2kCk instead of 1.

---

@firefrost_ind_125 Yes, you're right!!! 

Answer 3

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? 

---

Why there is 2k+1 position?

---

Because set U of size n and n>k so assume n=k+1. And n-2k elements positions are taken by A and B so 2k+1 remaining for U: n-2k+ 2k+1 = n+1 total

Answer 4

Answer: Option D

$U = \{1,2,3..n\}$

$n > 1000$ (does not matter,given as you do not put value of $n$ and compute)

$|A| = |B| = k < n$

$A \cap B = \phi$

From $n$, you have to select $2k$ elements for places of A and B => $\binom{n}{2k}$

Rest $n-2k$ element can permute between themselves => $(n - 2k)!$

From $2k$ elements, we have $2$ options

(i) all elements of $A$ come before $B$ => $k!.k!$ (all elements of $A$ and $B$ can permute between themselves)

or

(ii) all elements of $B$ come before $A$ => $k!.k!$

hence, $k!.k! + k!.k! = 2(k!)(k!)$

Now multiplying them all,

$= C(n, 2k) * (n - 2k)! * 2(k!)(k!)$

Comments

@nintendoit since A and B are sets for which we have chosen K elements each out of N element set U why do we need to evaluate the ways in which elements in A and B will arrange themselves as A and B are sets of elements K each.

Also could you please explain why did we consider (n-2k) elements? For permutations of U separating A and B?

---

This is my interpretation of the question,

Since sets $A$ and $B$ are disjoint fixed subsets with $k$ elements each, we have the option to permute their specific elements in $k!$ ways respectively. Here, order matters because every arrangement of the elements within set $A$ and set $B$ placed into the final sequence creates a new and distinct permutation.

Therefore, we have:

• $k!$ ways to permute the elements of set $A$ amongst themselves.

• $k!$ ways to permute the elements of set $B$ amongst themselves.
   

---

we use $\binom{n}{2k}$ to choose the $2k$ positions (or empty slots) out of the $n$ total available positions in the final sequence where the elements of $A$ and $B$ will eventually sit.

After choosing these $2k$ positions, we have $(n-2k)$ empty positions left over in the sequence. The remaining $(n-2k)$ elements of the universal set $U$ (the ones that do not belong to $A$ or $B$) will fill these leftover spots.

• There are $(n-2k)!$ ways of arranging these remaining elements into the remaining $(n-2k)$ positions.

Finally, because the permutation must completely separate , we can place them into the chosen $2k$ positions in two valid orders: either all elements of $A$ occupy the first $k$ positions followed by all elements of $B$, or vice versa.

• This gives us a multiplier of $2$.

Answer 5

 

Option (D) is correct.

It is a very easy question, unlike its first impression.

Given,

n > 1000 and k < n.

also, |A| = |B| = k and A∩B  = ∅ which means n should be an even number.

To, follow the permutation rules we have to take all the members of A first and then B or vice-versa from U.

So, typically the number of permutations is coming as, |A| ! * |B| ! * 2 = 2 * ($|A|!)^{2}$ .

Comments

How did you decide that k should be an even number?

---

It was a mistake, it should be “n” not “k” because, for all odd n, we can not find such A and B where |A| = |B| and also A∩B  = ∅

---

Could you clarify? Say n is 1001, and k is 5. It satisfies the constraints right? It didn't say that k should be chosen such that 2k should be equal to n. Am I missing something? In fact if that was the case, then why do we even have (n-2k)! factor in the eqn, since if 2k = n, then this term would always be 1.

---

@Rohit Jacob you are right.There is nothing mentioned in the question that says ${n} ={2k}$.Only thing you can argue is that ${n} \geq {2k}$.Also n does not have to be even for this question.Being even/odd is completely irrelevant to this question.