Post History

Let's take a look at the computation once more.

The number of ways of arranging $3$ people in a line is $3! = 3 \cdot 2 \cdot 1 = 6$. That is, for any choice of $3$ people from the group of $8$ people, there are $3!$ ways to arrange them in a line. That is, there are $3!$ redundancies *per* choice of $3$ people. Note the word "per"! If we know the redundancies in arrangements for every (i.e. per) choice of $3$ people, and also the total number of arrangements of $3$ people from the group of $8$, then *dividing* by the total number of redundancies gives the right answer for the number of combinations.

This is a basic counting principle in combinatorics, that can be stated more generally as follows:

Let $\varphi \colon A \to B$ be a map of finite sets with the property that $\lvert \varphi^{-1}(b) \rvert = k$ (constant) for all $b \in B$. Note that $\varphi^{-1}(b) := \\{ a \in A : \varphi(a) = b \\}$. Then, $\lvert B \rvert = \lvert A \rvert / k$.


-----


On the other hand, when should we expect to use subtraction instead of division? I will again phrase this in terms of finding sizes of sets (for example, the count of the number of permutations of $k$ objects out of a pool of $n$ objects is just the size of the set of all permutations of $k$ objects out of a pool of $n$ objects).

The basic idea is that if we want to find $\lvert A \rvert$, and $A \subseteq B$, then it is enough to know $\lvert B \rvert$ (the larger total) and $\lvert B \setminus A \rvert$ (the excess), because $\lvert A \rvert = \lvert B \rvert - \lvert B \setminus A \rvert$. In practice, things are rarely so simple. Instead, we have what is known as the "Principle of Inclusion-Exclusion", which in its simplest forms looks like:
$$
\begin{gather}
\lvert X \cup Y \rvert = \lvert X \rvert + \lvert Y \rvert - \lvert X \cap Y \rvert\\\\
\lvert X \cup Y \cup Z \rvert = \lvert X \rvert + \lvert Y \rvert + \lvert Z \rvert - \lvert X \cap Y \rvert - \lvert X \cap Z \rvert - \lvert Y \cap Z \rvert + \lvert X \cap Y \cap Z \rvert
\end{gather}
$$
etc., or a bit more generally,
$$
\left\lvert \bigcup_{i = 1}^n X_i \right\rvert = \sum_{\emptyset \neq J \subseteq \\{1,\dotsc,n\\}} (-1)^{\lvert J \rvert +1} \left\lvert \bigcap_{j \in J} X_j \right\rvert.
$$
The Principle of Inclusion-Exclusion is very powerful and has much better formulations than the one I just gave. The [Wikipedia page](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle) is a decent place to start exploring this topic.