Combinatorics is simply the study and theory of counting.  It also acts as an introduction to the theory of probability and statistics.  Counting is a fairly simple thing to do, however combinatorics encompasses the studies of population statistics and logical probability as well.  One application of combinatorics is the Venn Diagram.  Developed by British logician John Venn during the nineteenth century, the Venn diagrams acted as a pictorial and visual representation of logical interactions among a set or sets to display statistical information that could be read easily. 

To draw a Venn diagram, first a rectangle is drawn to represent a universe (thus the rectangle is designated U).  Inside this rectangle, the sets are drawn as circles. An area of overlap between two circles (sets) contains elements that are common to both sets, and thus represents a third set.  Circles that do not overlap each other logically represent sets with no elements in common.  In order to clearly show how the different elements in overlapped subsets relate to each other, the circles are shaded and denoted by an equation. When the elements of any two sets, lets call them A and B for instance, are in common intersection, the equation AnB is used to denote that just the intersection or overlap is in relation to one another.  Therefore just the overlapped space between the two sets is shaped.  When both sets have a common union, the entire two sets and the intersecting third set are shaded.  This is denoted by AUB.  A set of all elements not in set A is called the compliment of A.  The same definition applies for each of the other included sets.  Take a look at this website to get a clearer understanding of the different shading methods.

 Venn diagrams are useful in surveys and statistics.  Lets take a look at an example that better demonstrates the convenience of the diagrams.  Take a population of 300 surveyed music listeners.  160 people like rock music, 140 people like techno, and 60 people like both.  Now, we know that the overlapping set (fans of both rock and techno) contains 60 people, therefore both the circles must contain 60 people less (because there are rock fans that don’t like only rock). The two sets are drawn inside the universe of 300 people.  One set will now include the 100 rock fans, and the other set, the 80 techno fans.  The diagram is very logical.   From this diagram, the total number of persons that dislike both rock and techno can be determined.  We know that the entire set within the universe contains rock and techno fans, therefore the total populations of the sets includes the only rock and techno fans.  Therefore, to find the number of people in the universe which dislike rock or techno, the populations of the set can be added together, and subtracted from the total universe. 100 rock fans +80 techno fans + 60 rock or techno fans = 240 total rock and techno fans.  300 total music fans – 240 rock and techno fans = 60 people who don’t care much for either of the referred music genres.

With the basic premise of Venn diagrams behind us, we can now dive further into other applications of combinatorics.  Lets say you had 6 pairs of khakis and 2 tee shirts.  How many different t-shirt to khaki outfits can you wear?  This question takes us into the theory or probability and multiplication principles.  The multiplication principle states that if an action can be performed in n ways, for each of these ways another action can be performed in m ways, than the two actions can be performed in nm ways.  To answer the question, knowing that you are either choosing a t-shirt or a pair of khakis, the number of khakis to t-shirts can be simply multiplied.  6 x 2 = 12.  12 different outfits can be created due to the multiplication principle.  From this principle, this application can be expanded to permutations and combinations.

Permutations and combinations have become the basis for combinatorics in mathematics.  Perms and Combs focus directly on counting, probability, and statistical reasoning. By textbook definition, combinations pay no attention to the order of a certain arrangement. In permutations, however, different orderings are counted as distinct, and repetitions of the elements selected may or may not be allowed.

The best example to demonstrate the definition of a permutation would be the combination lock (sounds wrong, but just wait).  In a combination lock, the order in which a person enters his or her combination matters greatly.  Lets say your combination is 11,22,33.  If you tried to enter the numbers out of order like 22,11,33, the lock would not open.  Now you can see that the name of the lock (combination) is a major and overlooked flaw.  The combination factor may have only played a factor in constructing the locks (creating the numeric codes for each of the locks).

Suppose that we are given 3 different objects. We’ll designate them as n.  A selection of 2 letters (we’ll call this number r) arranged in a particular order is called a permutation of 3 letters taken 2 at a time and the number of permutations of n objects taken r at time is denoted _nP_r. We can now see that there are six permutations of these objects taken two at a time, namely, AB, BA, AC, CA, BC, CB. We see that ₃P₂ = 6. From this we get the formula _nP_r which is short for n!/(n-r)!.

Now lets use our knowledge of permutations to explain combinations.  Suppose that we are given the same 3 letters again. A selection of just 2 of them, without regard to the order of arrangement of the objects, is called a combination of 3 objects taken 2 at a time. This number of combinations of n objects taken r at a time is denoted _nC_r which is short for n!/(n-r)!r!.  You must realized that a combination differs from a permutation in that a combination does not take into account the order of an arrangement. For instance, we saw that the permutations of the three letters A, B, C taken two at a time are: AB, BA, AC, CA, BC, CB.  However, when we form combinations of these same three letters taken two at a time, the order of the letters does not count. For instance, the two permutations AB and BA are regarded as the same combination. There are only three combinations in this example, namely: AB, AC, BC. If you would like to find more information on permutations and combinations, take a look at this website.

Understanding Permutations and Combinations will now help you understand circular permutations, or permutations with repetition.  Suppose we take the world MAGNELLI. How many arrangements of the letters in the word can be made?  From this we can base off our solution on the original formula for permutations.  We see that in MAGNELLI, there are only two letters repeated.  Therefore we can use the following method to find the number of arrangements.  MAGNELLI is 8 letters, and there are two repetitions of the letter “l”.  Thus:  8!/2!.  From this we get an answer of 20,160 different arrangements. 

Well this is where we finally part.  I hope that my written documentation has made you all a bit clearer on the world of combinatorics and Chapter 15.  Thanks for visiting =)
-MIKE LING (4-30-01) (Mr. Magnelli, Period 1, Math Analysis)