APPENDIX B
INTRODUCTION TO COMBINATORICS
In Chapter 1 we saw that probability in Laplace spaces reduces itself to counting the number of elements of a finite set. The mathematical theory dealing with counting problems of that sort is formally known as combinatorial analysis. All the counting techniques are based on the following fundamental principle.
Theorem B.l (The Basic Principle of Counting) Suppose that two experiments are carried out. The first one has m possible results and for each result of this experiment there are n possible results of the second experiment Then, the total number of possible results of the two experiments, when carried out in the indicated order, is mn.
Proof: The basic principle of counting can be proved by enumerating all possible results in the following way:
This array consists of m rows and n columns and therefore has mn entries. 
EXAMPLE B.1There are 10 professors in the statistics department of a University, each with 15 graduate students under their tutelage. If one professor and one of his students are going to be chosen to represent the department at an academic event, how many different ways can the selection be made?
In this case there are 10 possible ways to pick the professor and, once chosen, 15 ways of choosing the student. By the basic principle of counting there are 150 ways of selecting the pair that will represent the department. 
The basic principle of counting can be generalized as follows:
Theorem B.2 (Generalization of the Basic Principle of Counting) If r experiments are carried out in such a way that the first one has n1 possible outcomes, for each of those n1 results there are n2 possible results for the second experiment, for each outcome of the second experiment there are n3 possible results of the third experiment, and so on, then the total number of results when the r experiments are carried put in the indicated order is n1 × n2 × … × nr.
Proof: Left as an exercise for the reader.
The total number of automobile plate numbers that can be made if each plate number consists of three different letters and five numbers equals 26 × 25 × 24 × 105 = 1.56 × 109.
If a fair dice is rolled four consecutive times, then the total number of possible results of this experiment is 64 = 1296.
Suppose that there are n distinguishable balls and r distinguishable urns. Then the number of ways in which the balls can be put inside the urns equals rn. Indeed, the first ball can be placed in any of the r urns, the second ball can be placed in any of the r urns, and so on; therefore, there are
ways to put the balls inside the urns.
A permutation is an arrangement of objects from a given set in a particular order. For example, the permutations of the letters a, b, and c are abc, acb, bac, bca, cab, and cba. That is, there are six permutations of the three letters.
The total number of permutations of the objects belonging to a given set can be found without having to explicitly write down each possible permutation by reasoning as follows: Suppose that a set containing n elements is given, then the first position can be filled with any of the n numbers, the second position with any of the remaining n − 1 elements, the third position with any of the n − 2 remaining elements, and so on. Therefore, the total number P(n, n) of permutations of the n elements is:
P(n, n) = n(n − 1)(n − 2) … 1.
Since the product of a positive integer n with all the positive integers preceding is notated as n! and called n factorial, we can write:
P(n, n) = n!
Remember that, by definition, 0! := 1.
A permutation of n objects taken r ≤ n at a time is defined as an arrangement of r of the n objects in a particular order. Thus, the permutations of the letters a, b, c, and d taken two at a time are ab, ba, ac, ca, ad, da, bc, cb, bd, db, cd, and dc. That is, there are 12 permutations of the letters a, b, c and d taken two at a time. The total number P(n, r) of permutations of n objects taken r at a time can be found as follows: There are n objects that can be chosen for the first position, there are n − 1 objects that can be chosen for the second position, and so on, until we reach the rth position, for which there will be n − r + 1 possible objects to choose from. In other words:
Suppose that four girls and three boys have to be seated in a row. If the boys and girls can be seated in any order, then we would have 7! = 5040 ways to do so. If we wish that the boys and girls are alternated in the row, then there would be
4 × 3 × 3 × 2 × 2 × 1 × 1 = 144
ways to seat them. If we wish that the boys and the girls are seated together (boys with boys, girls with girls) then, there would be 2 × 4! × 3! = 288 ways to seat them.
A student wishes to put 4 calculus, 2 physics, 5 probability, and 3 algebra books on a shelf in such a way that all books belonging to the same subject are grouped together. There are 4! × 2! × 5! × 3! ways to place the books if the first ones are calculus books, then the physics books followed by the probability books and the algebra books. Since there are 4! ways to organize the subjects, there is a total of
4! × 4! × 2! × 5! × 3! = 8.2944 × 105
ways to put the books on the shelf.
We wish to calculate the number of ways in which 3 Mexican, 4 Egyptian, 3 English and 5 Chinese people can be seated at a round table if individuals of the same nationality insist on sitting together. In this case we have four groups of people: Mexicans, Egyptians, Englishmen, and Chinese. The number of ways to place this groups around the table is 3!. The Mexicans can be seated in 3! ways, the Egyptians in 4! ways, the English in 3! ways and the Chinese in 5! ways. Therefore, there are
3! × 3! × 4! × 3! × 5! = 6.2208 × 105
ways to seat the people around the table.
Let N be the number of different permutations of the letters in the word ”experiment”. If all the letters were different, then the total number of permutations would be 10!, but since the three “e” can be permuted between them in 3! ways, then 3!N = 10!. That is:
In general we have that the total number N of different permutations of n objects, of which n1, n2, …, nr are equal between them, is:
Suppose that there are n different objects. Each possible election of r ≤ n of the objects is called a combination of order r. In other words, a combination of order r from a set S with n elements is a subset of S having exactly r elements. For example, the combinations of order 2 of the letters a, b, c and d are {a, b}, {a, c}, {a, d}, {b, c}, {b, d} and {c, d}; that is, there are six possible combinations of order 2 of the letters a, b, c and d. To determine the number of combinations C(n, r) of order r taken from n objects, we observe that if we took the elements in order there would be P(n, r) ways of choosing the r objects, and since r objects can be permuted in r! ways, then:
The number C(n, r) is called “n choose r” and is written as 
. It is further defined that:
Five couples, each couple a man and a woman, must be chosen for a dance from a group consisting of 10 women and 12 men. We wish to determine the number of possible selections.
We have that there are 
ways to pick the men, and after they are chosen we select the women, which can be done in 
different ways. Therefore, there are
ways to pick the five couples.
A committee of 3 people must be formed by selecting its members from a group of 5 men and 3 women. How many possible committees are there? How many if the committee must have at least a woman? How many if two men do not get along and therefore cannot both be part of the committee? How many if there is a man-woman couple that would only accept to join the committee if they both belong to it?
First, we have that there are 
= 56 different ways of selecting the committee members.
Now, if the committee must have at least a woman, then there are
ways of selecting the committee.
In the case where two men do not get along, there are two options: either one of them is included or both are excluded, which means that there are
ways of selecting the committee.
Finally, in the last case we have two options, either both members of the couple are included or both are excluded, yielding
ways of selecting the committee.
A set of n elements is to be partitioned in m different groups of sizes n1, r2, …, rm, where:
r1 + r2 + … + rm = n.
We wish to find the number of different possible ways to accomplish this task. We observe that there are 
ways of selecting the first group, for every possible choice of the first group there are 
ways of selecting the second group, and so on. Therefore, there are
ways of selecting the groups. This number is called the multinomial coefficient and is notated as:
Thirty students in a third-grade class must be split in 5 groups, each having 12, 5, 3, 6 and 4 students, respectively. How many possible partitions are there? According to the previous example, we have that there are
possible ways to split the class.
Suppose that there are n indistinguishable balls. How many ways are there to distribute the n balls in r urns?
The result of this experiment can be described by a vector (x1, …, xr) where xi represents the number of balls placed on the ith urn. This allows us to reduce the problem to finding all the vectors (x1, …, xr) with nonnegative integer entries such that x1 + … + xr = n.
To solve this problem, suppose that the objects are put in a horizontal line and then divided in r groups by proceeding as follows: from the n − 1 spaces separating the objects we choose r − 1 and trace dividing lines there; by doing this we get r nonempty groups. That is, there are 
vectors (x1, …, xr) with positive components satisfying x1 + … + xr = n.
Since the number of nonnegative solutions of x1 + … + xr = n equals the number of positive solutions of y1 + … + yr = n + r with yi = xi + 1 for i = 1, 2, …, r, then the total number of ways to distribute the n indistinguishable balls inside the r urns is:
Twelve gifts are divided between 7 children. How many different distributions are possible? How many if each kid must get at least one present?
According to the previous example, there are 
= 18,564 ways of distributing the gifts between the children.
If, furthermore, each kid must receive at least one present, then, the number of possible distributions reduces to 
= 462.
EXERCISES
B.l How many three-digit numbers less than 500 with all digits different from each other can be formed with the digits 1,2,3,4,5,6 and 7?
B.2 How many three-digit numbers can be formed with the digits 1,4,8 and 5 if:
- The three digits are different?
- The numbers must be odd?
- The numbers must be divisible by 5?
B.3 How many ways are there to seat in a row four boys and four girls if they must be seated alternated? How many if the boys and the girls are seated together? How many if only the girls axe seated together?
B.4 An inspector checks six different machines during the day. In order to avoid the operators knowing when those inspections are going to be made, he varies the order each time. In how many ways can he do this?
B.5 A group of 5 German, 6 Australian, 4 Japanese and 6 Colombian people must be seated at a round table. How many ways are there to do this? How many if people having the same nationality must be together? How many if the Colombians must stay together?
B.6 How many different arrangements can be formed with the letters in the word “successes”?
B.7 In a probability exam, a student must answer 10 out of 13 questions. How many ways of answering the exam does the student have? How many if he must answer at least 3 from the first 5 questions? How many if he must answer exactly 3 of the first 5 questions?
B.8 The effects of two medications A and B are going to be compared in a pharmaceutical study involving 50 volunteers. Twenty volunteers receive medication A, another 20 receive medication B and the remaining 10 take a placebo. How many different ways of distributing the medications and placebos between the volunteers are there?
B.9 The statistics department of a university has 33 professors who must be divided into four groups of 15, 8, 7 and 3 members. How many possible partitions are there? How many if the 5 marked members of the advisor committee must be in the first group?
B.10 In how many ways can 7 gifts be divided between three children if one child must receive 3 of them and the other two kids must get 2 each?
B.11 The sciences faculty of a university has received 30 identical computers to be split between the 7 departments of the faculty. How many different distributions are possible? How many if each department must get at least 2 computers?
B.12 An investor has $600,000 to invest in six possible bonds. Each investment has to be made in thousands of dollars. How many investment strategies are possible?