Many mathematical proofs and techniques boil down to being able to count things when they are sorted into various groups, to being able to answer questions that start out "how many ...? ". The field of mathematics dealing with advanced methods of counting things is called combinatorics. Many of these combinatorical methods are a spin off from probability theory.
All these methods start with a set of things to be arranged and counted. Any set of things can be used, but for definiteness, a finite or infinite set of natural numbers (0, 1, 2, 3, ... etc.) is frequently used. We will denote our set of things, whatever it is, by the letter S.
Let's assume S = { 1, 2, 3, 4, 5, 6 } for awhile. One thing you can do with S is list its elements in a sequence in various orders, such as 1, 2, 3, 4, 5, 6 or 2, 4, 6, 5, 3, 1 or many other variations. A natural question is: how many of these sequences are there?
A sequence like this can be described by listing its first element, then its second, and so on until you reach the last symbol in the sequence. Now, since S has 6 elements, there are 6 possible choices for the first element in the sequence. After choosing one of these elements, there are 5 possible choices left for the second element. This leaves 4 choices for the third position, and so on, until there is only one element left for the 6th position. This means there are 6*5*4*3*2*1 = 720 possible ways to choose a sequence from S, so there must be 720 distinct sequences, answering our first question.
Algebraic expressions like n*(n-1)*(n-2)*...*2*1 are so common in combinatorics that mathematicians have invented a symbol for this special operation. It's called the factorial operation and is symbolized by the exclamation point ("!") character. We will make the definition:
n ! = n * (n-1) * (n-2) * ... * 2 *1, for any n greater than 0The symbol "n!" is read "n factorial" if you're still moving your lips when you read. For convenience in simplifying our formulas, we define 0! = 1! = 1. (Note: the ! sign has nothing to do with expressing surprise or amazement. However, it may have something to do with how big n! gets to be, even for small values of n.) In general, if there are n things in our set S, you can arrange these things into n! distinct sequences. These sequences are sometimes called "permutations of the set S", though we will introduce a more general definition of the term permutation in the next section.
A more general question about S than the first one is: how many sequences can you make from S when the sequences are only 4 symbols long? Examples of such sequences are 1, 2, 3, 4 or 5, 3, 6, 2.
We can reason in a similar manner as we did in the first case. There are 6 choices for the first position, 5 for the second, 4 for the third, 3 for the fourth, and ... stop! Hence there are 6*5*4*3 = 360 possible sequences.
Let's look at this situation from another perspective. Let's start with the full 6 element sequences of the first case, all 6! = 720 of them, and divide them into groups. We'll put two sequences in the same group if they have exactly the same symbols in their first 4 positions. Therefore, sequences in the same group can only differ in the last two positions. Assuming we've already chosen the first 4 positions, there are just 2! = 2*1 ways to choose elements for the last two positions. Hence, we can conclude each group contains exactly 2 sequences. This means the number of groups = (total number of 6-sequences)/(number of sequences in each group) = 6! / 2! = 720 / 2 = 360, the same result we got before.
Generalizing this argument, if S has n elements, there are a total of n! sequences in S. Restrict our attention to sequences that are r positions long, where r is less than or equal to n. Divide up the full sequences into groups that agree on the first r positions and disagree on the final (n-r) positions. Each group has (n-r)! members. So the number of groups or "permutations of n things, taken r at a time", written as P(n;r) for short, is simply:
P(n;r) = n ! / (n-r) !If n = r, then (n-r)! = 0! = 1. Therefore, the number of sequences of all n elements at a time is P(n;n) = n!/0! = n!, which agrees with our calculation in the simpler first case.
Combinations are like permutations, except that the order of the symbols is unimportant. So while the sequences 3, 4, 5, 6 and 6, 5, 4, 3 are distinct permutations of S, taken 4 at a time, they both represent the some "combination of 4 elements" because you can rearrange the order of these sequences so they agree. So, what is the total number of "combinations of n things, taken r at a time", written C(n;r)?
Again, let's take all the permutations of S, r at a time, and arrange these sequences into groups that are the same except for order. Since there are r! ways to rearrange the elements of these sequences of length r, each group must have exactly r! sequences. We already calculated that there are P(n;r) sequences, so the formula for C(n;r) is:
C(n;r) = P(n;r) / r ! = n ! /( (n-r) ! * r ! )So the number of combinations of 6 things, taken 4 at a time is C(6;4) = 6!/( 4! * 2!) = 720 / (24 * 2) = 15.
One of the most dramatic ways of displaying the values of the combination formula is a triangular grid known (in the West, at least) as Pascal's Triangle. All the values in Pascal's triangle are values of C(n;r) for various values of n and r. This pattern shows up in many areas of mathematics, including probability theory and algebra. An example of Pascal's Triangle can be found in one of McFnordland's articles in this site.
I can't leave the topic of combinatorics without at least mentioning one powerful proof technique, known as the Pidgeon Hole Principle (PHP). It gets its name from sorting mail into mail slots that are sometimes called pidgeon holes. In a nutshell, PHP says that if you divide n things into r groups, where n is strictly greater than r, then at least one of these groups will have more than 1 thing. In the finite case, this is a notion that easily agrees with common sense. However, it can get tricky when n and r are infinite, although this is where PHP arguments are sometimes at their most brilliant. Unfortunately, we'll have to leave off our discussion at this point.