Discrete Math & Cryptographic Logic

Mastering Combinatorics: Order vs Selection

Combinatorics requires discerning whether order matters (Permutations $^nP_r$) or order is irrelevant (Combinations $^nC_r$). Master restriction strategies: the "Tie/Block" technique for adjacent items, the "Slot" technique for separated items, circular symmetry, and multi-condition committee selection.

1. Core Distinctions & Analytical Framework

Permutations $^nP_r$ (Pilihatur)

Order Matters

Used when sequencing, ranking, seating in rows, or forming numbers and words.

$^nP_r = \frac{n!}{(n-r)!}$
Identical items: $\frac{n!}{p! q! r!}$ • Circular: $(n-1)!$
Key Techniques:
  • "Always Together" (Tie Block): Bundle items as 1 single super-item. Count arrangements of items, then multiply by internal permutations inside the bundle.
  • "Never Together" (Slot Method): Arrange unrestricted items first, creating spaces/slots at both ends and in between. Place separated items into these slots using $^mP_k$.

Combinations $^nC_r$ (Gabungan)

Order Irrelevant

Used when picking teams, choosing questions, selecting lottery balls, or forming polygons.

$^nC_r = \frac{n!}{r!(n-r)!} = \frac{^nP_r}{r!}$
Symmetry: $^nC_r = {^nC_{n-r}} \qquad ^nC_0 = {^nC_n} = 1$
Key Techniques:
  • "At least / At most": Set up a table of mutually exclusive cases, calculate $^nC_r$ for each, then sum up the cases.
  • Geometry: From $n$ points (no 3 collinear), lines formed $= {^nC_2}$; triangles formed $= {^nC_3}$.

2. Progressive SPM Worked Examples with Marking Schemes

Example 1 • SPM Paper 1 Restrictions [5 Marks]

The 7 letters from the word K L U A N G S are to be arranged in a straight row without repetition.

(a) Find the number of different arrangements that begin with a vowel and end with a consonant. [2 marks]
(b) Find the number of arrangements in which the two vowels $U$ and $A$ are never adjacent. [3 marks]
Step-by-Step Marking Solution
(a) Begin with vowel, end with consonant:
Vowels: $\{U, A\}$ (2 letters). Consonants: $\{K, L, N, G, S\}$ (5 letters).
First position: 2 choices.
Last position: 5 choices.
Remaining 5 positions in the middle: $5!$ ways.
Total arrangements $= 2 \times 5! \times 5 = 2 \times 120 \times 5 = 1\,200$
[K1] $2 \times 5! \times 5$
[N1] $1\,200$
(b) Vowels $U$ and $A$ are never adjacent:
Method (Complementary subtraction):
Total unrestricted arrangements of 7 letters $= 7! = 5\,040$.
Arrangements where $U$ and $A$ ARE together (bundle $\{UA\}$ as 1 unit):
Units to arrange $= 5 \text{ consonants} + 1 \text{ bundle} = 6 \text{ units} \implies 6!$
Internal arrangements of $U$ and $A$ inside bundle $= 2!$
Together arrangements $= 6! \times 2! = 720 \times 2 = 1\,440$ [K1]
$\therefore$ Never adjacent $= 5\,040 - 1\,440 = 3\,600$
[K1] $6! \times 2!$
[K1] $7! - 1440$
[N1] $3\,600$
Example 2 • SPM Paper 2 Section A Committee [6 Marks]

A school robotics team consists of 6 boys and 5 girls. A delegation of 5 students is to be chosen to represent the school at an international innovation competition.

(a) Find the number of ways to form the delegation if it must contain at least 3 girls. [3 marks]
(b) Two specific students, Adam (boy) and Betty (girl), refuse to serve together in the same delegation. Find the number of ways to select the 5 delegates under this condition. [3 marks]
Step-by-Step Marking Solution
(a) At least 3 girls (delegation size = 5):
• Case 1 (3 Girls, 2 Boys): ${^5C_3} \times {^6C_2} = 10 \times 15 = 150$
• Case 2 (4 Girls, 1 Boy): ${^5C_4} \times {^6C_1} = 5 \times 6 = 30$
• Case 3 (5 Girls, 0 Boys): ${^5C_5} \times {^6C_0} = 1 \times 1 = 1$
Total ways $= 150 + 30 + 1 = 181$
[K1] case breakdown
[K1] combinations
[N1] $181$
(b) Adam and Betty refuse to serve together:
Total pool $= 6 + 5 = 11$ students.
Total unrestricted ways to pick 5 from 11 $= {^{11}C_5} = \frac{11 \times 10 \times 9 \times 8 \times 7}{5 \times 4 \times 3 \times 2 \times 1} = 462$. [K1]
Ways where BOTH Adam and Betty are chosen together:
Both are fixed in delegation, remaining 3 spots must be chosen from the other 9 students:
${^9C_3} = \frac{9 \times 8 \times 7}{3 \times 2 \times 1} = 84$ ways. [K1]
$\therefore$ Ways where they DO NOT serve together $= 462 - 84 = 378$.
[K1] ${^{11}C_5} = 462$
[K1] ${^9C_3} = 84$
[N1] $378$
Example 3 • KBAT Cybersecurity Passcode Architecture [5 Marks]

A financial banking app requires users to create a 6-character alphanumeric authorization code using the digits $\{2, 3, 4, 5, 7, 8, 9\}$ and the uppercase letters $\{A, B, C, D, E\}$.

The code must consist of exactly 4 distinct digits followed by 2 distinct letters.
(a) How many valid passcodes can be generated? [2 marks]
(b) If the code must represent an even number (determined by the last digit of the 4-digit sequence) and the 2 letters must both be vowels, find the number of possible passcodes. [3 marks]
(a) 7 digits available, choose and arrange 4: $^7P_4 = \frac{7!}{3!} = 840$.
5 letters available, choose and arrange 2: $^5P_2 = \frac{5!}{3!} = 20$.
Total valid passcodes $= {^7P_4} \times {^5P_2} = 840 \times 20 = 16\,800$.
[K1] ${^7P_4} \times {^5P_2}$
[N1] $16\,800$
(b) Restricted Even 4-Digit Block + 2 Vowels:
Available even digits: $\{2, 4, 8\}$ (3 choices for the 4th digit position).
Remaining 3 positions for digits can be filled from the remaining 6 digits: $^6P_3 = 6 \times 5 \times 4 = 120$.
Number of valid 4-digit even sequences $= 120 \times 3 = 360$. [K1]
Available vowels in $\{A, B, C, D, E\}$: $\{A, E\}$ (2 vowels).
Arranging 2 distinct vowels into the 2 letter positions $= 2! = 2$. [K1]
Total secure passcodes $= 360 \times 2 = 720$. [N1] 720