1
$\begingroup$

A is a set containing n elements. A subset P of A is chosen at random. The set A is reconstructed by replacing the elements of the subset of P. A subset Q of A is again chosen at random. Find the probability that P and Q have no common elements.

I tried to calculate in this way :

In set P we can have no element i.e.Φ, 1 element, 2 elements, ...... upto n elements. If we have no element in P, we will leave by all the elements and number of set Q formed by those elements will have no common element in common with P. Similarly, it there are r elements in P we are left with rest of (n - r) element to form Q, satisfying the condition that P and Q should be disjoint.

enter image description here

Now, my confusion is how can I find the Total number of ways in which we can form P and Q?

$\endgroup$

3 Answers 3

1
$\begingroup$

Each element of $A$ has 3 choices- it can either be a part of $P$, of $Q$, or neither of the two, since it cannot be a part of both.

Hence by multiplication rule, for $n$ elements, total number of ways to divide the elements = $3^n$.

$\endgroup$
1
$\begingroup$

What you have done in the case $n=5$ is correct. If the first set has $k$ elements then the second set can be chosen in $2^{n-k}$ ways. Hence the total number us $\sum_{k=0}^{n} \binom {n} {k} 2^{n-k}=2^{n} (1+\frac 1 2)^{n}=3^{n}$.

$\endgroup$
1
  • $\begingroup$ What if $P$ and $Q$ are both non-empty. This is not asked by OP but I am wondering what the new expression would be $\endgroup$
    – Maverick
    Dec 2, 2023 at 13:28
-1
$\begingroup$

$P,Q$ can both be one of the $2^n$ subsets of $A$. The total number of ways to form $P$ and $Q$ is $2^n\cdot2^n=2^{2n}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .