• Support PF! Buy your school textbooks, materials and every day products Here!

Probability and set theory

  • #1
utkarshakash
Gold Member
855
13

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 any one of the above.

[itex]P=\dfrac{^nC_2+^{n(n-1)}C_2+^{n(n-1)(n-2)}C_2.........+^{n!}C_2}{^{2^n}C_2}[/itex]
 

Answers and Replies

  • #2
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
33,193
5,259
What's the probability that A has n elements? That both have n elements?
 
  • #3
utkarshakash
Gold Member
855
13
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.:confused:
 
  • #4
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
33,193
5,259
The probability that A has n elements is 1/n. But I'm not sure.:confused:
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
utkarshakash
Gold Member
855
13
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.
 
  • #6
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
33,193
5,259
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?
 
  • #7
utkarshakash
Gold Member
855
13
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?
 
  • #8
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
33,193
5,259
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?
 

Related Threads on Probability and set theory

  • Last Post
Replies
23
Views
1K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
20
Views
2K
Replies
1
Views
911
Top