ACJC 2025 Permutations and Combinations Lecture Notes

1 8 PERMUTATIONS AND COMBINATIONS SYLLABUS ▪ Addition and multiplication principles for counting ▪ Concepts of permutation ( )! or n rnP and combination ( ) n rC ▪ Arrangements of objects in a line or in a circle, including cases involving repetition and restriction

ACJC 2025/26 H2 Mathematics (9758) 2 CONTENTS 1 Basic Principles of Counting ............................................................ 3 1.1 Addition Principle for Mutually Exclusive Situations ............ 3 1.2 Multiplication Principle for Successive Operations................ 3 2 Combination ..................................................................................... 5 2.1 Combination of r Objects Taken From n Distinct Objects ..... 6 2.2 Principle of Complementation ................................................ 7 3 Permutation of n Distinct Objects .................................................. 12 3.1 Permutation of n Distinct Objects in a Row ......................... 12 3.2 Relationship between Permutation and Combination ........... 13 3.3 Permutation of r Objects From n Distinct Objects (without Replacement) ....................................................................... 14 3.4 Permutation of r Objects From n Distinct Objects (with Replacement) ....................................................................... 17 4 Permutation of n Objects (Not All Distinct) .................................. 19 5 Permutation with Conditions .......................................................... 21 6 Circular Permutations .................................................................... 24 Annex: Practice Questions on Permutations and Combinations ...... 29

8 Permutations and Combinations 3 LECTURE 1 Lesson Outline • Basic Principles of Counting - Addition & multiplication principles for counting • Combination - Combination of r objects from n distinct objects - Principle of complementation 1 BASIC PRINCIPLES OF COUNTING 1.1 Addition Principle for Mutually Exclusive Situations If two operations are mutually exclusive (i.e. they cannot both be done at the same time) and one of them can be done in r ways and the other can be done in s ways, then one operation or the other can be done in r + s ways. This result can be extended to more than 2 operations. Example 1 A man travel by air or ship from Singapore to Tokyo. If there are 4 airlines and 3 shipping lines operating between the two cities, in how many ways can the man travel? Solution Rationale By the Addition Principle, No. of ways = 4 + 3 = 7 ways The man can either travel by air (4 ways) OR by sea (3 ways). ■ 1.2 Multiplication Principle for Successive Operations If there are r different ways of performing an operation, and after this operation is completed, a second operation can be performed in s different ways, then the two operations can be done one after the other in r  s ways.

ACJC 2025/26 H2 Mathematics (9758) 4 Example 2 There are 3 buses operating between Jurong and Clementi and 2 buses operating between Clementi and Bedok. How many different ways can a man travel from Jurong to Bedok via Clementi by bus? Solution Rationale By the Multiplication Principle, No. of ways = 3 x 2 = 6 ways The man can travel from Jurong to Bedok via Clementi using one of the 6 routes: J 1 → C 1 → B J 2 → C 1 → B J 3 → C 1 → B J 1 → C 2 → B J 2 → C 2 → B J 3 → C 2 → B ■ Extension of result This result can be extended to more than 2 operations. In general, if there are 1n ways of performing the first operation, 2n ways to perform a second operation, 3n ways to perform a third operation, ending with kn ways to perform the kth operation, then there are ( 1 2 3 ... kn n n n    ) ways of performing all the k operations in succession. Note This multiplication rule only applies when the operations are independent, i.e., the choice made for one operation does not affect the choice made for any of the other operations. 2 1 3 1 2 J C B

8 Permutations and Combinations 5 2 COMBINATION Definition A combination of a set of objects is a selection of objects where the order of selection does not matter. For example, we are interested in choosing 3 H2 subjects out of 5 subjects: Mathematics (M), Economics (E), Biology (B), Chemistry (C), History (H). How many possible subject combinations are there? Notice that we are not concerned with the order in which the subjects are selected. So there are a total of 10 combinations, namely, MEB, MEC, MEH, MBC, MBH, MCH, EBC, EBH, ECH, BCH In other words, the number of combinations of 3 subjects selected from 5 subjects = 5 3 10C = . More Examples Number of Selections Select combinations of 3 letters from the 4 letters A, B, C, D 4 3 4C = Select 3 students from a class of 25 for AC Games 25 3 2300C = Draw 3 balls from a bag containing 5 differently coloured balls 5 3 10C = From an ordinary pack of 52 cards, draw 2 diamonds 13 2 78C = From the letters O,R,A,N,G,E, select 2 vowels 3 2 3C = Note that in the above examples, we are not concerned with the order of items in the selection.

ACJC 2025/26 H2 Mathematics (9758) 6 2.1 Combination of r Objects Taken From n Distinct Objects Number of combinations of r objects taken from n distinct objects is given by ! ( )! ! n r nC n r r= − . To calculate the value of n rC , first key in the value of n, then press [ALPHA] [WINDOW (F2)] [8] and key in the value of r. Example 3 In how many ways can 5 basketball players be selected from a team of 12 players to participate in a friendly game (i) if there is no restriction? (ii) if the oldest has to be included? Solution Rationale (i) No. of ways of selecting 5 players (no restriction) = 12 5 792C = (ii) No. of ways of selecting 5 players (include oldest) = 11 4 330C = Excluding the oldest from the selection, we are left with 11 players to select 4. ■

8 Permutations and Combinations 7 Practice Question 1 In how many ways can a group of 4 boys be selected from 10 boys if (i) there is no restriction? (ii) the eldest boy is included in the group? (iii) the eldest boy is excluded in the group? Solution Rationale (i) No. of ways of selecting 4 boys from 10 boys (no restriction) = 10 4 210C = (ii) No. of ways of selecting 4 boys from 10 boys (include eldest) = 9 3 84C = Since the eldest boy has to be included in the group, we are left with 9 boys to choose 3. (iii) No. of ways of selecting 4 boys from 10 boys (exclude eldest) = 9 4 126C = Since the eldest boy has to be excluded, we are left with 9 boys to choose 4. ■ 2.2 Principle of Complementation If there are m ways for all the events to happen and n ways for event A to happen, then there are ()mn− ways for event A , the complement of A, to happen. Example 4 A delegation of 5 pupils is to be chosen from a class of 4 girls and 6 boys. Find the number of possible delegations if the delegation consists of (i) 3 girls and 2 boys; (ii) at least 1 girl. Solution Rationale (i) No. of delegations (3 girls and 2 boys) = 46 32 60CC= By the Multiplication Principle, No. of delegations (3 girls and 2 boys) = No. of ways of selecting 3 girls from 4  No. of ways of selecting 2 boys from 6

ACJC 2025/26 H2 Mathematics (9758) 8 (ii) Method 1 No. o f delegations (at least 1 girl) = 10 6 55 246CC−= Using Principle of Complementation, No. of delegations (at least 1 girl) = No. of delegations without restriction – No. of delegations with no girls Method 2 Case 1 (Exactly 1 girl): 46 14CC = 60 ways Case 2 (Exactly 2 girls): 46 23CC = 120 ways Case 3 (Exactly 3 girls): 46 32CC = 60 ways Case 4 (Exactly 4 girls): 46 41CC = 6 ways Total no. of delegations (at