Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Set size of a cartesian product!

  1. Sep 28, 2011 #1
    Set S with n elements!
    Set size of
    {<x,y> | (X,Y are proper subsets of S), (X union Y = S)!
    I tried doing something, but I'm stuck staring at a closed door, so I need a fresh start!
    Any hints would be appreciated!
     
  2. jcsd
  3. Sep 28, 2011 #2

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    If X has k elements, then how many elements does Y have?
    What is the minimum and maximum value for k?

    Maybe you can try writing out all the combinations for n = 2 and n = 3 to get some feeling for the problem.
     
  4. Sep 28, 2011 #3
    If x has k elements, than Y has n-k to n-k elements at most!
    Minimum value for k is 1, and max is n-1
    It's pretty much pointless to write about 2 elements since that way I'd have only 2 cartesian products only since by the condition sets are not subsets so they can't be equal to the parent ie we get two sets of 1 element!
    The same with 3 :/
     
  5. Sep 28, 2011 #4
    X union Y = S is a big clue.
     
  6. Sep 29, 2011 #5

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    Is there a typo, or did you just mean "n - k elements exactly"? :-)

    OK, here's another hint: how many different subsets of k elements can you choose from a set of n? In other words, how many possibilities are there for X?
     
  7. Sep 29, 2011 #6
    n-1 a typo....There are k^2 possibilities for X, and C of k from n for Y I think!
    PS.Can we go more direct with hints I'm deadline's due 02:15 GMT :)
     
  8. Sep 29, 2011 #7

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    You're almost there, just take a moment to think it through.

    C(n, k) is the number of k-element subsets you can make for X.

    Then Y has to contain all the other elements (and, if X and Y don't need to be disjoint, any subset of X. How many of those are there?)
     
  9. Sep 30, 2011 #8
    C(n,k), n-k the number of elements of Y, 2^(n-k) the number of subsets...by binomial I got 3^n!
    Thanks a lot guys
     
  10. Sep 30, 2011 #9
    C(n,k), n-k the number of elements of Y, 2^(n-k) the number of subsets...by binomial I got 3^n!
    Thanks a lot guys
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Set size of a cartesian product!
  1. Cartesian Products (Replies: 7)

Loading...