# Number of unique sets from subsets

I have six sets: {2, 6}, {2, 6}, {1, 3}, {1, 5}, {4, 5} and {3, 4}. How many different combinations can I produce by taking one value from each set so that I produce the set {1, 2, 3, 4, 5, 6}?

A possible combination is:

S1: 2 S2: 6 S3: 1 S4: 5 S5: 4 S6: 3

and another:

S1: 6 S2: 2 S3: 1 S4: 5 S5: 4 S6: 3

-
To be picky, you have only five sets since $\{2,6\} = \{2,6\}$. This eliminates some possibilities, since you can only choose a 2 or a 6 from that set, as opposed to choosing a 2 from the "first" set and a 6 from the "second" one. Your meaning is clear but the notation doesn't express what you want. –  Patrick Mar 7 '12 at 16:32

Picky note: Use curly braces for sets: $\{2,6\}$ not $(2,6)$.

You must either choose 2 from the first $\{2,6\}$ or the second $\{2,6\}$ and then are forced to choose $6$ from the opposite pair.

Next, you must choose $3$ from either $\{1,3\}$ or $\{3,4\}$.

Case 1: Choose $3$ from $\{1,3\}$ forces you to choose $1$ from $\{1,5\}$ which forces $5$ to be chosen from $\{4,5\}$ which then forces $4$ to be chosen from $\{3,4\}$

Case 2: Choose $3$ from $\{3,4\}$ forces $4$ to be chosen from $\{4,5\}$ etc.

Thus there are 2 ways to deal with 2 and 6 and 2 ways to deal with 1,3,4,5. These options are independent, so there are a total of $4=2\cdot 2$ ways to choose.

-
Is this brute-force method the best way to go? –  John Mar 7 '12 at 16:00
I'm not sure there is a nice "slick" way to proceed. I think brute force is about all you can do. This sort of counting problem gets really complicated as the size of the problem increases. It's not terribly far off from a knapsack problem. –  Bill Cook Mar 7 '12 at 16:42