First, let us start with a basic counting problem. Say I have 3 shirts, 2 pants, and 3 pairs of shoes. How many different outfits can I make? To visualize this, one can make a tree, with 3 primary branches representing the 3 shirts, 2 tertiary branches spreading from each of the 3 primary branches representing the 2 pants, and another 3 branches spreading from each of the tertiary branches representing the 3 pairs of shoes. It sounds complicated, but it really is simple. For each shirt, there are 2 options of pants. For each shirt and pant combination, there are 3 options of shoes. So the total number of combinations are 3 shoes x 2 pants x 3 shirts=3(2)(3)=18.
From this example, the Rule of Counting can be deduced. If there are n_1 elements of type R_1, n_2 elements of type R_2, and in general n_i elements of type R_i, then the total number of combinations one can make with one element each of type R_1, R_2,...,R_i is the product (n_1)(n_2)...(n_i).
With this basic rule in hand, we can now take on some more counting examples. Say we have the letters A, B, C, & D. How many different 4 letter strings can be made from these four letters? ABCD is one, ABDC is another. It turns out that there are 24 possible strings that can be made from these four letters. The reasoning is fairly simple. For the first letter of the string, there are four possible choices: A, B, C, or D. After we choose one of these letters, that leaves 3 for the second choice, and then 2 for the third, and only one for the fourth and final choice. By the rule of counting, the number of total combinations would be
4(3)(2)(1)=24. In general, say we have n elements, and we want to make a n-element string out of these elements. Then the number of strings that can be made is simply n(n-1)(n-2)...1. Since this product occurs so often in counting, we denote it as n!, which is read as "n factorial."
Now say we have 6 die, and we roll them all at once, obtaining 6 numbers. How many different sets of 6 numbers can be rolled? By the Rule of Counting, each die has 6 options, and there are 6 die, therefore there are 6(6)(6)(6)(6)(6)=6^6 different possible rolled number sets. Say we have the binomial (a+b)^n. If we multiply out, how many terms would we get, before simplification? When we multiply out, each term will be of the form (a^i)(b^j), where i+j=n. Since there are n terms of (a+b) in the binomial, and each binomial has two elements that can be multiplied out, the total number of terms after multiplying out would be 2(2)...2, where there are n 2's in the product. This number is equal to 2^n. Say we have a set of n elements. How many subsets can be made from this set, including the null set (which has no elements) and the full set (which has every element)? We can look at this problem this way: when we form a subset, we go through each of the n elements, and decide either to "yes" include the element in the subset, or "no" do not include the element in the subset. Therefore for each n elements, there are 2 options, either to include or exclude. Therefore the number of subsets is 2^n.
Onto a more complicated example. If we have a set of n elements, how many different ways can we choose a subset of k elements from this set? First, we must figure out the number of ways we can choose an ordered set of k elements from a set of n elements. This is simply n(n-1)...(k+1). Now the problem at hand is to find the number of different subsets of size k of a set of size n, which in other words is the number of unordered set of k elements. Each unordered set of k elements can be arranged k! times to give an ordered set of k elements. Therefore each unordered set gives k! ordered sets. Therefore if we have i as the number of unordered sets of k elements, the relation i(k!)=n(n-1)...(k+1) must hold. Solving for i, we get:
i=n(n-1)...(k+t)/(k!), which can be written as:
i=n!/[k!(n-k)!]
This expression occurs very often in mathematics, and is called the binomial coefficient. It is denoted (n k). It turns out that when the binomial (a+b)^n is multiplied out, the number of terms that are of the form (a^k)(b^(n-k)) is simply (n k). Why must this be the case? Because since there are n possible a's and we need to choose k from these n, the number of possible choices must be (n k). Also note that (n k) = (n n-k).
