Question

Let A be a set containing n elements, A subset P of A is chosen and set A is reconstructed by replacing the elements of P. A subset Q of A is chosen again. The number of ways of choosing P and Q such that Q contains just one element more than P is

• A. ²ⁿC_n-1
• B. ²ⁿC_n
• C. ²ⁿC_n+2
• D. 2²ⁿ⁺¹

Answer 1

The Correct Option is A

Let $A$ be a set with $n$ elements.

We want to count the number of ways to choose two subsets $P$ and $Q$ such that:

• $P \subseteq A$
• $Q \subseteq A$ 
• The number of elements in $Q$ is exactly one more than the number of elements in $P$

Step 1: Fix the size of $P$

Let the size of $P$ be $k$, where $k$ can range from $0$ to $n - 1$. (We stop at $n - 1$ because $Q$ must have $k+1$ elements, and $Q$ cannot have more than $n$ elements.)

Step 2: Choose $P$

There are $\binom{n}{k}$ ways to choose a subset $P$ with $k$ elements from the $n$ elements of $A$.

Step 3: Choose $Q$ such that $P \subset Q$ and $|Q| = k+1$

We must choose 1 element from the remaining $n - k$ elements (elements in $A$ but not in $P$) to add to $P$ to form $Q$.

This can be done in $\binom{n-k}{1}$ ways.

Total number of such pairs $(P, Q)$ for fixed $k$:

$\binom{n}{k} \cdot \binom{n - k}{1}$

Step 4: Sum over all valid values of $k$ (from $0$ to $n-1$):

$\sum_{k=0}^{n-1} \binom{n}{k} \cdot (n - k)$

This sum simplifies to: $\binom{2n}{n - 1}$

This is a known identity in combinatorics. Hence,

Final Answer: Option (A): $\binom{2n}{n - 1}$