MA2011 / MA2211 — Discrete Mathematics Week 8

Week 8

Counting & Combinatorics

MA2011 Discrete Mathematics for Computing | MA2211 Discrete Mathematics

8.1 Basic Counting 8.2 Permutations & Combinations 8.3 Complex Problems 8.4 Probability

Our running scenario today: Organising the JCU Hackathon 🏆

MA2011 / MA2211 8.1 Basic Counting

What is Combinatorics?

Combinatorics

Combinatorics is the branch of mathematics that counts, arranges, and selects objects from finite sets. The big question is always: "How many ways can we do this?"

🏆 Hackathon Scenario

Running Example

The JCU Hackathon has 30 students registering. We need to:
• Assign them to rooms — how many can fit?
• Pick a team of 5 — how many possible teams?
• Award Gold / Silver / Bronze — in how many orders?

Combinatorics uses precise counting techniques, not guessing or listing everything.
Unlike arithmetic, problems in combinatorics can look simple but require creative thinking.
Tools we'll learn: Multiplicative Principle, Pigeonhole, Inclusion-Exclusion, P(n,r), C(n,r)

MA2011 / MA2211 8.1 Basic Counting

The Multiplicative Principle

Multiplicative Principle

If task 1 can be done in m ways, and for each of those, task 2 can be done in n ways, then both tasks together can be done in m × n ways.

🏆 Hackathon: Designing Team T-Shirts

Example

Hackathon T-shirts come in 4 colours (Red, Blue, Green, Black) and 3 sizes (S, M, L).
How many distinct T-shirt options are there?

4 colours × 3 sizes = 12 options

Think of it as a grid:

	S	M	L
Red	R-S	R-M	R-L
Blue	B-S	B-M	B-L
Green	G-S	G-M	G-L
Black	K-S	K-M	K-L

Key Idea

Each extra independent choice multiplies the total. Three independent choices of sizes a, b, c gives a × b × c outcomes.

MA2011 / MA2211 8.1 Basic Counting

The Pigeonhole Principle

Pigeonhole Principle

If n + 1 or more objects are placed into n containers, then at least one container holds 2 or more objects.

🏆 Hackathon: Assigning Rooms

The hackathon has 3 rooms (Lab A, Lab B, Seminar). 13 students arrive — by the pigeonhole principle, at least one room must hold at least 5 students.

🧑‍💻Lab A

🧑‍💻Lab B

🧑‍💻Seminar

General Form

If n items go into k containers, at least one container holds at least ⌈n/k⌉ items.

MA2011 / MA2211 8.1 Basic Counting

Inclusion-Exclusion Principle

Inclusion-Exclusion (2 sets)

|A ∪ B| = |A| + |B| − |A ∩ B|

🏆 Hackathon: Skill Survey

Problem

Of 30 students surveyed:
• 18 know Python
• 12 know JavaScript
• 7 know both

How many know Python or JavaScript (or both)?

18 + 12 − 7 = 23

Why subtract the overlap?

Adding |A| + |B| counts students in both groups twice. We correct this by subtracting |A ∩ B| once.

MA2011 / MA2211 Quick Check

Quick Check — Basic Counting

Question 1

At the hackathon, lunch has 3 choices of main, 4 choices of drink, and 2 choices of dessert. How many different lunch combinations are there?

Question 2

35 students must be assigned to 6 project themes. Can we guarantee that at least one theme gets 6 or more students?

MA2011 / MA2211 8.2 Permutations & Combinations

Permutations — Order Matters

Permutation

A permutation is an ordered arrangement. The number of ways to arrange r objects chosen from n distinct objects is:

P(n, r) = n! / (n − r)! = n × (n−1) × … × (n−r+1)

🏆 Hackathon: Awards Ceremony

Example

10 teams compete. We award Gold 🥇, Silver 🥈, Bronze 🥉.
Order matters — 1st ≠ 2nd.

P(10, 3) = 10 × 9 × 8 = 720

1Gold: 10 choices
2Silver: 9 remaining
3Bronze: 8 remaining

10 × 9 × 8 = 720

When do you use P(n,r)?

Use permutations when order matters: rankings, arranging in a row, assigning distinct roles to people.

MA2011 / MA2211 8.2 Permutations & Combinations

Combinations — Order Doesn't Matter

Combination

A combination is an unordered selection. The number of ways to choose r objects from n distinct objects is:

C(n, r) = n! / (r! × (n − r)!) = "n choose r"

🏆 Hackathon: Selecting a Committee

Example

Choose 5 judges from 30 registered participants. A committee has no "first judge" or "second judge" — order doesn't matter.

C(30, 5) = 30! / (5! × 25!)
= 142,506 ways

Key insight: permutations over-count by the number of ways to reorder the chosen group:

C(n,r) = P(n,r) / r!

Dividing by r! removes all orderings of the same selection.

P vs C — The Key Question

Ask yourself: "Does swapping two chosen items give a different result?" If YES → permutation. If NO → combination.

MA2011 / MA2211 8.2 Pascal & Binomial

Pascal's Identity & the Binomial Theorem

Pascal's Identity

C(n+1, r) = C(n, r−1) + C(n, r)

Choosing from n+1 objects = include the new object or don't.

n\r	0	1	2	3
0	1
1	1	1
2	1	2	1
3	1	3	3	1

Binomial Theorem

(x + y)ⁿ = Σ C(n,k) xᵏ yⁿ⁻ᵏ
for k = 0 to n

Example (n=3)

(x+y)³ = x³ + 3x²y + 3xy² + y³
Coefficients: 1, 3, 3, 1 — row 3 of Pascal's triangle!

🏆 Hackathon: Subsets of judges

Total subsets of 3 judges from a group = 2³ = 8. Setting x=y=1 in the binomial theorem gives Σ C(3,k) = 2³.

MA2011 / MA2211 Quick Check

Quick Check — Permutations & Combinations

Question 3

The hackathon shortlists 8 teams. We need to pick a 3-person group for a 'best presentation' showcase — teams just appear together, no ranking. How many ways?

Question 4

A 4-digit PIN for the hackathon WiFi uses digits 0–9, no repetition. How many PINs are possible?

MA2011 / MA2211 8.3 Complex Problems

Tackling Complex Counting Problems

There's no single formula — you need a strategy.

1Read carefully. What exactly is being counted? What are the constraints?
2Identify the type. Does order matter? Are repetitions allowed? Are there restrictions?
3Break it down. Use the multiplicative principle to split into independent stages.
4Count, then check. Try small examples first to verify your formula.

🏆 Complex Hackathon Problem

Example: Forming teams with constraints

Form a 4-person team from 30 students where exactly 2 must be Computing students (there are 12 Computing students, 18 others).

Stage 1: Choose 2 from 12 Computing: C(12, 2) = 66
Stage 2: Choose 2 from 18 others: C(18, 2) = 153
Total: 66 × 153 = 10,098 teams

MA2011 / MA2211 8.4 Simple Probability

Combinatorics & Probability

Equally Likely Outcomes

If all outcomes are equally likely: P(event) = (# favourable outcomes) / (# total outcomes)

🏆 Hackathon Prize Draw

Example 1

30 students enter a draw for 1 prize. What is the probability a Computing student wins? (12 are Computing)

P = 12/30 = 2/5 = 0.4

Example 2

A 3-person team is randomly drawn from all 30. What is the probability that all 3 are Computing students?

P = C(12,3) / C(30,3)
= 220 / 4060 ≈ 0.054

Connection to Counting

Probability with equally likely outcomes reduces to a counting problem. Master 8.1–8.3 and probability follows naturally.

MA2011 / MA2211 Week 8 — Summary

Week 8 Summary

8.1 Basic Counting

Multiplicative: independent choices → multiply

Pigeonhole: n+1 items, n boxes → share

Inclusion-Exclusion: |A∪B| = |A|+|B|−|A∩B|

8.2 Permutations & Combinations

P(n,r): ordered, no repeat
= n!/(n−r)!

C(n,r): unordered, no repeat
= n!/(r!(n−r)!)

Pascal's / Binomial

8.3 & 8.4

Complex: break into stages, multiply

Probability:
P = favourable / total

Always ask: does order matter?

🏆 Our Hackathon Journey

T-shirt options (multiplicative) → Room assignment (pigeonhole) → Skill overlap (inclusion-exclusion) → Awards (permutation) → Committee (combination) → Prize probability — all from one event!

📋 Coming up: Online Quiz 8 (Nov-20) · Graded Problem Sheet 4 (Nov-26)