Chapter 5

The Bijection Principle

We have introduced three basic principles for counting, namely, the (AP), the (MP) and the (CP). In this chapter, we shall introduce another basic principle for counting which we call the Bijection Principle, and discuss some of its applications.

Figure 5.1

Suppose that there are 200 parking lots in a multi-storey carpark. The carpark is full with each vehicle occupying a lot and each lot being occupied by a vehicle (see Figure 5.1). Then we know that the number of vehicles in the carpark is 200 without having to count the vehicles one by one. The number of vehicles and the number of lots are the same because there is a one-to-one correspondence between the set of vehicles and the set of lots in the carpark. This is a simple illustration of the Bijection Principle that we will soon state.

Let us first recall some concepts on mappings of sets. Suppose A and B are two given sets. A mapping f from A to B, denoted by

is a rule which assigns to each element a in A a unique element, denoted by f (a), in B. Four examples of mappings are shown pictorially in Figure 5.2.

Certain kinds of mappings are important. Let f : A → B be a mapping. We say that f is injective (or one-to-one) if in B whenever x ≠ y in A. Thus, in Figure 5.2, f₂ and f₄ are injective, while f₁ and f₃ are not (why?). We say that f is surjective (or onto) if for any b in B, there exists an a in A such that f(a) = b. Thus, in Figure 5.2, f₃ and f₄ are surjective whereas f₁ and f₂ are not (why?). We call f a bijection from A to B if f is both injective and surjective. (Sometimes, a bijection from A to B is referred to as a one-to-one correspondence between A and B.) Thus, in Figure 5.2, f₄ is the only bijection. These observations on the four mappings are summarised in Table 5.1.

Figure 5.2

Table 5.1

Let A and B be two finite sets. Suppose there is a mapping f: A → B that is injective. Then, by definition, each element a in A corresponds to its image f(a) in B, and distinct elements in A correspond to distinct images in B. Thus, we have:

Suppose further, that the one-to-one mapping f:A → B is onto. Then each element b in B has a unique preimage a in A such that f(a) = b. In this case, we clearly have:

In this chapter, we shall focus on (BP). Through the discussions on a number of problems, we shall show you how powerful this principle is.

First of all, let us revisit a problem we studied in Chapter 4. In Example 4.5, we counted the number of chords and the number of points of intersection of the chords joining some fixed points on the circumference of a circle. Let us consider a similar problem. Figure 5.3 shows five distinct points on the circumference of a circle.

How many chords can be formed by these points?

Let A be the set of such chords, and B, the set of 2-element subsets of {1,2,3,4, 5}. Given a chord α in A, define f(α) = {p,q}, where p, q are the two points (on the circumference) which determine the chord α (see Figure 5.4). Then β is a mapping from A to B. Clearly, if α and β are two distinct chords in A, then f(α) = f(β). Thus, f is injective. On the other hand, for any 2-element subset {p, q} in B (say, p = 2 and q = 5), there is a chord α in A (in this instance, α is the chord joining points 2 and 5) such that f(α) = {p,q}. Thus, f is onto.

Figure 5.3

Figure 5.4

Hence, f : A → B is a bijection and, by (BP), we have |A| = |B|. As B is the set of all 2-element subsets of We thus conclude that

Next we ask: How many points of intersection (of these chords) that lie in the interior of the circle are there if no three chords are concurrent in the interior of the circle?

Let A be the set of such points of intersection and B, the set of 4-element subsets of {1,2,3,4,5}. Figure 5.5 exhibits a bijection between A and B (figure out the rule which defines the bijection!). Thus, by (BP), by definition, we have

Figure 5.5

Let us proceed to show some more applications of (BP).

Example 5.1 Figure 5.6 shows a 2 × 4 rectangular grid with two specified corners P and Q. There are 12 horizontal segments and 10 vertical segments in the grid. A shortest P-Q route is a continuous path from P to Q consisting of 4 horizontal segments and 2 verticalsegments. An example is shown in Figure 5.6. How many shortest P-Q routes in the grid are there

Figure 5.6

Solution Certainly, we can solve the problem directly by listing all the possible shortest routes. This, however, would not be practical if we wish to solve the same problem in, say, a 190 × 100 rectangular grid. We look for a more efficient way.

There are two types of segments: horizontal and vertical. Let us use a “0” to represent a horizontal segment, and a “1” to represent a vertical segment. Thus, the shortest P–Q route shown in Figure 5.6 can accordingly be represented by the binary sequence with four “0”s and two “1”s as shown below:

and so on.

Now, let A be the set of all shortest P-Q routes and B, the set of all 6-digit binary sequences with two 1’s. Then we see that the above way of representing a shortest P-Q route in A by a binary sequence in B defines a mapping f : A → B. Clearly, different shortest P-Q routes in A correspond to different sequences in B under f. Thus, fis one-to-one. Further, for any sequence b in B, say, b = 100010, one can find a shortest P-Q route, a in A, in this case,so that f(a) = b. Thus f is onto, and so it is a bijection. Now, by (BP), we conclude that |A| = |B|. But how does this simplify our effort to find the number of shortest P-Q routes?

Let us explain. What is the set B? B is the set of all 6-digit binary sequences with two 1’s. Can we count |B|? Oh, yes! We have already solved it in Example 4.4. The answer is Accordingly, we have

Example 5.2 The power set of a set S, denoted by is the set of all subsets of S, inclusive of S and the empty set ø. Thus, for we have

Note that Table 3.1 shows that What is the value of ?

Solution For convenience, let that is, A is the power set of {1, 2, 3, 4, 5}. Represent these subsets by 5-digit binary sequences as follows:

The rule is that the ith digit of the corresponding binary sequence is “1” if “i” is in the subset; and “0” otherwise. Let B be the set of all 5-digit binary sequences. Clearly, the above rule establishes a bijection between A and B. Thus, by (BP), |A| = |B|. Since |B| = 2⁵ (see Example 2.2), |A| = 2⁵.

Note that What is for n ≥ 1? (See Exercise 5.3.)

Finally, let us introduce a counting problem related to the notion of divisors of natural numbers. We shall denote by , the set of natural numbers; i.e.

Assume that d,n ∈ . We say that d is a divisor of n if when n is divided by d, the remainder is zero. Thus, 3 is a divisor of 12, 5 is a divisor of 100, but 2 is not a divisor of 9.

Let n ∈ , n ≥ 2. Clearly, n has at least two divisors, namely 1 and n. How many divisors (inclusive of 1 and n) does n have? This is a type of problem that can often be found in mathematical competitions. We shall tackle this problem and see how (MP) and (BP) are used in solving the problem.

To understand the solution, we first recall a special type of numbers called prime numbers and state an important result relating natural numbers and prime numbers.

A natural number p is said to be prime (or called a prime) if p ≥ 2 and the only divisors of p are 1 and p. All prime numbers less than 100 are shown below:

The primes are often referred to as building blocks of numbers because every natural number can always be expressed uniquely as a product of some primes. For example,

This fact is so basic and important to the study of numbers that it is called the Fundamental Theorem of Arithmetic (FTA).

(FTA) was first studied by the Greek mathematician, Euclid (c. 450–380 BC) in the case where the number of primes is at most 4. It was the German mathematician, Carl Friedrich Gauss (1777–1855), known as the Prince of Mathematicians, who stated and proved the full result in 1801.

Let us now return to the problem of counting the number of divisors of n. How many divisors does the number 72 have? Since 72 is not a big number, we can get the answer simply by listing all the divisors of 72:

The way of counting the divisors of n by listing as shown above is certainly impractical when n gets larger. We look for a more efficient way.

The images above are those of Euclid on a stamp of the Maldives and Gauss on a German banknote.

 

Let us look at the example when n = 72 again and try to get some information about 72 and its divisors by (FTA).

Observe that 72 = 2³ × 3². Suppose x is a divisor of 72. Clearly, x does not contain prime factors other than 2 and 3. That is, x must be of the form

where, clearly, p ∈ {0,1, 2, 3} and q ∈ {0,1, 2}. On the other hand, any such number 2^p × 3^q is a divisor of 72. Indeed,

Let A be the set of divisors of 72 and Then the above list implies that the mapping f defined by

is a bijection from A to B. Thus, by (BP) and (MP), |A| = |B| = which agrees with the above listing.

The following example extends what we discussed above.

Example 5.3 Find the number of divisors of 12600.

Solution Observe that 12600 = 2³ × 3² × 5² × 7¹.

Thus a number z is a divisor of 12600 if and only if it is of the form

where a, b, c, d are integers such that and 0 ≤ d ≤ 1.

Let A be the set of divisors z of 12600 and Clearly, the mapping f defined by

is a bijection from A to B. Then, by (BP) and (MP), |A| = |B| =

We have seen from the above examples how crucial applying (BP) is as a step towards solving a counting problem. Given a finite set A, the objective is to enumerate |A|, but unfortunately, the straightforward approach is often not easy. In the course of applying (BP), we look for a more familiar finite set B and try to establish a bijec-tion between these two sets. Once this is done, the harder problem of counting |A| is transformed to an easier problem (hopefully) of counting |B|. It does not matter how different the members in A and those in B are in nature. As long as there exists a bijection between them, we get |A| = |B| .

Exercise

5.1 (a) Find the number of positive divisors of n if

  (i) n = 31752;

 (ii)n = 55125.

(b) In general, given an integer n > 2, how do you find the number of positive divisors of n?

5.2 Find all positive integers that are divisible by 105 and have exactly 105 different positive divisors.

5.3 In each of the following cases, find the number of shortest P-Q routes in the grid below:

   (i) the routes must pass through A;

  (ii) the routes must pass through AB;

 (iii) the routes must pass through A and C;

(iv) the segment AB is deleted.

5.4 For each positive integer n, show that by establishing a bijection between and the set of n-digit binary sequences.

5.5 Let n and r be integers with 1 ≤ r ≤ n. Prove that by establishing a bijection between the set of r-element subsets of _n and the set of (n – r)-element subsets of _n.

5.6 The number 4 can be expressed as a sum of one or more positive integers, taking order into account, in the following 8 ways:

Show that every natural number n can be so expressed in 2^n-1 ways.

5.7 How many rectangles are there in the following 6 × 7 grid?

5.8 Find the number of parallelograms which are contained in the configuration below and which have no sides parallel to BC. (Hint: Adjoin a new row at the base of the triangle.)

5.9 If n points on the circumference of a circle are joined by straight lines in all possible ways and no three of these lines meet at a single point inside the circle, find

(i) the number of triangles formed with all vertices lying inside the circle;

(ii) the number of triangles formed with exactly two vertices inside the circle;

(iii) the number of triangles formed with exactly one vertex inside the circle;

(iv) the total number of triangles formed.