Discussion
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\)?
Answer: D
The count is \(2\binom{n}{2k}(n-2k)!\,(k!)^{2}\).
Build a separating permutation in steps:
- Choose the 2k positions that the members of \(A \cup B\) will occupy: \(\binom{n}{2k}\) ways.
- Fill the other \(n - 2k\) positions with the remaining elements: \((n-2k)!\) ways.
- Decide which set comes first in the chosen positions: 2 ways. The first k of those positions then hold that set and the last k the other.
- Arrange A within its k positions and B within its k positions: \(k!\,k! = (k!)^{2}\) ways.
Multiplying gives the answer. The option without the factor 2 counts only one of the two orders, the option without \((k!)^{2}\) forgets to arrange the members inside each set, and \(n!\) counts every permutation, separating or not.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development