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

haruspex
Homework Helper
Gold Member
2020 Award
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. haruspex
Homework Helper
Gold Member
2020 Award
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.

haruspex
Homework Helper
Gold Member
2020 Award
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?

haruspex
Homework Helper
Gold Member
2020 Award
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?