Rigorous nature of combinatorics

Solution 1:

Combinatorics certainly can be rigourous but is not usually presented that way because doing it that way is:

• longer (obviously)
• less clear because the rigour can obscure the key ideas
• boring because once you know intuitively that something works you lose interest in a rigourous argument

For example, compare the following two proofs that the binomial coefficient is $n!/k!(n - k)!$ where I will define the binomial coefficient as the number of $k$-element subsets of $\{1,\dots,n\}$.

Proof 1:

Take a permutation $a_1,\dots, a_n$ of $n$. Separate this into $a_1,\dots,a_k$ and $a_{k + 1}, \dots, a_n$. We can permute $1,\dots, n$ in $n!$ ways and since we don't care about the order of $a_1,\dots,a_k$ or $a_{k + 1},\dots,a_n$ we divide by $k!(n - k)!$ for a total of $n!/k!(n - k)!$.

Proof 2:

Let $B(n, k)$ denote the set of $k$-element subsets of $\{1,\dots,n\}$. We will show that there is a bijection

$$ S_n \longleftrightarrow B(n, k) \times S_k \times S_{n - k}. $$

The map $\to$ is defined as follows. Let $\pi \in S_n$. Let $A = \{\pi(1),\pi(2),\dots,\pi(k)\}$ and let $B = \{\pi(k + 1),\dots, \pi(n)\}$. For each finite subset $C$ of $\{1,\dots,n\}$ with $m$ elements, fix a bijection $g_C : C \longleftrightarrow \{1,\dots,m\}$ by writting the elements of $C$ in increasing order $c_1 \le \dots \le c_m$ and mapping $c_i \longleftrightarrow i$.

Define maps $\pi_A$ and $\pi_B$ on $\{1,\dots,k\}$ and $\{1,\dots,n-k\}$ respectively by defining $$ \pi_A(i) = g_A(\pi(i)) \text{ and } \pi_B(j) = g_B(\pi(j)). $$

We map the element $\pi \in S_n$ to the triple $(A, \pi_A, \pi_B) \in B(n, k) \times S_k \times S_{n - k}$.

Conversely, given a triple $(A, \sigma, \rho) \in B(n, k) \times S_k \times S_{n - k}$ we define $\pi \in S_n$ by $$ \pi(i) = \begin{cases} g_A^{-1}(\sigma(i)) & \text{if } i \in \{1,\dots,k\} \\ g_B^{-1}(\rho(i-k)) & \text{if } i \in \{k + 1,\dots,n \} \end{cases} $$ where $B = \{1,\dots,n\} \setminus A$.

This defines a bijection $S_n \longleftrightarrow B(n, k) \times S_k \times S_{n - k}$ and hence

$$ n! = {n \choose k} k!(n - k)! $$

as required.

Analysis:

The first proof was two sentences whereas the second was some complicated mess. People with experience in combinatorics will understand the second argument is happening behind the scenes when reading the first argument. To them, the first argument is all the rigour necessary. For students it is useful to teach the second method a few times to build a level of comfort with bijective proofs. But if we tried to do all of combinatorics the second way it would take too long and there would be rioting.

Post Scriptum

I will say that a lot of combinatorics textbooks and papers do tend to be written more in the line of the second argument (i.e. rigourously). Talks and lectures tend to be more in line with the first argument. However, higher level books and papers only prove "higher level results" in this way and will simply state results that are found in lower level sources. They will also move a lot faster and not explain each step exactly.

For example, I didn't show that the map above was a bijection, merely stated it. In a lower level book there will be a proof that the two maps compose to the identity in both ways. In a higher level book, you might just see an example of the bijection and a statement that there is a bijection in general with the assumption that the person reading through the example could construct a proof on their own.

Solution 2:

Essentially, all (nearly all?) of combinatorics comes down to two things, the multiplication rule and the addition rule.

If $A,B$ are finite sets then $|A\times B|=|A|\,|B|$.

If $A,B$ are finite sets and $A\cap B=\emptyset$, then $|A\cup B|=|A|+|B|$.

These can be rigorously proved, and more sophisticated techniques can be rigorously derived from them, for example, the fact that the number of different $r$-element subsets of an $n$-element set is $C(n,r)$.

So, this far, combinatorics is perfectly rigorous. IMHO, the point at which it may become (or may appear to become) less rigorous is when it moves from pure to applied mathematics. So, with your specific example, you have to assume (or justify if you can) that counting the number of choices of $2$ men and $3$ women from $8$ men and $9$ women is the same as evaluating $$|\{A\subseteq M: |A|=2\}\times \{B\subseteq W: |B|=3\}|\ ,$$ where $|M|=8$ and $|W|=9$.

It should not be surprising that the applied aspect of the topic requires some assumptions that may not be mathematically rigorous. The same is true in many other cases: for example, modelling a physical system by means of differential equations. Solving the equations once you have them can be done (more or less) rigorously, but deriving the equations in the first place usually cannot.

Hope this helps!

Solution 3:

Let's take an example of how bijective proof works rigorously. We'll prove that $${n \choose k} = {n-1 \choose k - 1} + {n-1 \choose k}, $$ i.e., Pascal's identity, for $1 \le k \le n$. We know that ${n \choose k}$ counts the number of $k$-sets we can make from a set of $n$ elements; let us select an arbitrary set of $n$ elements $A = \{a_1, \dots, a_n \}$, and let the collection of $k$-subsets of $A$ be called $K$. Now because $n \ge 1$ we can isolate an element $e$ of $A$, and, defining $E = \{s \in K: e \in s\}$, we can write $K = E \sqcup (K \cap E^c)$, so that $$|K| = |E| + |K \cap E^c|;$$ and we recall that by definition, $|K| = {n \choose k}$.

Now, take $A' = A - \{e\}$. The point here is that there is a bijection $\phi$ (an intuitively obvious one) between the $(k-1)$-subsets of $A'$ and the elements of $E$; namely, if $\alpha$ is a $(k-1)$-subset of $A'$, we take $$\phi: \quad \alpha \mapsto \{e\} \cup \alpha$$

The proof is trivial: if $\alpha$ and $\alpha'$ are $(k-1)$-subsets of $A'$, then $\{e\} \cup \alpha = \{e\} \cup \alpha' \implies \alpha \subseteq \alpha'$ and $\alpha' \subseteq \alpha$, going element-by-element, so that $\alpha = \alpha'$. In the other direction, if $\beta \in E$ then $\beta - \{e\}$ is a $(k - 1)$-subset of $A'$, so $\phi(\beta - \{e\}) = \beta$. So $\phi$ is injective and surjective, and so it is bijective.

But we know by definition that the number of $(k-1)$ sets we can make from the $(n-1)$ elements of $A'$ is ${n - 1 \choose k - 1}$; and because bijections such as $\phi$ preserve the cardinality of finite sets, we conclude that

$$|E| = {n-1 \choose k-1}.$$

In an entirely similar way we can prove that $|K \cap E^c| = {n-1 \choose k}$. Thus we've proven Pascal's identity, very formally and carefully. But we've also elongated the proof tremendously, and obscured the lines of the argument somewhat with set-theoretic details.