Tutorial 5: Combinatorics and Graphs

How to submit:

• Submit before actual tutorial time for it to be graded. There are 2 ways to do this:
  1. There is a submission box on Canvas for you to submit your document. Either .docx, .pdf, or a picture of your written solutions are acceptable as long as we can read your attempts.
  2. Submit your written attempts in-person during our tutorial.

• Official due date for submission: 31 Mar 2026, 11:59 PM or during tutorial itself.

Collaboration Policy:

• You may discuss high-level ideas with your classmates or friends. You should list your collaborators if you do so.
• Do not share your solutions.
• ChatGPT (and other LLMs) are not allowed.
• Your submission must be of your own write-up.

Late Policy:

• < 1 week after submission deadline: 50% penalty
• < 2 weeks after submission deadline: 75% penalty
• No submissions after 2 weeks.

Overview

This tutorial gives practice questions to be discussed during the relevant tutorial in person. This particular tutorial sheet corresponds to Unit 6 and Unit 7. It is recommended to either watch the lectures or read the notes for each respective parts before attempting the tutorial sheet.

1. Questions 1 and 2 are related to combinatorics.
2. Questions 3 through 6 are related to graph theory.
3. Question 8 is related to the pigeonhole principle.

After Week 9’s content, you should be able to attempt questions 1 and 2. After Week 10’s content, you should be able to attempt questions 2 through 7.

Questions 1 and 5 are graded for participation.

That said, we encourage you to try all the questions. This way, when you come for tutorials we can make the best use of your time since you can either verify your solutions, or understand the discussions when our tutors go through the solutions.

---

Question 1 [Graded for Participation]:

Let’s say that we want to build a password system that only accepts:

1. Lowercase letters ($\text{a}$-$\text{z}$); there are $26$ possible choices
2. Uppercase letters ($\text{A}$-$\text{Z}$); there are $26$ possible choices
3. Numbers ($0$-$9$); there are $10$ possible choices

We are going to try to count how many possible passwords there are, depending on different rules that the system will allow.

Sub-part 1

Let’s say the password system says:

Any password must be of length $\ge 8$ and $\le 32$.

If this is the only requirement, how many possible passwords are there? You need not compute the actual value, you can leave your answer in the form of a summation if need be.

Sub-part 2

Let’s say the password system says:

Any password (i) must be of length $\ge 8$ and $\le 32$, and (ii) must be alphanumeric (i.e., contain at least one uppercase or lowercase letter, and at least one number).

If this is the requirement, how many possible passwords are there? You need not compute the actual value, you can leave your answer in the form of a summation if need be.

Hint: Can we make use of ideas from this section somehow?

Sub-part 3

Let’s say the password system says:

Any password (i) must be of length exactly $8$, and (ii) must alternate numbers and letters.

Hence, passwords like "$\text{a1b2c3d4}$" or "$\text{1m9j8s7h}$" are allowed, but not "$\text{aa1b3d0p}$", because there are two adjacent "$\text{a}$"s.

If this is the requirement, how many possible passwords are there? You need not compute the actual value, you can leave your answer in the form of a summation if need be.

Sub-part 4

Let’s say the password system says:

Any password (i) must be of length exactly $8$, and (ii) must not repeat any numbers or letters.

Hence, passwords like "$\text{a1b2c3d4}$" or "$\text{1m9j8s7h}$" are allowed, but not "$\text{a1b3d0pa}$", because the letter "$\text{a}$" has been repeated.

If this is the requirement, how many possible passwords are there? You need not compute the actual value, you can leave your answer in the form of a summation if need be.

Sub-part 5

Let’s say the password system says:

Any password (i) must be of length exactly $8$, (ii) must be alphabetical, (iii) the password letters must be sorted, and (iv) each letter must only appear once.

Hence, passwords like "$\text{adgkwxyz}$" or "$\text{abcdefgh}$" are allowed, but not "$\text{bajoweaz}$".

If this is the requirement, how many possible passwords are there? You need not compute the actual value, you can leave your answer in the form of a summation if need be.

---

Question 2:

Sub-part 1

Let’s say we wanted to arrange $5$ people around a table. How many possible ways are there for us to arrange them? In general, how many possible ways are there for us to arrange $n$ people?

To be clear, if we had $5$ people, then it doesn’t matter where they sit, only the relative ordering matters.

Sub-part 2

Again let’s say we wanted to arrange $5$ people around a table, but an arrangement and its anti-clockwise arrangement are considered the same. How many arrangements do we have now?

---

Question 3:

Among a group of $7$ people, is it possible that every person is friends with exactly only $2$ other people? Is it possible that every person is friends with exactly $5$ other people?

---

Question 4:

Given a graph $G=(V,E)$ that has $|E|=t$ edges, how many edges does $\bar{G}$ have?

---

Question 5 [Graded for Participation]:

Given a graph $G$ that is a full $k$-ary tree of height $h$. How many nodes does it have? How many edges does it have? How many leaves does it have?

---

Question 6:

Given a complete graph $G$ on $n$ nodes, how many cycles can we possibly make (assuming that clockwise and anticlockwise cycles are considered the same)?

---

Question 7:

Let’s say that there was a tournament with $n$ teams. A match happens when $2$ different teams play against each other (a team cannot play against itself). This means a team can participate in any number of matches from $0$ to $n-1$ inclusive.

Show that there will always be two teams that have played the same number of matches.