Mathematics Admissions Test (MAT) Combinatorics, Counting and Number Syllabus

How many ways can $r$ objects be chosen from $n$ with repetition allowed and order unimportant (stars and bars)?

$$\binom{n+r-1}{r}.$$ Equivalently the number of non-negative integer solutions of $x_1 + x_2 + \cdots + x_n = r$.

State the Fundamental Theorem of Arithmetic.

Every integer greater than $1$ can be written as a product of prime numbers, and this prime factorisation is unique up to the order of the factors.

If $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ is the prime factorisation, how many positive divisors does $n$ have?

$$d(n) = (a_1 + 1)(a_2 + 1)\cdots(a_k + 1).$$ Each exponent in a divisor independently ranges from $0$ to $a_i$.

For $n = p_1^{a_1}\cdots p_k^{a_k}$, what is the sum of all positive divisors of $n$?

$$\sigma(n) = \prod_{i=1}^{k} \frac{p_i^{a_i+1} - 1}{p_i - 1} = \prod_{i=1}^{k}\left(1 + p_i + p_i^2 + \cdots + p_i^{a_i}\right).$$

How do you compute the highest common factor (HCF/GCD) and lowest common multiple (LCM) from prime factorisations?

For each prime, take the minimum exponent appearing in both numbers for the HCF, and the maximum exponent for the LCM. Also $\gcd(a,b)\times \operatorname{lcm}(a,b) = a \times b$.

State the relationship between the GCD and LCM of two positive integers $a$ and $b$.

$$\gcd(a,b)\times \operatorname{lcm}(a,b) = ab.$$

What does it mean for two integers to be coprime (relatively prime)?

Two integers are coprime if their greatest common divisor is $1$, i.e. $\gcd(a,b)=1$; they share no common prime factor.

State the Division Algorithm for integers.

For integers $a$ and $b$ with $b > 0$, there exist unique integers $q$ (quotient) and $r$ (remainder) such that $a = bq + r$ with $0 \leq r < b$.

Define parity, and state the parity rules for sums and products.

Parity is whether an integer is even or odd. Sums: even+even=even, odd+odd=even, even+odd=odd. Products: a product is odd only if every factor is odd; it is even if any factor is even.

How can odd and even integers be written algebraically?

An even integer is $2k$ and an odd integer is $2k+1$ (or $2k-1$) for some integer $k$. This algebraic form is the standard tool for parity proofs.

State the divisibility rules for 2, 3, and 5.

Divisible by $2$: last digit is even. Divisible by $3$: digit sum is divisible by $3$. Divisible by $5$: last digit is $0$ or $5$.

State the divisibility rules for 4, 8, and 9.

Divisible by $4$: last two digits form a number divisible by $4$. Divisible by $8$: last three digits form a number divisible by $8$. Divisible by $9$: digit sum is divisible by $9$.

State the divisibility rule for 11.

An integer is divisible by $11$ if the alternating sum of its digits (e.g. $d_0 - d_1 + d_2 - \cdots$) is divisible by $11$ (including $0$).

How is a base-10 integer with digits $d_k d_{k-1}\cdots d_1 d_0$ expressed in terms of place value?

$$N = d_k 10^{k} + d_{k-1} 10^{k-1} + \cdots + d_1 10 + d_0,$$ where each $d_i \in \{0,1,\ldots,9\}$.

For a two-digit number with tens digit $a$ and units digit $b$, what is its value, and what is the value when its digits are reversed?

Original: $10a + b$. Reversed: $10b + a$. Their difference is $9(a-b)$, which is why such differences are always divisible by $9$.

Why is the difference between a number and the number formed by reversing its (two) digits always a multiple of 9?

$(10a+b) - (10b+a) = 9a - 9b = 9(a-b)$, an explicit multiple of $9$. More generally digit-reversal differences are multiples of $9$ because $10 \equiv 1 \pmod 9$.

How many $n$-digit positive integers are there (in base 10)?

$9 \times 10^{n-1}$. The leading digit has $9$ choices ($1$ to $9$, no leading zero) and each of the remaining $n-1$ digits has $10$ choices.

What is a systematic strategy for enumerating all cases without missing or repeating any?

Impose a fixed order (e.g. lexicographic or by increasing first element), split into exhaustive non-overlapping cases, list possibilities methodically within each case, and check the cases are disjoint and complete so totals can be added.

How many ways can a number be written as an ordered sum (composition) and how does this differ from a partition?

A composition counts ordered sums (order matters): $n$ has $2^{n-1}$ compositions. A partition counts unordered sums (order ignored), e.g. $4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1 = 4$, giving $5$ partitions.

Define a recurrence relation and give the recurrence and seed values for the Fibonacci sequence.

A recurrence defines each term using earlier terms. Fibonacci: $F_n = F_{n-1} + F_{n-2}$, with $F_1 = 1,\ F_2 = 1$ (so $1,1,2,3,5,8,13,\ldots$).

How many ways can you tile a $1 \times n$ strip using $1\times 1$ and $1\times 2$ tiles, and what recurrence governs it?

Let $T_n$ be the count. Then $T_n = T_{n-1} + T_{n-2}$ (last tile is a single or a domino), with $T_1 = 1, T_2 = 2$. This gives Fibonacci numbers.

How many ways can you climb a staircase of $n$ steps taking $1$ or $2$ steps at a time?

It satisfies $a_n = a_{n-1} + a_{n-2}$ with $a_1 = 1,\ a_2 = 2$, giving Fibonacci numbers; $a_n = F_{n+1}$.

What is the standard method for solving a counting problem with a recursive structure?

Define a sequence $a_n$ for the count at size $n$, find a recurrence by conditioning on the last/first choice, establish base cases, then iterate or solve the recurrence to obtain $a_n$.

State the Pigeonhole Principle (simple form).

If $n+1$ or more objects are placed into $n$ boxes, then at least one box contains at least two objects. More generally, you cannot place $n$ items into fewer than $n$ boxes with all boxes holding at most one item.

State the Generalised Pigeonhole Principle.

If $N$ objects are placed into $k$ boxes, then at least one box contains at least $\left\lceil \dfrac{N}{k} \right\rceil$ objects.

Using pigeonhole: among any group of how many people must at least two share a birthday month, and why?

$13$ people. There are $12$ months (boxes); with $13$ people (objects) and $13 > 12$, by the pigeonhole principle at least two must share a month.

What is the Extremal Principle in combinatorial arguments?

Consider an object that is extreme in some sense — the largest, smallest, first, longest, etc. — and use its extremal property to derive a contradiction or force a conclusion. It often pairs with infinite descent or pigeonhole.

What is the complementary counting technique and when is it useful?

Count the complement: number of ways with property $=$ (total) $-$ (number of ways without it). It is useful when the 'bad' or excluded cases are far easier to count than the desired ones (e.g. 'at least one' problems).

Show why the number of ways to arrange $n$ people in a row so that two specific people are together is $2 \times (n-1)!$.

Glue the two specific people into a single block: there are $(n-1)!$ arrangements of the $n-1$ items (block plus others), and the two people can be ordered within the block in $2! = 2$ ways, giving $2(n-1)!$.

How many diagonals does a convex polygon with $n$ vertices have?

$$\binom{n}{2} - n = \frac{n(n-3)}{2}.$$ Each pair of vertices gives a segment ($\binom{n}{2}$), minus the $n$ sides leaves the diagonals.