Fundamental principles of counting

Three basic rules let us count the number of ways of carrying out a task, without listing every possibility.

1. The Sum Rule. If a first task can be completed in $M$ different ways and a second task in $N$ different ways, and the two tasks cannot be performed simultaneously (i.e. we do one or the other, not both), then there are $M+N$ ways of doing either task. More generally, for $n$ non-simultaneous tasks $T_1,T_2,\ldots,T_n$ performable in $m_1,m_2,\ldots,m_n$ ways respectively, the number of ways of doing one of them is $m_1+m_2+\cdots+m_n$.

Illustration: choosing one girl or one boy for a competition from 17 boys and 29 girls can be done in $17+29=46$ ways.

2. The Product Rule. If a task is made of two procedures, the first completed in $M$ ways and the second in $N$ ways after the first is done, then the whole task can be completed in $M\times N$ ways. Extended to $n$ procedures $P_1,\ldots,P_n$ (performable in $m_1,\ldots,m_n$ ways, with $P_i$ done only after $P_1,\ldots,P_{i-1}$), the task can be completed in $m_1\times m_2\times\cdots\times m_n$ ways.

Illustration: travelling Chennai → Trichy (2 roads) → Tirunelveli (3 roads) can be done in $2\times3=6$ ways.

3. The Principle of Inclusion–Exclusion. When two tasks $A,B$ can be performed simultaneously, simply adding $n(A)+n(B)$ over-counts the ways of doing at least one of them — the ways of doing both at once, $n(A\cap B)$, get counted twice. The correct count is

Illustration: positive integers up to 1000 divisible by 2 or 7: $n(A)=500$ (multiples of 2), $n(B)=142$ (multiples of 7), $n(A\cap B)=71$ (multiples of 14), so $n(A\cup B)=500+142-71=571$.

Tree diagrams are a visual aid: each branch of the tree represents one of the choices available at that stage, and every root-to-leaf path is one complete outcome — useful for laying out, e.g., every brand–colour–variant combination when buying a car. …