## Sunday, April 27, 2008

### Intro to Combinatorics

So, the long awaited blog post on combinatorics from last Friday. At least its not 12 at night right? Haha. Anyways, here we gooo!

During the first period class on Friday we had our Logarithms and Exponents test. It wasn't fun. If you werent there for the test It would probably be a good idea to talk to Mr. K about a time in which you can re-write the test. They are worth marks you know :P

The afternoon class introduced us to this wonderful thing called combinatorics. Now Mr.K told us that this is basically a branch of math that involves counting. When prompted as to why it was called combinatorics rather then something like, countinatorics or something he gave us a sample problem.

Given 5 students and 5 chairs, how many different ways can those students be seated in those chairs? Now it is important to note that the question is HOW MANY different ways, and now WHAT ARE the ways. When asked what are the ways, we are prompted to list all possible combinations, which is a long and tedious (although not necessarily difficult) task. In the following image, we used a tree diagram, to go through all the possible combinations or students (named a,b,c,d and e).

(*note* this image can also be found in the slides, in case this is too small to read.)

Although we found the answer to our question of how many but listing out what all the combinations were, there is an easier way to do this, thanks to that handy dandy thing called a calculator. By hitting 5x4x3x2x1 (five times four times three times two times one) on our calculators we can find the total number of calculations without drawing out every single one. We did this by looking at the possibilities we had left. So if theres 5 open seats, and 5 students, we have a 5 choices. When we pick one, we're left with 4 students to choose for the 4 seats. When we pick another student theres 3 spots left, and so on. Thus you multiply 5 x 4 x 3 x 2 x 1 (1 because once you've used 4 of the 5, there aren't really any choices left.)

So Lets recap.

So Far...
-Unit is Called Combinatorics
-Tree Diagrams help
-Looking at your options and choices allows you to multiply to find HOW MANY different ways.
-HOW MANY, and WHAT ARE are two totally different things.
-Theres a difference between Long and Tedious, and Hard/Difficult.

Now Moving onward!

the next problem presented a twist, what happens when there are more then 1 option for each choice? An example of this was in the next problem.

HOW MANY different ways can a nickel, dime, and quarter land on a table?

So to solve this we have to look at the options available to us (or use a tree diagram again :] ).

To solve this we looked at our options. For any 1 coin there are 2 possible outcomes, either heads or tails. now because order doesn't matter in this case, we set up our tree like this. you read the tree, by following its branches. For every flip of the nickel that lands heads or tails, the dime can land either heads or tails, and for every flip of the dime, the quarter can land either heads or tails. This the total number of combinations is, 2 x 2 x 2 = 8 (as shown in the red there.)

Now the next problem changed one of the coins to a die, thus adding a bit of a wrench to the system. BUT since we're smarter then the average bears, we figured out quite quickly that the total number would be 2 x 2 x 6 = 24 (because the die has 6 sides...normally.)

After having gallivanted through a few problems like this Mr. K unveiled the pattern behind this specific branch of math.

Fundamental Principal of Counting
-If you have "M" number of ways to do one thing, and "N" number of things to do another thing, then there are M times N number of ways to do both things.

Above is the simplified version of the Principal of Counting. Basically if you can do one thing x number of ways and another y number of ways, then you can do both of them at the same time, x times y number of ways. (haha I basically just repeated it :P)

Shortly after we were introduced to this we were introduced to Factorial Notation

Factorial Notation
n! = n · (n-1)(n-2)(n-3)...3·2·1

Basically what that means is that (correct me if I'm wrong here ^_^;) is n factorial equals n times, n minus 1, times n minus 2, times n minus 3, etc etc until you get down to, 3 times 2 times 1. Now because not everyone wants to input that into their calculator, they have an EVEN EASIER WAY!

By hitting, [n][math][<][4] you can get the factorial of whatever you want. This input reads in normal terms, means, hit your n value (whatever it is, 4, 7, 234872398, 0.0000000000002) followed by math, the arrow left key, and then 4. You should end up with your n value followed by a ! symbol (which means factorial, not I really mean the letter n)

Now we come to the final little bit of this blog, using the slot method, and irregular combinations.

In the first problem illustrated on this slide, the question reads, "How Many "words" of 4 different letters can be made from the letters A,E,I,O,R,S,T?" On the slide you can see that we set up our slots. Because there is a 4 letter limit, we only used 4. With 7 letters, we simply filled in the slots as we went down the line, multiplying as we went. The result was 7 x 6 x 5 x 4 = 840 words.

The next question gives even more restrictions, asking how many of the words begin with a vowel, and end with a consonant. Yet again we set up our slots, with 4 places. This time though, we set up our restrictions first. Because there are only 4 vowels, and 3 consonants, we fill those in first (as shown in the diagram.) Then we take the remaining letters and fill in the two slots in the middles (5 and 4 respectively, because we already used two with the first and last letter).

Finally in the last question, all the stops are pulled, and we are required to use two separate "slot" mechanisms, to solve it. Using all the same methods as before we came up with 144 as our answer. Thus we completed the class and our introduction to Combinatorics and I've just about finished my scribe post.

To conclude
-Using Tree diagrams helps, but is sometimes really long
-Factorial Notation saves the day (on your calculator [n][math][<][4])
-Fundamental Principal of Counting is if there are M ways for one thing, and N ways for another, there are MN ways for both.
-Using a slot system like those seen in the slides can greatly help
-When there are restrictions on a problem, solve the restrictions FIRST, then everything else.

Alrighty, I think that about sums it up. You know the deal if somethings wrong, tell me, or edit it or whatever, or if you don't get something ask me and I'll try to put it a different way, and edit the post on here.

So the next scribe post is....

*checks scribe list*

Francis....