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. 2nCn-1
• B. 2nCn
• C. 2nCn+2
• D. 22n+1

Answer 1

Answer: (A)

2nCn-1

Answer 2

We have a set A with n elements.

We want to choose a subset P of A, and then a subset Q of A such that Q contains just one element more than P.

Let's consider the process step by step:

• First, we need to choose the size of P. It can have any size from 0 to n, so we have n+1 options for the size of P (0 elements, 1 element, 2 elements, ..., n elements).
• Once the size of P is chosen, Q must contain one more element. This means that if P has k elements, Q must have k+1 elements.

Therefore, the number of ways to choose P and Q such that Q contains one element more than P is the sum of the following:

• Choose the size of P (k elements) from the set A (n elements). This can be done in nCk ways.
• Choose the additional element for Q (1 element) from the remaining elements in A after removing P (n-k elements). This can be done in (n-k)C1 ways.

Combining these two choices, the total number of ways is the sum for all possible sizes of P (from 0 to n): Σ (nCk * (n-k)C1) for k = 0 to n

This can be simplified to: Σ (nCk * (n-k)) for k = 0 to n

Notice that this expression is equivalent to 2nC(n-1). This is because nCk * (n-k) = nC(n-k) (using the symmetry property of binomial coefficients).

Therefore, the total number of ways is 2nC(n-1), which justifies the given answer.

The correct answer is option (A): 2nCn-1