Fascinating Facts About Sets, Subsets and Complements, and Combinations; Ordered and Unordered Selections With and Without Repetition

So you wanna learn about sets and you come across unordered selections with repetition (pt2) and unordered selections without repetition . Well, one thing that’s fascinating and useful for figuring all this out is that subsets of sets have complements (not spelled compliments). So if you have a set U and a subset A, the complement of A , written A^c will be everything in U that is not in subset A. The fascinating thing is that once you get into combinations, say you’re trying to find the number of all of the selections of r objects out of a total of n objects, you can figure that number out in two ways. You can figure out the number all the selections of r objects out of n objects directly…or you can figure out number of all the selections of the complements of the r objects. It’s sort of like yin and yang, negative space and positive space.

Each time you have one subset, it has a complement. And since there can be no repetition in sets, there will be no overlap between subsets and their complements. So for each unique subset, you have a unique complement. Which means…you can find out how many selections in the form of subsets there are directly, or by counting how many selections there are in the form of complements of the subsets there are. So if you want to find out how many selections of three things there are out of a total of five things, you can find that out also by finding out how many selections of two things there are. So that’s why {n \choose   r} = {n \choose n-r} in n choose r notation as far as I can tell. Wow!!!

Here’s a breakdown:

-ordered selections with repetition, (see tuples and cartesian products): n^m

-ordered selections without repetition, like permutations: n!/(n-m)!

-unordered selections with repetition: (n+r-1)!/(n-1)!r!    (I think)

-unordered selections without repetition, like combinations: n!/(m!(n-m!))

When you’re learning all this it’s important to note that notation-wise, tuples are surrounded by parentheses () while sets are surrounded by curly brackets {}.

Internal tag: math

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: