Combinatorics: Combinations

Combinations are similar to permutations in that they were created to model a certain situation, however, that situation is a little different. In order to explain the meaning of a combination consider the following example:

You are a teacher creating a gift basket will different types of candies and toys, and you have a total of five different items to choose from. You want to create baskets with exactly 3 items and each of those items has to be different than the other. Your goal is to figure out how many different types of baskets you can create.

Now the basket can hold 3 items but the order of the items in the basket doesn’t matter. In order to get the answer you could try and list all the terms and eventually come up with 10 different possibilities.

{a,b,c} {a,b,d} {a,b,e} {a,c,d} {a,c,e} {a,d,e} {b,c,d} {b,c,e} {b,d,e} {c,d,e}

Generating these terms is a lot harder than cranking out permutations, and it would take an eternity to generate the number of different choices if we had something like 10 different items to choose from. So it’s our task as mathematicians to simplify this scenario into mathematical formula that can be used to model this situation.

The formula for combinations can be derived from the formula for r-permutations, but it first requires viewing r-permutations in a different way. Instead of just viewing it as a way to position elements in a certain number of positions, you must think of r-permutations as a two step process.

Step 1: Generate a sets of r-elements

Step 2: Order those r-elements

So the r-permutation formula is implicitly calculating both step 1 & step 2 at the same time. Since we want just the result of step 1 we must divide out step 2. Which is why we come to the following formula:

{n}\choose{r} = \frac{P(n,r)}{r!}

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