EJC 2026 H3 Mathematics - Combinatorics 1: Bijection Principle - Notes and Tutorial

1 1 The Bijection Principle Let A and B be 2 sets and f: AB→ be a mapping. • f is injective (one to one) if ( ) ( )ff uv≠ in B for any 2 distinct elements u, v ( uv≠ ) in A. • f is surjective (onto) if for any b in B, there exists a in A such that ( )f ab= . • f is bijective (one to one correspondence) if it is both injective and surjective. Alternatively, f is bijective if there exists an injection from A to B and another injection from B to A. The Injection Principle Let A and B be 2 finite sets. If there is an injection from A to B, then AB≤ . The Bijection Principle Let A and B be 2 finite sets. If there is a bijection from A to B, then AB= . Example 1 (paths) A student wishes to walk from the corner X to the corner Y through streets as given in the street map shown below. Find the number of different shortest routes the student can take. Let A be the set of all the possible routes from X to Y. Define a mapping from A to the set B of all 9-digit binary sequences (containing 5 ‘0’s and 4 ‘1’s) where a horizontal segment maps to ‘0’ and ‘a vertical segment maps to ‘1’. Clearly, different shortest P-Q routes in A correspond to different sequences in B under f. Thus f is 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 ab= . Thus f is onto, and so is a bijection. 9! 5!4!AB= = or 9 5   or 9 4   .  H3 MATHEMATICS (9820) COMBINATORICS 1 BIJECTION PRINCIPLE P Q a = X Y

2 Example 2 (power set) The power set of a set S, denoted by P(S), is the set of all subsets of S, including S and the empty set φ. Thus, for n = {1, 2, …, n}, 1 ≤ n ≤ 3, we have P( 1 ) = {φ, {1}}, P( 2 ) = {φ, {1}, {2}, {1, 2}}, P( 3 ) = {φ, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}. We can construct a bijection between subsets of n and n-digit binary sequences. We set the kth digit of the sequence to be 1 if and only if k is in the subset. Example 3 (positive divisors of an integer) A positive integer k is a divisor of 31 26615 3 5 7=⋅⋅ if and only if 357abck =⋅⋅ for integers 0 3a≤≤ , 0 1b≤≤ , 0 2c≤≤ . Hence, there is a bijection between the positive integer divisors of 6615 (including 1 and itself) and the elements of the set ( ){ }, , : 0,1, 2,3; 0,1; 0,1, 2abc a b c = = = . So the total number of positive integer divisors of 6615 is 4 2 3 24⋅⋅= . We can use the same bijection to work out that, for example: • the number of positive integer divisors of 6615 that are not perfect squares is equal to • the sum of all positive integer divisors is equal to

3 Example 4 (chords and intersections of chords) Given 10 distinct points on a circle, (i) how many chords formed by these points are there? (ii) how many points of intersections of the chords in (i) lie within the circle if no 3 of the chords are concurrent within the circle? (i) Chords are uniquely defined by their endpoints and any pair of endpoints defines a chord. So there is a bijection between the set of chords and the set of pairs of points (where the order in each pair is unimportant). number of chords = number of pairs of points = 10 2   . (ii) We cannot simply count pairs of chords, because some chords do not intersect.

4 Example 5 (Counting rectangles) When counting the number of squares in a grid, say the 5-by-6 grid above, the usual method is to break the problem down by considering squares of each possible size, and use addition principle to obtain the total. When counting the number of rectangles, however, the number of possible sizes becomes quite large. Instead, we observe that each rectangle corresponds to a set of four lines, two horizontal and two vertical. Since different rectangles correspond to different sets, and every set of lines can be attributed to a rectangle, this is a bijection. Thus the total number of rectangles is

5 2 The Stars and Bars Model This extension of the “slotting” method from H2 Permutations and Combinations turns out to be very useful, as bijections can be drawn between it and a surprisingly large number of counting problems. (In fact, it is probably more accurate to say that H2 P&C teaches a very specific part of the Stars and Bars model, to cater to the specific counting scenarios present in H2.) Example 6 (Stars and Bars) Find the number of non-negative integer solutions to 12 5 ... 10xx x++ += . We can also frame this in a “distribution problem” context. The number of ways to distribute n identical objects into k distinct boxes is 11 1 nk nk kn +− +−  = −  . If, in addition we require that every box contains at least one object, then we require nk≥ and the number of ways is 11 1 nn k nk −−   =  −−   .

6 Example 7 John eats at least one apple a day. If he does that for 26 consecutive days, and the total number of apples that he eats is 45, show that there is a sequence of consecutive days that he eats 26 apples altogether how many ways can he eat the apples? Example 8 (2020/EJC/Prelim/Q3a) A shop sells doughnuts which comes in four flavours – vanilla, strawberry, chocolate, and banana. The shop has a large number of doughnuts of each flavour. (i) Mr. Lim wishes to buy a set of 12 doughnuts such that there is at least one doughnut of each flavour. In how many ways can he do this? [3] (ii) Mrs. Tan wishes to buy 12 doughnuts for her 4 children, where each child can get any number of doughnuts of any flavour, including none (subject to a total of 12 doughnuts). In how many ways can she do this? [3] (iii) Mr. Soh wishes to buy 2 doughnuts for each of 6 boys. In how many ways can he do this? [3]

7 There are other ways to read the arrangements of stars and bars. Example 9 Find the number of integer solutions to: (a) 1 0x = , 5 30x = , 1iix x+≤ for 1 ,2,3,4i= (b) 1 0x = , 30 5x = , 1iix x+≤ for 1,2,...,29i= (c) 1 0x = , 5 30x = , 1iix x+< for 1 ,2,3,4i= (d) 1 0x = , 5 30x ≤ , 1iix x+≤ for 1 ,2,3,4i= (e) 1 0x ≥ , 5 30x ≤ , 1iix x+≤ for 1 ,2,3,4i= (f) 1 0x ≥ , 30 5x ≤ , 1iix x+≤ for 1,2,...,29i=

8 3 Two More Bijection Tricks We are generally not expected to have prior knowledge of a large number of useful bijections; where an unfamiliar bijection is to be used, the question will usually contain guidance. We will only take a brief look at two further bijections. Young Diagram When we found the number of non- negative integer solutions to 12 5 ... 10xx x++ += , we considered (1,1,1,1, 6) and (6,1,1,1,1) to be two different solutions. However, sometimes we want to consider these to be the same, in other words “order does not matter”. This is called a partition. In terms of the distribution problem context, a partition arises from counting the number of ways to distribute n identical objects into k identical boxes. Example 10 Show that the number of partitions of 10 into at most 4 positive integer parts, is equal to the number of partitions of 10 into positive integer parts each no larger than 4. Note that partitions used to be in the H3 syllabus from 2017- 2024, but we are no longer expected to calculate partitions without guidance. More will be mentioned in Combinatorics 3.

9 Bijection leading to the Catalan Numbers The manipulation leading to this bijection is not easy to think of. Example 11 Middleton sits down at a game table with $1. Each game, if Middleton wins then she wins $1, if she loses then she loses $1. If at any time Middleton loses all her money, she cannot continue playing. Find the number of ways that, after 2n games have been played, Middleton has exactly $1, what she started with.

10 Exercises 1 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;