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

Combinatorics, Counting and Number syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Combinatorics, Counting and Number in Mathematics Admissions Test (MAT), not a summary of it.

1. 1

   Counting Principles

   3 topics

   • Addition and Multiplication Principles
     • Counting choices in sequence and in alternatives
     • Counting with simple restrictions
   • Permutations and Arrangements
     • Ordered arrangements of distinct objects
     • Arrangements with repeated objects or constraints
   • Combinations and Binomial Coefficients
     • Choosing subsets and the n-choose-r notation
     • Link between combinations and the binomial expansion
2. 2

   Number and Divisibility

   3 topics

   • Integers, Factors and Multiples
     • Prime factorisation and counting divisors
     • Highest common factor and lowest common multiple
   • Parity and Divisibility Arguments
     • Using odd and even in proofs
     • Simple modular reasoning about remainders
   • Digit and Place-Value Problems
     • Reasoning about decimal representations and digit sums
3. 3

   Combinatorial Problem Solving

   3 topics

   • Systematic Enumeration
     • Casework and avoiding double counting
     • Counting paths on a grid
   • Recursive Counting
     • Setting up a recurrence for a counting problem
     • Counting tilings and arrangements via recursion
   • Pigeonhole and Extremal Reasoning
     • Guaranteeing an outcome by the pigeonhole principle

Combinatorics, Counting and Number flashcards for Mathematics Admissions Test (MAT)

18 of 50 cards from the Combinatorics, Counting and Number deck — real questions with worked answers.

1. State the Addition Principle (rule of sum) for counting.

   If a task can be done in one of two mutually exclusive ways, with $m$ options of the first type and $n$ of the second type (no overlap), then the total number of ways is $m + n$. For disjoint sets, $|A \cup B| = |A| + |B|$.

2. State the Multiplication Principle (rule of product) for counting.

   If a process consists of a sequence of independent stages with $n_1$ choices at the first, $n_2$ at the second, ..., $n_k$ at the $k$-th, then the total number of outcomes is $n_1 \times n_2 \times \cdots \times n_k$.

3. When do you use the addition principle versus the multiplication principle?

   Use addition when counting alternatives (this case OR that case, mutually exclusive). Use multiplication when counting a sequence of choices made together (this AND then that). 'OR' suggests $+$; 'AND/then' suggests $\times$.

4. How many ways can you choose one item from a set of $m$ AND one item from a separate set of $n$? How many ways to choose just one item from either set (disjoint)?

   One from each (a pair): $m \times n$ by the multiplication principle. One item total from either set: $m + n$ by the addition principle.

5. State the Inclusion-Exclusion Principle for two sets.

   $$|A \cup B| = |A| + |B| - |A \cap B|.$$ The intersection is subtracted to avoid double-counting elements in both sets.

6. State the Inclusion-Exclusion Principle for three sets.

   $$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|.$$

7. Define $n!$ (n factorial) and give the value of $0!$.

   $n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$ for a positive integer $n$. By convention $0! = 1$.

8. How many ways can $n$ distinct objects be arranged in a row (permutations of all of them)?

   $n!$ ways. The first position has $n$ choices, the next $n-1$, and so on down to $1$, giving $n \times (n-1) \times \cdots \times 1$.

9. Give the formula for the number of permutations (ordered arrangements) of $r$ objects chosen from $n$ distinct objects.

   $$^{n}P_{r} = \frac{n!}{(n-r)!} = n(n-1)\cdots(n-r+1).$$ Order matters; no repetition.

10. How many ways can $n$ distinct objects be arranged in a circle (rotations considered the same)?

    $(n-1)!$ arrangements. Fixing one object to remove rotational symmetry leaves $(n-1)!$ orderings of the rest.

11. How many distinct arrangements are there of the letters in a word where the letters are not all distinct, e.g. with $n$ letters total and repeated letters in groups of sizes $n_1, n_2, \ldots, n_k$?

    $$\frac{n!}{n_1!\, n_2!\cdots n_k!}.$$ Divide by the factorial of each repeat count to cancel indistinguishable rearrangements.

12. How many distinct arrangements of the letters of the word MISSISSIPPI are there?

    There are 11 letters: M(1), I(4), S(4), P(2). Number of arrangements $= \dfrac{11!}{1!\,4!\,4!\,2!} = 34650$.

13. Define a combination and give the formula for $\binom{n}{r}$.

    A combination is an unordered selection of $r$ objects from $n$ distinct objects. $$\binom{n}{r} = {}^{n}C_{r} = \frac{n!}{r!\,(n-r)!}.$$

14. What is the key difference between a permutation and a combination?

    A permutation counts ordered arrangements (order matters); a combination counts unordered selections (order does not matter). They relate by $^{n}P_{r} = \binom{n}{r} \times r!$.

15. State the symmetry property of binomial coefficients.

    $$\binom{n}{r} = \binom{n}{n-r}.$$ Choosing $r$ to include is equivalent to choosing $n-r$ to exclude.

16. State Pascal's rule (the recurrence for binomial coefficients).

    $$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}.$$ This generates Pascal's triangle, where each entry is the sum of the two above it.

17. State the Binomial Theorem for $(a+b)^n$ where $n$ is a positive integer.

    $$(a+b)^n = \sum_{r=0}^{n} \binom{n}{r} a^{n-r} b^{r}.$$

18. What is the general term and its coefficient in the expansion of $(a+b)^n$?

    The term containing $b^r$ is $\binom{n}{r} a^{n-r} b^{r}$, so the coefficient of $a^{n-r}b^{r}$ is $\binom{n}{r}$.

See more Combinatorics, Counting and Number flashcards →

Planning Combinatorics, Counting and Number for Mathematics Admissions Test (MAT)

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