EJC 2026 H3 Mathematics - Combinatorics 2: Principle of Inclusion and Exclusion - Notes and Tutorial

Eunoia Junior College 202 6 JC2 H3 Mathematics Page 1 of 15 1 The Principle of Inclusion and Exclusion (PIE) Recall that when the sets A and B are disjoint, A B A B = + (by the Addition Principle). However, when the sets A and B are not disjoint, how do we find the value of AB ? What if we have more than 2 sets? Principle of Inclusion and Exclusion (PIE) For 2 sets: A B A B A B = + −  If A and B are disjoint sets, then A B A B = + (AP) For 3 sets: ( )A B C A B C A B A C B C A B C  = + + −  +  +  +   Useful result For a real number r, the floor function  r denotes the greatest integer that is smaller than or equal to r. In general, for any two natural numbers n, k with kn , the number of integers in the set  1, 2, , n  which are divisible by k is given by n k   . H 3 M ATHEMATICS ( 9820 ) C OMBINATORICS 2 P RINCIPLE OF I NCLUSION AND E XCLUSION (PIE)

Eunoia Junior College 202 6 JC2 H3 Mathematics Page 2 of 15 Example 1 Find the number of integers from the set  1, 2, , 1000  which are divisible by 3 or 5. Let  1, 2, , 1000S = ,   is divisible by 3A x S x= , and   is divisible by 5B x S x= . Example 2 Find the number of positive divisors of at least one of the numbers 5400 and 18000. Let A = {x  ℕ: x is a divisor of 5400} and B = {x  ℕ: x is a divisor of 18000}.

Eunoia Junior College 202 6 JC2 H3 Mathematics Page 3 of 15 Example 3 (Self-Reading) The diagram below shows a 4 by 8 rectangular grid with two specified corners p and q and three specified segments uv, wx and yz. Find in the grid (i) the number of shortest p-q routes; (ii) the number of shortest p-q routes which pass through wx; (iii) the number of shortest p-q routes which pass through at least one of the segments uv, wx and yz; (iv) the number of shortest p-q routes which do not pass through any of the segments uv, wx and yz. (i) Number of shortest p-q routes is given by      =      + 4 12 4 84 = 495. (ii) As shown in the diagram below, a shortest p-q route passing through wx consists of a shortest p-w route (in a 2 by 3 grid), the segment wx and a shortest x-q route (in a 2 by 4 grid) . Thus, the number of shortest p-q routes passing through wx is given by            =      +      + 2 6 2 5 2 4212 32 = 150. (iii) Let A, B and C be the set of shortest p-q routes which pass through uv, wx and yz respectively. | A | = 1 2 3 5 3 8 1681 3 1 3 ++     ==           , q z y w x u v p

Eunoia Junior College 202 6 JC2 H3 Mathematics Page 4 of 15 | B | = 56 15022    =     (from (ii)), and | C | = 3 4 1 3 7 4 1403 1 3 1 ++     ==           . Next, we compute | A  B |, | A  C | and | B  C |. Observe that A  B is the set of shortest p-q routes passing through both uv and wx. Any such shortest p-q route consists of a shortest p-u route, the route uvwx and a shortest x-q route. Thus, | A  B | = 3 6 3 61 451 2 1 2         = =             . Likewise, we obtain | B  C | = 54 4021    =     . And each route in A  C consists of a shortest p-u route, the segment uv, a shortest v- y route, the segment yz and a shortest z-q route, which gives | A  C | = 361 4 2 3 1 3 =                  . Finally, we evaluate | A  B  C |. Each route in A  B  C is a p-q route consisting of a shortest p-u route, the route uvwxyz and a shortest z-q route. Thus, | A  B  C | = 121 4 1 3 =            . By (PIE), ( )A B C A B C A B A C B C A B C  = + + −  +  +  +   ( )168 150 140 45 36 40 12= + + − + + + 349= (iv) By (CP), (i) – (iii). i.e. 495 – 349 = 146 (see below for reason)  Let S be a set and A, B and C be subsets of S. Then S \ (A  B  C) = CBA  = CBA  )( = CBA  (by De Morgan’s Laws: ,A B A B A B A B =   =  ) = CBA  It follows that | CBA  | = | S \ (A  B  C) | = | S | − | A  B  C |. or | CBA  | = |S| − (|A| + |B| + |C|) + (|A  B| + |A  C| + |B  C|) − |A  B  C|

Eunoia Junior College 202 6 JC2 H3 Mathematics Page 5 of 15 Tip on when to use PIE A useful consideration on whether to apply PIE is to ask if the set A to be counted can be split into sets iA , 1,2, ,in=  , such that either 12 nA A A A=     or 12 ... nA A A A=    . Whether we choose the first or the second depends on whether it is easier to find the cardinality of the unions of Ai’s or the cardinality of the intersections of iA ’s. Example 4 (onto mappings) Let  1, 2, 3, 4, 5X = and  1, 2, 3Y = . (i) How many mappings are there from X to Y? (ii) How many onto mappings are there from X to Y? (i) Number of mappings from X to Y is given by 53 . (ii) Let S be the set of mappings from X to Y. Let A be the set of mappings from X to \1Y , B be the set of mappings from X to  \2Y , and C be the set of mappings from X to  \3Y . Then A is the set of mappings from X to Y which contain ‘1’ in Y as an image, B is the set of mappings from X to Y which contain ‘2’ in Y as an image, and C is the set of mappings from X to Y which contain ‘3’ in Y as an image. It follows that CBA  is the set of mappings from X to Y which contain ‘1’, ‘2’ and ‘3’ in Y as images; that is, CBA  is the set of onto mappings from X to Y. 53S = by (i). Since A is the set of mappings from {1, 2, 3, 4, 5} to {2, 3}, 52A = . Likewise, 52B = and 52C = . As A  B is the set of mappings from {1, 2, 3, 4, 5} to {3}, 511AB = = . Likewise, 1AC= and 1BC= . Finally, observe that A B C is the set of mappings from X to Y \ {1, 2, 3} (= ) Thus, A B C   = and so 0A B C  = . Thus, | CBA  | = |S| − (|A| + |B| + |C|) + (|A  B| + |A  C| + | B  C|) − |A  B  C| ( ) ( )5 5 5 53 2 2 2 1 1 1 0= − + + + + + − 150= 

Eunoia Junior College 202 6 JC2 H3 Mathematics Page 6 of 15 General Statement of the Principle of Inclusion and Exclusion From the PIE for 2 and 3 sets, we observe the following patterns on the right-hand sides of the identities. For the sum of the terms within the first grouping, we have: n Sum Number of terms in the sum 2 | A1 | + | A2 |      = 1 22 3 | A1 | + | A2 | + | A3 |      = 1 33 For the sum of terms within the second grouping, we have: n Sum Number of terms in the sum 2 | A1  A2 |      = 2 21 3 | A1  A2 | + | A1  A3 | + | A2  A3 |      = 2 33 For the sum of terms within the third grouping, we have: n Sum Number of terms in the sum 2 None 0 3 | A1  A2  A3 |      = 3 31 We also notice that the groupings alternate in sign, beginning with a (+) sign. Suppose now that we are given n finite sets: A1, A2, …, An. By generalizing the above observations, what identity would you expect for | A1  A2  …  An |? The first grouping should be the sum of nn =      1 terms, each involving a single set: | A1 | + | A2 | + … + | An |; or, in abbreviation,  = n i iA 1 || .

Eunoia Junior College 202 6 JC2 H3 Mathematics Page 7 of 15 The second grouping should be the sum of       2 n terms, each involving the intersection of two sets: | A1  A2 | + | A1  A3 | + … + | An−1  An |; in abbreviation,    ji ji AA || . The third grouping should be the sum of       3 n terms, each involving the intersection of three sets: | A1  A2  A3 | + | A1  A2  A4 | + … + | An−2  An−1  An |; in abbreviation,    kji kji AAA || . This pattern continues until the final, nth grouping with 1n n  = term involving the intersection of n sets. Bearing in mind that the groupings