Register

GATE CSE 2023 | Question: 38

• edited by
6,546 views
14 votes
14 votes

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

  1. $n!$ 
  2. $\left(\begin{array}{c}n \\ 2 k\end{array}\right)(n-2 k)$ !
  3. $\left(\begin{array}{c}n \\ 2 k\end{array}\right)(n-2 k) !(k !)^{2}$
  4. $2\left(\begin{array}{c}n \\ 2 k\end{array}\right)(n-2 k) !(k !)^{2}$
• edited by
User Avatar

3 Answers

5 votes
5 votes
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
User Avatar
4 votes
4 votes

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.

User Avatar
0 votes
0 votes

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

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

7 votes
7 votes
2 answers
1
gatecse asked Feb 8, 2021
714 views
GATE Overflow Test Series | Mock GATE | Test 5 | Question: 38
How many triangles can be formed with vertices on a $3 \times3 $ grid of squares? $516$ $548$ $536$ None of these
How many triangles can be formed with vertices on a $3 \times3 $ grid of squares?$516$$548$$536$None of these
User Avatar
7 votes
7 votes
4 answers
2
admin asked Feb 15, 2023
7,949 views
GATE CSE 2023 | Question: 5
The Lucas sequence $L_{n}$ is defined by the recurrence relation: \[ L_{n}=L_{n-1}+L_{n-2}, \quad \text { for } \quad n \geq 3, \] with $L_{1}=1$ and $L_{2}=3$ ... $L_{n}=\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}$
The Lucas sequence $L_{n}$ is defined by the recurrence relation:\[L_{n}=L_{n-1}+L_{n-2}, \quad \text { for } \quad n \geq 3,\]with $L_{1}=1$ and $L_{2}=3$.Which one of t...
User Avatar
Link Copied!