1131

Principles of Combinatorics There are a number of principles that are useful in solving combinatorics problems. They are stated below, each with an illustration. 1. Pigeon Hole Principle If n + 1 objects are put into n boxes, then at least one box must contain 2 or more objects. (We show that if 5 points are placed inside a square whose sides 2 are 2 cm long, there will be at least one pair of points √ such that the distance between them is less than or equal to 2 cm. If we divide the square as shown, then at least two of the points must be in one of√these squares. But the length of the diagonals √ of the squares is 2. Hence, the two points cannot be further apart than 2 cm.)

2

2. Socks in a Drawer Principle If a drawer contains n pairs of socks and if the socks are all separate, a blindfolded individual would have to remove n + 1 socks to be sure of obtaining a matched pair of socks. (A drawer contains 7 pairs of socks. The socks are all separate. A blindfolded person would have to remove 9 socks from the drawer to be sure of getting 2 matched pairs.) 3. Some problems can be solved simply by Counting the various cases. (The number of digits to write out the numbers from 1 to 123 is 9+2(90)+3(24)=261.) 4. A cycle is a complete set of events which reoccurs in the same order. Some examples are the days of the week, the months in a year, and the hours in a day. (Suppose March 1 falls on a wednesday. To find what day June 30 falls on, we note that there are 30 more days in March, 30 in April, 31 in May, and 30 in June, a total of 121. This makes 17 weeks and 2 days, so that June 30 falls on a friday. 5. Multiplication Principle If one event can occur in m ways and after that event has occurred, a second event can occur in k ways, then the two events can occur in mk ways. (The numbers of even 3 digit numbers that can be constructed using the integers 1,2,3,4,5,6, and 7 if (a) repetition of integers is permitted and (b) repetitions are not permitted is (a) 3(7)(7) and (b) 3(6)(5).) 6. A permutation of n distinct object taken r at a time is any arrangement of r of the objects. Different arrangements of the same r objects are different permutations. For example, to ask how many 3-digit numbers that can be formed from the five digits 1,2,3,4,and 5 where repetitions are not allowed, is to ask for the number of permutations of the five digits taken three at a time. We can answer this by noting that the first digit of the 3-digit number can be chosen in 5 ways, the second digit in 4 ways, and the third digit in 3 ways. Using the Multiplication Principle, the number of 3-digit numbers is 5 · 4 · 3 = 60. If we denote the number of permutations of n distinct objects taken r at a time by n Pr , then the formula for n Pr is n Pr

= n(n − 1)(n − 2) · · · (n − r + 1) =

n! . (n − r)!

This formula is also correct for r = n if we define 0! = 1, in which case n Pn = n!. 7. In many applications, we are interested in the number of ways r objects can be selected from n distinct objects, and we are not concerned with the arrangement of the selected objects. For instance, we might be concerned with the number of ways a committee of three can be formed from seven people. We are interested in the membership of the committee, not on how the members are listed. A combination of n distinct objects taken r at a time is a subset of r objects. The number
n of such combinations is denoted by r or n Cr . It is given by 1

  n! n . = n Cr = r! (n − r)! r For example, the number of ways that a committee of three can be chosen from 7 people is   7 7! = 7 C3 = = 35. 3! 4! 3 8. Scheduling Principle In a league consisting of n teams, if each team is to play every other team k times, the number of games in the league’s schedule is k(n C2 ) = kn(n − 1)/2. (In a league with 4 teams, if each team plays every other team twice, the number of games is 2(4)(3)/2 = 12.)

2