# Probability and set theory

Gold Member

## Homework Statement

Let X be a set containing n elements. If two subsets A and B of X are picked at random, the probability that A and B have the same number of elements is

## The Attempt at a Solution

Total number of subsets possible is 2^n. Now the subsets containing 1 element=n. For 2 elements it is n(n-1). Similarly for n elements it is n!. Now A and B can belong to any one of the above.

$P=\dfrac{^nC_2+^{n(n-1)}C_2+^{n(n-1)(n-2)}C_2.........+^{n!}C_2}{^{2^n}C_2}$

Homework Helper
Gold Member
What's the probability that A has n elements? That both have n elements?

Gold Member
What's the probability that A has n elements? That both have n elements?

The probability that A has n elements is 1/n. But I'm not sure.

Homework Helper
Gold Member
The probability that A has n elements is 1/n. But I'm not sure.
Sorry, I just realised I may have confused you by reusing n. I should have asked for the probability that A has, say, r elements. It isn't 1/r.
You have stated the total number of subsets, and they're all equally likely. How many have r elements?

Gold Member
Sorry, I just realised I may have confused you by reusing n. I should have asked for the probability that A has, say, r elements. It isn't 1/r.
You have stated the total number of subsets, and they're all equally likely. How many have r elements?

nCr.

Homework Helper
Gold Member
nCr.
Right, so what is the probability that an arbitrary subset A has r elements? What is the probability that A and B each have r elements? Thus, what is the probability that A and B have the same number of elements?

Gold Member
Right, so what is the probability that an arbitrary subset A has r elements? What is the probability that A and B each have r elements? Thus, what is the probability that A and B have the same number of elements?

The probability that A has r elements is nCr/2^n and the probability that A and B both have r elements is nCr*nCr/2^2n. Now I'll have to sum this as r varies from 0 to n. But I find this a bit difficult. I only know that 2^n=C0+C1+C2.....Cn. But how do I get squares on the coefficients?