Introduction

Combinatorics is the branch of mathematics concerned with counting — with arrangements of objects and with enumerating objects that share a specific property. Its roots go back roughly to 2800 BCE, when it was used to study magic squares and the patterns within them.

The chapter opens with a tribute to Sir Isaac Newton (1643–1727), the English physicist and mathematician most famous for the law of gravitation. Newton's belief in the "persistence of patterns" led him to his first major mathematical discovery — the generalisation of the expansion of binomial expressions, the Binomial Theorem, which he considered the easiest way to work out the quadrature (area) of curves. Its generalisation to several variables, the Multinomial Theorem, is heavily used in combinatorics and statistics today. Newton was also the first to use fractional indices, to apply coordinate geometry to Diophantine equations, to approximate partial sums of the harmonic series by logarithms (a forerunner of Euler's summation formula), and to use — and revert — power series with confidence, an interest sparked by Simon Stevin's work on decimals. He was knighted in 1705, and together with Leibnitz is credited with developing the essential theory of calculus.

Motivating example — the electricity consumer card. An electricity consumer number has the form $A:B:C$, where $A$ is the substation/larger-capacity transformer number, $B$ is the smaller-capacity transformer number, and $C$ is the consumer number linked to it. Each substation can only support a certain maximum number of transformers, and each transformer only a certain maximum number of consumer connections. Deciding whether a new transformer or substation needs to be built comes down to counting how many consumer connections are already linked to a given substation transformer — and that count is found using exactly the counting principles this chapter builds, starting with the Fundamental Principles of Counting, then moving through Permutations and Combinations, and finishing with the Principle of Mathematical Induction, the standard tool for proving the summation and divisibility patterns counting problems throw up.