Discrete Mathematics for Computer Science

430 CHAPTER 7 Counting and Combinatorics

= 6.6-6.6.6

= 7776

(# 1-1 functions) (# Possible images of a) • (# Possible images of b)

(excluding the image of a) ... (# Possible images of e)

(excluding the images of a, b, c, d)

=6.5.4.3.2

= 720

Therefore, the total number of functions that are not 1-1 is

7776 - 720 = 7056 U

73.2 Using the Pigeon-Hole Principle

The Pigeon-Hole Principle (see Section 4.6 ) states that if m objects are to be put in n

locations, where m > n > 0, then at least one location must receive at least two objects.

Thus, to prove that a set of objects has at least two elements with the same property, first

count the number of distinct properties of objects in the set, and then count the number of

distinct elements. If the total number of elements is larger than the number of distinct prop-

erties of objects, then the Pigeon-Hole Principle implies that at least two of the elements

have the same property. The next example is an illustration of this type of argument.

Example 9. A local bank requires customers to choose a four-digit code to use with an

ATM card. The code must consist of two letters in the first two positions and two digits in

the other two positions. The bank has 75,000 customers. Show that at least two customers

choose the same four-digit code.

Solution. First, use the Multiplication Principle to calculate the number of distinct codes

possible:

(# Four-symbol codes) = (# Choices of letter 1) • (# Choices for letter 2)

• (# Choices for digit 1) • (# Choices for digit 2)
  = 26 .26. 10. 10
  = 67,600

Now, apply the Pigeon-Hole Principle. Since there are 75,000 customers and only 67,600

codes, the Pigeon-Hole Principle implies that at least two of the customers choose the same

code. E

The Pigeon-Hole Principle gives very sketchy information about what could actually

happen when the 75,000 customers choose four-digit codes. One possibility is that the

same code is chosen by all customers. Another possibility is that all codes are chosen at

least once and at most twice. In Example 4, the Pigeon-Hole Principle only says that at

least two customers choose the same code.

The Generalized Pigeon-Hole Principle can give us answers that will tell us more than

simply that a single value is repeated at least once.