Set combination question

Got this as an homework assignment and not really sure where to start!

Given the set {1,2,3,4}, you can form six combinations of length two from that set, viz:

{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}

If I was to choose one of the combinations, ({1,2}开发者_Go百科 for example), how can I tell how many of the others are not disjoint to it? In this case it is four: {1,3},{1,4},{2,3}{2,4}

Not really sure about how to go about this mathematically, any pointers in the right direction would be much appreciated.

Number of subsets that can be formed from a set of n items taking r items at a time is

total = P(n, r) = n! / (r! * (n - r)!)

Let s be the selected combination. To find the number of subsets that are not disjoint with s, we start by finding the number of subsets that are disjoint with s - those sets that doesn't have any items in s (lets call that number k). Thus k is the number of subsets that can be formed from a set of n - r items, taking r at a time.

k = P(n - r, r) = (n - r)! / (r! * (n - r - r)!)
  = (n - r)! / (r! * (n - 2r)!)

Thus, the number of subsets disjoint with the selected set is:

total - k = P(n, r) - P(n - r, r)

Remember that this includes the selected subset s. Subtract one from this to get the number of disjoint sets with s.

Consider the following example:

//Let n = 6 and r = 2
total = P(n, r) = n! / (r! * (n - r)!) = 6! / (2! * 4!) = 15

k = P(n - r, r) = (n - r)! / (r! * (n - 2r)!) = 4! / (2! * 2!) = 6
answer = 15 - 6 = 9; answer excluding the selected set s = 8

//Super set: 
  {123456}
//Possible sub sets: 
  {12,13,14,15,16,23,24,25,26,34,35,36,45,46,56}  //15 items

//Let the selected set be {12}, then sets without 1 and 2: 
  {34,35,36,45,46,56} //6 items

//9 sets (including the selected set) are not disjoint with the selected set

Maybe start by reading some book or articles on combinatorics ..

If you can program, this library will help you.

I would do something like this:

For each item in my combination ( 1 then 2 ) do the following
* For each item in the set (1, 2, 3, then 4) do the following
** if set item is different from both combination item 1 and 2
*** print out combination item and print out set item

Try Combinatorics or better Permutations.

The sets X = {a, b} and Y are disjoint if a and b both do not appear in Y. Therefore, X and Y are not disjoint if a appears in Y or b appears in Y.

To find out how many other sets are not disjoint with {a, b}, consider all the possibilities: In general all the sets with two elements that are not disjoint with {a, b} are of the form {a, x} or {b, x}, for any x in the original set. If the original set had n elements, then there are n possibilities for {a, x} and another n for
{b, x}, for a total of 2*n*.

However, {a, b} is both of the form {a, x} (for x = b) and of the form {b, x} (for x = a), so we are counting it twice. We must count it zero times, because {a, b} is the same set as the one we were starting with. So we subtract 2, for a total of 2*n* - 2.

But we're still counting {a, a} (for x = a) and {b, b} (for x = b). But those only contain one element each ({a, a} = {a} and {b, b} = {b}), so we shouldn't count them. Therefore we subtract 2, for a total of 2*n* - 4.

For your example, {1, 2, 3, 4} gives n = 4, so the number of elements not disjoint with {1, 2} is 2*4 - 4 = 4.