1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Probability and set theory

  1. Oct 20, 2013 #1

    utkarshakash

    User Avatar
    Gold Member

    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.

    [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]
     
  2. jcsd
  3. Oct 21, 2013 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    What's the probability that A has n elements? That both have n elements?
     
  4. Oct 21, 2013 #3

    utkarshakash

    User Avatar
    Gold Member

    The probability that A has n elements is 1/n. But I'm not sure.:confused:
     
  5. Oct 21, 2013 #4

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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?
     
  6. Oct 22, 2013 #5

    utkarshakash

    User Avatar
    Gold Member

    nCr.
     
  7. Oct 22, 2013 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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?
     
  8. Oct 22, 2013 #7

    utkarshakash

    User Avatar
    Gold Member

    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?
     
  9. Oct 22, 2013 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Probability and set theory
  1. Set Theory (Replies: 11)

  2. Set theory (Replies: 2)

  3. Set theory (Replies: 4)

Loading...