Counting Primer (11/22/03)
prepared by:
Joseph Malkevitch
Mathematics Department
York College (CUNY)
Jamaica, New York 11451
Email: malkevitch@york.cuny.edu (for additions, suggestions, and corrections)
Suppose one has 4 shirts and 2 pairs of pants. For how many days can one wear a different outfit consisting of a shirt-pants pair? Can you see why the answer is 8 days?
Here is a way of seeing this geometrically. Think of the process of picking a shirt followed by a pair of pants as a two-stage process. In Stage 1 a shirt is picked. This is illustrated by the thick lines in the diagram below, which shows that in Stage 1, one can pick either shirt S1, S2, S3, or S4.
Having picked S1 in Stage I, one picks either of the pairs of pants P1 or P2 in Stage II. Similarly, if S2 was chosen in Stage I, one can pick either of the pairs of pants P1 or P2 in Stage II. The process can be extended to the other shirt choices in Stage I. We can illustrate this by extending the diagram above to see the results of the process of picking a shirt followed by a pair of pants. The less thick lines show the choices made at the second stage.
A diagram such as the above is known as a tree diagram. The labels at the points (vertices) of the tree diagram which have one edge (line segment) at them, and are known as the leaves of the tree, show the cumulative labels for the process. Thus, S3P2 indicates the third shirt and second pair of pants was worn. Clearly, the number of different outfits is 8, the product of 4 and 2. Note that the reason there are 8 outcomes stems in part from the fact that one can tell apart the 4 shirts and the two pairs of pants look different. That is, the objects involved are distinguishable from each other. Below, we will consider situations where one tries to count outcomes where some of the objects are alike.
This simple example contains the core of the idea known as the Fundamental Principle of Counting.:
If one wants to count the number of outcomes from a process carried out in two stages, where there are n1 outcomes for the first stage, and having completed this stage, the there are n2 outcomes for carrying out the second stage, then the number of outcomes from carrying out the stages one after the other is n1n2.
Furthermore, the idea can be extended to processes carried in k stages. If we know the number of ways of carrying out a k stage process, the number of outcomes as a result of carrying out all the stages is the product of the number of outcomes for each stage.
Here is an example of how to apply the fundamental principle of counting in a manner that reflects the way it might be used in practice. How long would it take for someone to break into someone elses computer account which is protected by a password consisting of 5 different vowels (a,e, i, o, or u), if 5 letter passwords can be tested at the rate of 10 a minute?
To solve this problem first let us count how many different passwords of the kind described there are. Typical example of legal passwords: aieou, aeiou, ieoau, or ouiea. Passwords such as aaaao or aiioo are not legal because we require the vowels in the password be different from each other. We can think of choosing a password of length 5 as a 5 stage process, where the first stage consists of picking a letter for the first symbol of the password. Since we are allowed the choice of a, e, i, o, or u we have 5 ways of carrying out this stage. Next, we must pick a vowel for the second letter of the password. Since this letter must be different from the first letter, and we have 5 vowels one of which was already used, there are 4 ways to pick the second letter of the password after having picked the first letter. Continuing in this way to count the ways of carrying out stages, 3, 4, and 5 we see that stage 3 can be carried out in 3 ways, stage 4 in two ways, and the last stage in one way, because after picking 4 vowels for the first four letters of the password, there is only one way to pick the last letter, the remaining vowel. Thus, there being 5, 4, 3, 2, and 1 ways of carrying out the 5 stages, the fundamental principle of counting allows us to concluder there are (5)(4)(3)(2)(1) ways to select a password. Carrying out the multiplications we see there are 120 ways to pick a password. If passwords can be entered at 10 a minute, dividing 10 into 120 we see that this system can be broken in 12 minutes. If the system allowed the repetition of vowels in a password, thus, permitting passwords such as aaaoo or uiuou, the fundamental principle of counting shows there would be (5)(5)(5)(5)(5) different passwords. This would be 3125 passwords. If one tries to break this system entering 10 passwords a minute, it would take about 313 minutes or 5 hours and 13 minutes to guarantee that one finds the right password. This is somewhat better security; perhaps enough to discourage someone from breaking into an email account. However, many people might have the patience if the password allowed one to transfer $10,000 into ones own bank account!
Having a powerful tool such as the fundamental principle of counting available, one might try to apply this tool to problems that repeatedly come up in practice. Examples of this kind are counting the number of ways that one can select r distinct objects from n distinct objects. There are two possibilities to consider: the order in which the objects are selected makes a difference or the order of selection is irrelevant.
Consider the following two scenarios. The numbers are being kept artificially small to enable a complete enumeration in a reasonable amount of time.
a. Three of the 5 members of the Mathematics and Computer Science Club must be elected as President, Vice President, and Treasurer.
b. Three of the 5 members of the Mathematics and Computer Science Club must be selected to travel to a local Mathematical Association of America meeting.
Can you see the reason the results of these two counts are different?
Suppose the Club members are names Alice, Bob, Carol, David, and Edward, denoted in the future by A, B, C, D, and E. If C is chosen as President, B as VP, and A as treasurer, this is very different from choosing A as President, B as VP, and C as treasurer. By contrast, the selection of C, B, and A to go to the meeting is the SAME as the selection of A, B, and C to go to the meeting. The presence or lack of order associated with the selection makes a difference in the two situations.
Here is a complete enumeration of the ways to elect a President, VP, and Treasurer, where the first letter listed indicates that the person was selected to be President, the second that the person was chosen to be VP, and the last that the person became the Treasurer:
ABC, ACB, BAC, BCA, CAB, CBA
ABD, ADB, BAD, BDA, DAB, DBA
ABE, AEB, BAE, BEA, EAB, EBA
ACD, ADC, CAD, CDA, DAC, DCA
ACE, AEC, CAE, CEA, EAC, ECA
ADE, AED, DAE, DEA, EAD, EDA
BCD. BDC, CBD, CDB, DBC, DCB
BCE, BEC, CBE, CEB, EBC, ECB
BDE, BED, DBE, DEB, EBD, EDB
CDE, CED, DCE, DEC, ECD, EDC
By contrast, there are many fewer ways to make the selection of a group of people to go to the meeting. Note that now, the triple ABC could be replaced by any of the other triples ACB, BAC, BCA, CAB, or CBA. You can think of ABC as the set {A, B, C} and as usual, the order in which elements are written in set notation is not relevant.
ABC
ABD
ABE
ACD
ACE
ADE
BCD
BCE
BDE
CDE
We will denote by nPr the number of ordered selections of r things from n. Ordered selections are often called permutations. We will denote by nCr the number of unordered selections of r things from n. Unordered selections are often called combinations. We can compute the value of nPr by a direct application of the fundamental principle of counting. There are n ways to pick the first item, (n-1) to pick the next one, and (n-r+1) ways to pick the rth item selected. Thus, by the fundamental principle of counting:
nPr = (n)(n-1)...(n-r+1)
A special case of this result is the number of ways to select n things from n where order matters:
nPn = (n)(n-1)(n-2)...(1)
It is convenient to have a special notation for (n)(n-1)(n-2)...(1). This notation is n!, which is read "n factorial." For example, 5! = 5(4)(3)(2)(1) = 120.
We can use the special case nPn to derive a way to count nCr. Since, if we are selecting r things from n, where order is not taken into account, all the r! different arrangements of r things selected from r things, where order did matter, "collapse" onto one selection, we can count nCr by counting nPr and dividing by r!. Thus:
nCr = (nPr)/(r!)
Note also, that in selecting r objects from n we are also selecting (n-r) objects to be left behind. Thus, nCr = nC(n-r).
The general formula here reflects the situation we saw above where we counted the number of committees one could select of size 3 from 5 people. Each committee of three corresponded to one of the 6 ways to arrange three letters (the first letters of the committee member names) among themselves where order was taken into account.
If one wants to know how many passwords can be made with all of the letters from the work COUNT, since the letters are distinct, the answer will be 5P5 which is 5! or 120. How many passwords can be made using all of the letters of the COMBINATORICS? This work has 13 letters but the answer is not 13! This is because not all of the letters in the word "combinatorics" are different. Here is a clever way that we can come up with the true answer. Pretend that the two c's, two i's, and two o's are different. These letters can be arranged in 13! ways. However, for each letter that is repeated, we will be overcounting by the number of ways that each of the repeated letters can be arranged among themselves. In this case, therefore, we have 13!/(2!)(2!)(2!) ways that the letters of combinatorics can be arranged in different orders that can be told apart from one another, despite the repeated symbols.
The general result here is that if we have k symbols, and there are n1 symbols of the first type, n2 symbols of the second type, ..., nk symbols of the kth type, then the number of ways that the n1 + n2 + ... + nk symbols can be arranged so that the strings with the repeated symbols can be told apart is given by (n1 + n2 + ... + nk)/(n1!)(n2!)....(nk!).
As an example of this, how many different ways can one arrange 3 blue, 2 black and 4 white file folders which can not be told apart except for color on a shelf? The answer is 9!/(3!)(2!)(4!).
Another type of "classical" combinatorics problems involves the placing of balls in boxes. These problems can be distinguished according as the boxes can or cannot be told apart and whether or not the balls can or cannot be told apart. Here are some examples to test your skill at determining what are the balls and what are the boxes, and whether or not the boxes and balls are distinguishable!
How many different ways are there to:
a. Pick the winning numbers for a church lottery where one gets to paint any of three numbers on four apples ordered in a row?
b. Custom design a box of a 12 chocolates where the chocolate candies have 4 varieties, each of which can be filled with one of three different fillings?
c. Count the number of patterns by which the 7 passengers in an elevator can get off at the three different floors above the ground floor of the building. (We do not care which passengers get off at a stop, only the pattern of how many of them there are.)
d. To hide six $5 bills in two identical books.
In some of the problems above different interpretations are possible according as one assumes that one can or cannot tell about the objects involved. (For example, $5 bills are not identical; they have different serial numbers but one can pretend that one cannot tell them apart.)
One can further subdivide problems of this kind according as boxes are allowed to be empty or not! This leads to 8 types of counting problems.
Here are the answers to these 4 basic different types of problems.
Type 1: r distinct balls to be placed into n distinct boxes:
nr
This result is a direct application of the fundamental principle of counting.
Type II: r identical balls to be placed into n distinct boxes
(n + r - 1)Cr
Here is the way to derive this rather surprising result. Think of the boxes as being in a row from left to right, and think of the balls as identical copies of the letter x. Suppose we have 3 boxes (n) and 5 balls (r). We can show the end of the content of a box, except for the last box, by putting a vertical line. Thus, for example, ||xxxxx means 0 balls in boxes 1 and 2 and 5 balls in box 3, xx|x|xx codes 2 balls in box 1, 1 in box 2 and 2 in box 3, and |xxxxx| codes that all the balls are in box 2. Think of the string that codes the number of ways of putting the balls into boxes as having 7 positions (7 because n-1+r is 3-1+5 =7). We need to select 2 of these 7 positions into which to put the verticle lines, and this can be done in (n + r - 1)Cr = (n + r - 1)C(n-1) ways! For example, when one choose to put the vertical lines in positions 2 and 4, one is coding the string x|x|xxx which means 1 ball in box 1, 1 ball in box 2 and three balls in box 3. How is that for clever. Here we have used the simple property that aCb = aC(a-b).
Type III: r distinct balls to be placed into n identical boxes
The numbers S(r,i) above are the Sterling numbers of the second kind. They are defined as follows:
S(r, n) is the number of ways that r distinct objects can be placed into n identical boxes so that no box is left empty.
The treatment of the Sterling numbers of the second kind is elementary but will take us too far afield and will not be treated in this essay. One approach to computing these numbers is the use of recursion relations.
Type IV: r identical balls to be placed into n identical boxes
The number of ways to partition r into n or fewer parts.
For example, the number of ways to place 6 identical balls into two identical boxes would 4; 6 balls could be placed into one box, none into the other; 5 balls in one box and 1 in the other, 4 balls into one box, 2 into the other; 3 balls could be put into each box. (Both 4 + 2 and 2 + 4 are considered the same partition of 6.)
References
Andrews, G., The Theory of Partitions, Cambridge U. Press, New York, 1984.
Bogart, K., Introductory Combinatorics, Second Edition, Harcourt, Brace, Jovanovich, New York 1990.
Bryant, V. Aspects of Combinatorics, Cambridge U. Press, New York, 1993.
Chuan-Chong, C. and K. Khee-Meng, Principles and Techniques of Combinatorics, World Scientific, Singapore, 1992.
Martin, G., Counting: The Art of Enumerative Combinatorics, Springer-Verlag, New York, 2001.
Roberts, F., Applied Combinatorics, Prentice-Hall, Englewood Cliffs, 1984.
Slomson, A. An Introduction to Combinatorics, Chapman and Hall, New York, 1991.
Tucker, A., Applied Combinatorics, 3rd edition, Wiley, New York, 1995.