# Probability and set theory

1. Oct 20, 2013

### utkarshakash

1. The problem statement, all variables and given/known data
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

2. Relevant equations

3. 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}$

2. Oct 21, 2013

### haruspex

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

3. Oct 21, 2013

### utkarshakash

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

4. Oct 21, 2013

### haruspex

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?

5. Oct 22, 2013

### utkarshakash

nCr.

6. Oct 22, 2013

### haruspex

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?

7. Oct 22, 2013

### utkarshakash

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?

8. Oct 22, 2013

### haruspex

Here's a couple of hints.

Try doing that sum for a few small values of n. Do the numbers that result look familiar?

A sum like that can arise from multiplying together two series. E.g. suppose you multiply the expansions of (1+x)a and (1+x)b and collect up terms with the same power of x. Can you see how that would lead to sums of products of binomial coefficients? Can you find an a and b that would lead to a sum like the one we need to solve?