CODEWITHSUNDEEP
setpermutationcombinatorics
MarkL
MarkL

Reputation: 11

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} 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.

Upvotes: 1

Views: 329

Answers (5)

Amarghosh
Amarghosh

Reputation: 59461

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

Upvotes: 1

Joren
Joren

Reputation: 14746

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.

Upvotes: 0

Juergen
Juergen

Reputation: 12738

Try Combinatorics or better Permutations.

Upvotes: 0

Kieveli
Kieveli

Reputation: 11084

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

Upvotes: 0

miku
miku

Reputation: 188134

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

If you can program, this library will help you.

Upvotes: 0

Related Questions