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.

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.

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 2^{4}= 16 subsets, there would be _{16}C_{2}= 16!/(2! 14!)= 8(15)= 120 of those, not 25!

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:

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.

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.