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

What are Subset Pairs as mentioned in this problem?

  1. Oct 28, 2006 #1
    What are "Subset Pairs" as mentioned in this problem?

    In reference to this problem. BTW - I'm not asking for a solution or even a method of attack for a solution since I just enjoy doing these puzzles. I'm just trying to get clarification on one of the terms used.


    Say, for A={3, 5, 6, 7} (example pulled from here), what are the 25 subset pairs?
  2. jcsd
  3. Oct 28, 2006 #2


    User Avatar
    Science Advisor

    Something doesn't look right. There are only six pairs.
  4. Oct 28, 2006 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Which problem is that from?
  5. Oct 28, 2006 #4
    I assume it means you can pair a 1 element set with a 1, 2, or 3 element set, but you'd definitely not have to compare 1x1 element sets or nxm element sets where n doesn't equal m. But still, there are (2^4-1) non-empty subsets in that case. :dunno: I just can't find a pairing that counts to 25.

    :uhh: I posted the links to it right there
    Last edited: Oct 28, 2006
  6. Oct 29, 2006 #5


    User Avatar
    Science Advisor

    I think mathman was assuming that "subset pairs" meant "subsets with exactly two members"- there are only 6 of those.

    I, on the other hand, assumed it meant "pairs of subsets". Of course, since a 4 element set has 24= 16 subsets, there would be 16C2= 16!/(2! 14!)= 8(15)= 120 of those, not 25!
  7. Oct 29, 2006 #6


    User Avatar
    Science Advisor
    Homework Helper

    Both your links were to the project euler homepage, not to the specific problem you are looking at, which is possibly 106:


    A subset pair in that problem is a pair of disjoint, non-empty subsets. For your example A={3,5,6,7}. Just sort them by the sizes, for example pairs where both sets have 1 element:

    {{3},{5}}, {{3},{6}}, {{3},{7}}, {{5},{6}}, {{5},{7}}, {{6},{7}}

    Then look at 2 and 1 elements, 3 and 1 elements, finally 2 and 2 elements.

    To count them, count ordered subset pairs instead, then divide by 2. There are 4 ways to pick the first subset to have size 1, then 2^(4-1)-1=7 ways to pick the second set in the pair, so 28 so far. There are 4!/2!/2!=6 ways to pick the first subset to have size 2, 2^(4-2)-1=3 ways to pick the second set, so 18 more. There are 4 ways to pick the first subset to have size 3, and 1 way to pick it's pair, so another 4, for a total of 50. Divide by 2 to kill off our over counting from considering the order as distinct.
  8. Oct 29, 2006 #7
    Maybe the links are different when you're logged in, but they go to 106 and 103 for me. :dunno:

    Thanks for that explanation, I found my error:

    What I finally had was:

    (4 choose 1)*(3 choose 1) + (4 choose 2)*(2 choose 2) + (4 choose 1)*(3 choose 2) + (4 choose 1)*(3 choose 3)

    I forgot to divide the first and second terms by two :)
  9. Oct 29, 2006 #8


    User Avatar
    Science Advisor
    Homework Helper

    That must be, looking at the url of your links they are slightly different than the one I used. Your version must send you to a default page if you're not signed in to that website.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook