Introductory Combinatorics (with Sesame St. pictures!)

Person

oLahav

Introductory Combinatorics (with Sesame St. pictures!)

Author: oLahav

Ask The Experts

Join Communities:

Study Abroad VISA

Online CAT 2010

Student Jobs

Online GRE 2010

Scholarship

Introduction to super-simple Combinatorics: Permutations and Combinations

Do you play poker? Are you a bingo fanatic? Do you enjoy arranging people in lines? If so, combinatorics is the area of mathematics that would appeal to you. If not, you should still read this, combinatorics are pretty cool.

Let's count!

We'll start off easy, and explain the concepts along the way. So here's a simple example- I have 3 shirts. How many ways can I choose a shirt to wear today? The answer is obvious, 3. But, say I have 2 pairs of pants. Now how many different outfits can I make? Intuitively, for each of the 3 shirts there are 2 pants selections, so the answer should be 2 * 3=6

. Now say I have 15 shirts, 5 pants, 3 pairs of shoes, but I can't wear a green shirt with my white pants and I can only wear black shoes with black pants. How many different outfits can I make now?

That's the basic idea of simple combinatorics- counting ways of choosing or selecting things. It gets complicated, but luckily we do have tools to deal with harder problems. Here comes the first one…

The factorial!

How many ways are there to order 3 people? Lets count them: A-B-C , A-C-B, B-A-C, B-C-A, C-A-B, C-B-A. That's 6. But how many ways are there to order 6 items? Do you really want to count all of those?

Didn't think so. There's a faster, cleaner way- the factorial, which has the symbol "!". Here's how it works: n!=n * (n-1) * (n-2) * ... * 3 * 2 * 1 . This gives you the number of ways to order n elements- the first place has n choices. Once you placed the first element, the second place has n-1 options to choose from, then n-2, etc. Most scientific calculators have a nice ! button you can just push and get an answer right away.

There is a neat little thing you should notice about factorials: (n-1) ! * n= n! . That's just a direct application of the formula.

Now that I can order things, what else is there to do?

There's a lot more. For example, say I don't want to order elements, but choose some elements from a set. Can combinatorics help?

Sure it can, but first you have to ask yourself an important question- is order important?

If we're selecting some elements from a set without putting them back, and order is important, we've got ourselves a permutation problem. To solve it, say our set has n elements but we want to choose r in a certain order. The formula to do so is: $_nP_r=n * (n-1)* ... * (n-r+1)=\frac{n !}{(n-r) !}$ . This formula makes intuitive sense, since for the first item we have n choices, for the second we have (n-1) choices, etc., until for the last element number r we have (n-r+1) choices, so we just multiply those together.

So say I have 7 cookies and want to eat 3. In how many ways can I do this? Easy: $_7P_3=\frac{7 ! }{4 ! }=\frac{5040}{24}=210$ . Now that's a lot of ways to eat 3 cookies!

What happens if we lose the order?

If we're selecting elements from a set without replacing them and order is not important, we have a combination problem. The formula for a combination is pretty the same formula for permutations, divided by the order of the r elements since we don't care about it. Makes sense. It looks like this: $_nC_r=\frac{n !}{(n-r) ! r !}$ . We can also write _nC_r as $\binom{n}{r}$ .

So say I have 7 cookies and I want to grab 3 and munch them all together, so order isn't important. Now there are $_7C_3=\frac{7 !} {4 ! 3 ! }=35$ . A lot less options if we don't care about order!

Most calculators have permute and combine buttons, though they may be a bit tricky to find.

Cool! Now what if we replace the items?

Say we've got a lottery with n numbers where we have to choose r, but each time we select 1 we put it back in the bag. What happens?

This is even simpler than permutations and combinations. The first number has n choices. The second has… n choices. So does the third and so on. The actual formula is really just n ^ r . Isn't that nice?

Combinatorics are clearly useful in real life. They can help you see how many different poker hands you can draw out of a pack of 52, or how many different table arrangements you can make with 6 flowers. Together with probability, p<>. combinatorics can help you crack black jack and other card games and thus earn you some money (though we won't specify how here, it's unethical). Clearly, the subject of combinatorics is good to understand.

Good news and bad news

The good news is, that's pretty much everything you need to know to solve simple combinatorics problems. Really, applying those mechanics will work every time.

The bad news is, it can get ugly. Sometimes you have to subtract out options that aren't allowed, or do other small tricks. The thing to do is- think, like every math question, analyze the situation and come up with a logical solution.