Experts have designed these NCERT Class 9 Advanced Maths Solutions and Class 9 Advanced Maths Chapter 5 Combinatorics Notes for effective learning.
Combinatorics Notes Class 9 Advanced Maths
Introduction
At times, counting can become complicated. For example, how would someone go about creating every possible password for their mobile phone? What about arranging students in different seating positions or choosing players to form a team? If you had to list every possible outcome by hand, it would take far too long.
This section introduces common counting techniques called “permutations” and “combinations.” These methods simplify the process of counting possible outcomes and are widely used in everyday life, mathematics and computer science.
Brief History of Combinatorics
The earliest recorded combinatorial work appears in ancient Indian texts. The Sanskrit grammarian Pingala (c. 3rd century BCE) studied combinations of syllables in his work Chandahsastra.
Blaise Pascal (1623-1662) constructed Pascal’s Triangle, which represents combinatorial numbers (combinations).
Gottfried Wilhelm Leibniz (1646-1716) wrote Dissertatio de Arte Combinatoria, laying important foundations for combinatorial mathematics.
In the modern era, combinatorics is central to computer algorithms, network design and artificial intelligence.
Fundamental Principle of Counting and Tree Diagram Method
The Fundamental Principle of Counting (Fpc)
The Fundamental Principle of Counting is the cornerstone rule for counting outcomes across multiple independent decisions.
(a) The Rule of Multiplication (The AND’ Rule):
If one task can be done in m ways AND a second task can be done in n ways, then both tasks together can be done in m × n ways.
Total ways = m × n
Keyword signal: ‘AND’, ‘then’, ‘followed by’, ‘also’ — these indicate multiplication.
(b) The Rule of Addition (The ‘OR’ Rule):
If one task can be done in m ways OR a second (different/ alternative) task can be done in n ways, then the total number of ways is m + n.
Total ways = m + n
Keyword signal: ‘OR’, ‘either … or’, ‘alternatively’ — these indicate addition.
Fundamentals:
If one event can happen in m ways and another independent event can happen in n ways, then the two events together can happen in m × n ways. It is used to count total possible outcomes efficiently.
Visualising the Principle: The Tree Diagram
A tree diagram is a branching visual tool used to list all possible outcomes when counting is done in stages.
- Each branch represents one possible choice at that stage.
- Multiply the number of branches at each level to obtain the total number of outcomes.
- Tree diagrams are particularly helpful when the number of choices is small.
Example — Choosing an outfit (2 shirts: S1, S2 and 3 trousers: T1, T2, T3):
Fundamentals:
A tree diagram visually shows all possible outcomes of a sequence of events using branches. Each branch represents a choice, and the total number of final branches equals the total outcomes.
Example: A restaurant offers 3 types of starters (Soup, Salad, Spring Roll) and 4 types of main course (Pizza, Pasta, Burger, Rice Bowl).
(i) How many different complete meals (starter + main course) can a customer order?
(ii) If a customer chooses ONLY a starter OR ONLY a main course, how many choices do they have?
Solution:
(i) Using the AND rule (starter AND main course):
3 × 4 = 12 different meals
(ii) Using the OR rule (starter OR main course — mutually exclusive):
3 + 4 = 7 choices
Example 2:
A code consists of 3 letters followed by 3 digits. Letters can be A-Z (26 options) and digits can be 0-9 (10 options). Repetition is allowed. How many differ¬ent codes are possible?
Solution:
Stage 1: Choose 1st letter → 26 ways
Stage 2: Choose 2nd letter → 26 ways
Stage 3: Choose 3rd letter → 26 ways
Stage 4: Choose 1st digit → 10 ways
Stage 5: Choose 2nd digit → 10 ways
Stage 6: Choose 3rd digit → 10 ways
Possible ways = 26 × 26 × 26 × 10 × 10 × 10
= 263 × 103
= 17,576 × 1000
= 1,75,76,000
Example 1:
A mobile phone PIN has 6 digits. Each digit can be 0 – 9.
(i) How many possible PINs exist?
(ii) If the first digit cannot be 0, how many PINs are ; possible?
(iii) If no digit can be repeated, how many PINs are j : possible?
Solution:
(i) Each of 6 positions: 10 choices
10 × 10 × 10 × 10 × 10 × 10 = 106
= 10,00,000
(ii) First digit: 9 choices (1 – 9); remaining 5 digits: 10 ; :: choices each
9 × 105 = 9,00,000
(iii) First digit: 10 choices; second: 9 choices; third: 8 choices; fourth: 7 choices; fifth: 6 choices; sixth: 5 choices
10 × 9 × 8 × 7 × 6 × 5 = 1,51,200
Example 2:
A cafe offers:
- 2 types of drinks: Tea, Coffee
- 3 types of snacks: Sandwich, Muffin, Cookies
A customer wants to choose one drink and one snack for breakfast.
In how many different ways can the customer choose the breakfast combo?
Solution:
Here, the choice of drink and the choice of snack are independent events. Choosing a complete breakfast requires selecting one item from each category.
This can be illustrated using a tree diagram
Breakfast Combo Selection Tree Diagram
Total Combinations = 2 Drinks × 3 Snacks = 6 Ways
Possible breakfast combinations are:
- (Tea, Sandwich)
- (Tea, Muffin)
- (Tea, Cookies)
- (Coffee, Sandwich)
- (Coffee, Muffin)
- (Coffee, Cookies)
By counting the endpoints of the tree, we see there are exactly 6 unique breakfast combinations.
Instead of drawing a tree diagram for larger problems, we can use the Fundamental Principle of Counting:
2 (drinks) × 3 (snacks) = 6
Therefore, the customer can choose the breakfast combo in 6 different ways.
Factorials, Permutations and Combinations
Factorials
The factorial of a positive integer n (written w!) is the product of all positive integers from 1 to n.
n! = n × (n – 1) × (n – 2) × … × 2 × 1
Special case: 0! = 1 (by definition).
Factorials grow extremely fast. For example, 10! = 36,28,800 and 20! (≈2.43 × 1018) is over 2 quintillion (1 quintillion = 108).
| n | n!(value) |
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 6 |
| 4 | 24 |
| 5 | 120 |
| 6 | 720 |
| 7 | 5,040 |
| 10 | 36,28,800 |
Factorial Simplification Tip: Cancel common factors before multiplying.
Fundamentals:
A factorial represents the product of all positive j integers from 1 up to a number n.
n! = n(n – 1 )(n – 2) 3.2.1
Factorials are used in counting arrangements and selections.
Permutations: When order Matters
A permutation is an arrangement of objects where the order matters.
Consider permutations when you need to arrange, sequence, rank or assign positions.
Example: The words CAT, ACT and TAC are three different arrangements (permutations) of the same three letters.
Example: A 3-digit PIN code: 4-1-2 is different from 2-1-4, so order matters.
Memory Hook: P = Position Matters | ‘Permutation’ → ‘Position’
The Permutation Formula
The number of ways to arrange r objects chosen from n distinct objects (where order matters) is:
P(n, r) = \(\frac{n!}{(n-r)!}\)
Where: n = total number of distinct objects available,
r = number of objects being arranged.
Special case: When all n objects are arranged (r = n): P(n, n) = n!
Fundamentals:
A permutation is an arrangement where order matters, Different orders of the same objects are counted as different arrangements.
Example: How many 3-letter arrangements can be made from 5 different letters?
Solution:
P(5, 3) = \(\frac{5!}{(5-3)!}\)
= \(\frac{5!}{2!}=\frac{5 \times 4 \times 3 \times 2!}{2!}\)
= 5 × 4 × 3 = 60
Combinations: When order does not Matter
A combination is a selection of objects where the order does NOT matter. Only the group or set chosen matters, not the sequence.
Example: Choosing 3 students for a committee from 10 — the group A, B, C is the same as {C, A, B}. Example: Selecting 2 toppings from a pizza menu — {cheese, olives} is the Combinations same selection as {olives, cheese}.
Memory Hook: C = Choose without caring about order | ‘Com-bination’ → ‘Com-mittee’
The Combination Formula: The number of ways to choose r objects from n distinct objects (where order does not matter) is:
C(n, r) = \(\frac{n!}{r!\times(n-r)!}\)
Notice: C(n, r) = \(\frac{P(n, r)}{r!}\)
(We divide by r! because order does not matter.)
Fundamentals:
A combination is a selection where order does not matter. Different orders of the same objects are treated as the same selection.
Example: How many ways can a team of 3 be chosen from 5 players?
Solution:
C(5, 3) = \(\frac{5!}{3!\times(5-3)!}\)
= \(\frac{(5!)}{3!\times 2!}\)
= \(\frac{120}{6 \times 2}=\frac{120}{12}\)
= 10
Permutation vs Combination — Key Comparison
| Permutation (Order Matters) | Combination (Order Does NOT Matter) |
| Arrangement/sequence/rank | Selection/group/committee |
| P(n, r) = \(\frac{n!}{(n-r)!}\) | C(n, r) = \(\frac{n!}{r!(n-r)!}\) |
| CAT ≠ ACT ≠ TAC | A, B, C = C, A, B |
| PIN codes, race rankings, passwords | Lottery tickets, teams, pizza toppings |
| More arrangements (larger number) | Fewer selections (smaller number) |
Combinatorics in the Modern World
Cybersecurity: Password Safety
Password security directly depends on combinatorics. The strength of a password is measured by the number of possible combinations an attacker must try.
- A 4-digit numeric PIN (digits 0-9, repetition allowed): 10 × 10 × 10 × 10 = 10,000 combinations.
- A 6-character password using 26 lowercase letters, 26 uppercase letters, 10 digits: 626 ≈ 56 billion combinations.
- Adding special characters (!@#%…) increases this to trillions.
This is why cybersecurity experts recommend long, complex passwords — combinatorics makes ‘them exponentially harder to crack.
Data Processing and Task Scheduling
In computing, combinatorics governs how tasks are scheduled, how data is routed through networks and how algorithms are optimised.
- Scheduling n jobs on a single machine: There are n! possible orderings to evaluate.
- Choosing k servers from n available for a distributed task involves combinations and is given by C(n, k).
- In database systems, selecting and ordering r tables from n available tables can be modelled as a permutation problem and is given by P(n, r).
Example: How many ways can 5 books be arranged on a shelf?
Solution:
Arranging all 5 books in order:
P(5, 5) = \(\frac{5!}{(5-5)!}\)
= \(\frac{120}{0!}\)
= \(\frac{120}{0}\)
= 120
Example: From a class of 10 students, a teacher wants to form a committee of 4. In how many ways can this be done?
Solution:
A committee has no ranks — being on the committee is the same regardless of selection order.
Therefore, use Combination: C(10, 4)
Write the formula:
C(10, 4) = \(\frac{10!}{4!\times(10-4)!}\)
= \(\frac{10!}{4!\times 6!}\)
= \(\frac{10 \times 9 \times 8 \times 7 \times 6!}{4 \times 3 \times 2 \times 1 \times 6!}\)
= \(\frac{10 \times 9 \times 8 \times 7}{4 \times 3 \times 2 \times 1}\)
= \(\frac{5040}{24}\) = 210
There are 210 different committees possible.
Example 1:
Cybersecurity — Password Strength:
A website requires a password of exactly 3 characters chosen from a set of 10 special symbols (no repetition, order does not matter for storage in a hash). How many distinct character combinations are possible?
Solution:
No repetition, order does not matter (combination):
C(10, 3) = \(\frac{10!}{3!\times 7!}\)
C(10, 3) = \(\frac{10 \times 9 \times 8}{3 \times 2 \times 1}\)
=\(\frac{720}{6}\)
= 120
Security Insight: If order had mattered (permutation), P(10, 3) = 720 — six times more arrangements. Password systems that are case-sensitive and position- sensitive benefit from permutation-level security.
Example 2:
Data Processing — Task Scheduling:
A data centre has 12 available processing units. A software task requires exactly 4 units to run simulta-neously. The company needs to select which 4 units will handle the task. How many different selections are possible? Would the answer change if the 4 units were assigned specific roles (Unit A = primary, Unit B = backup, etc.)?
Solution:
Part 1 — Selection only (combination, no roles):
C(12, 4) = \(\frac{12!}{4!\times 8!}\)
= \(\frac{12 \times 11 \times 10 \times 9}{4 \times 3 \times 2 \times 1}\)
= \(\frac{11,880}{24}\) = 495
= 495
Hence, 495 selections are possible.
With specific roles assigned (permutation):
P(12, 4) = \(\frac{12!}{8!}\) = 12 × 11 × 10 × 9 = 11,880
Permutation gives 11,880 — 24 times more than : combination (because 4! = 24).
If roles don’t matter → C(12, 4) = 495. If roles differ → P(12, 4) = 11,880. The correct model depends entirely on whether assignment order carries meaning.