Do Two Random Subsets of X Have the Same Number of Elements?

[utkarshakash]

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

Homework Equations

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 anyone 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}$

 

[haruspex]

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

 

[utkarshakash]

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.

 

[haruspex]

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

Sorry, I just realized 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?

 

[utkarshakash]

Sorry, I just realized 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.

 

[haruspex]

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?

 

[utkarshakash]

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?

 

[haruspex]

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?

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?