This is a soft question, but I’ve tried to be specific about my concerns. When studying basic combinatorics, I was struck by the fact that it seems hard to verify if one has counted correctly.
It’s easiest to explain with an example, so I’ll give one (it’s fun!) and then pose my questions at the bottom. In this example there are two ways to count the number of ways $2n$ people can be placed into $n$ partnerships (from the book Introduction to Probability by Blitzstein and Hwang):
$$\frac{(2n)!}{2^n \cdot n!} = (2n – 1)(2n – 3) \cdots 3 \cdot 1$$
Story proof for the right side: For the first person you have $(2n – 1)$ choices for partner. Then for the next person you have $(2n – 3)$ choices, etc.
Story proof for the left side: Line all $2n$ people up, walk down the line, and select every 2 people as a pair. The ordering you chose for the line determines the pairs, and there are $2n!$ ways to order $2n$ people. But divide by $2^n$ because the order within each pairing doesn’t matter. Also divide by $n!$ because the order of the pairings doesn’t matter.
My question is:
What if I had been tasked with getting this number at work, and I chose the approach on the left side, but I neglected to divide by $2^n$ and only divided by $n!$? I’d be wrong of course, but how could I have known?
I suppose one answer to my question could just be “Try hard, try to think of ways you might be over/undercounting, look at other examples, and continue to study theory.”
But the prospect of not knowing if I’m wrong makes me nervous. So I’m looking for more concrete things I can do. So, three questions of increasing rigor:
Here are some methods I have used. Some of these have already been suggested in the comments, and none of them are fool-proof.
Here are some other methods:
Estimate what the answer should be. For example, Let’s say I want to count all 3-element subsets of $1,\dots,n$ where the sum of any two elements is not equal to the third. I think to myself “hmm, if $n$ is large then most three element subsets should be valid.” So whatever the answer is, I know that it should be close to $\binom{n}{3}$ if $n \gg 0$.
Also keep in mind that your intuition about how large the answer should be might be off. This is ok! It means you will put more thought into the problem.
Have someone look over your work. This can work really well because sometimes you’ll have something you are mistaken about in the back of your mind when you are writing. When this happens, what you write will (hopefully) look funny to other people whereas it might take a lot of thought on your part to catch that something is off.
Be more rigorous. This is easier said than done, obviously. For example if you are applying a theorem, look to make sure that you satisfy all the necessary hypotheses to be able to apply it.
Slow down and think about “why am I multiplying here?” or dividing, or differentiating. Make sure the algebra makes sense combinatorially. If you are dividing, make sure you end up with integers where there should be integers.
It is actually possible to be rigorous in questions like this – though it can be a lot of work.
The first step is to build a mathematical model that corresponds to the question. This part deserves some thought, and there is scope for error, but usually just expressing the question mathematically is easier to do without error than finding the actual answer.
For this example, we might say that a partnering of a group of $2n$ people (whom we’ll refer to as $G=\left\{0, 1, \ldots, 2n-1\right\}$) is any function $p: G \rightarrow G$ such that:
Hopefully it’s fairly clear that the above corresponds to the definition of a partnering from the question – if not, you can do it in a way that’s clearer to you.
Having made that definition, the question becomes: how many such functions $p$ are there?
One way to establish the answer rigorously is to come up with a bijection $B$ between the set of partnerings $P = \{p: p \,\hbox{is a partnering of $2n$ people}\}$ and an initial subset of the natural numbers $\mathbb N$.
That can be done as follows – I’ll omit a lot of details for brevity, but hopefully it should be clear that this can be made fully rigorous. Given a partnering $p$:
Start with a set $U_0=G$ of unpartnered people, and a value $v_0=0$. At each step $k$, starting from 0:
Repeat for $k$ from 0 to $n-2$, and take $v_{n-1}$ as our result for $B(p)$.
It’s clear that, given any partnering $p$, this procedure gives us back a number $B(p)$. What may not yet be clear is that, given $B(p)$, we can determine what $p$ was – that is, $B$ is a bijection.
I won’t go into the details of that, but note that, when calculating the value, the person who gets partnered with person 0 has their rank multiplied by $(2n-3)(2n-5)\ldots1$, and we can get it back by dividing $B(p)$ by that number – the integer part of the answer gives us $p(0)$, and then we can use the remainder in a similar way to deduce the rest of the pairings in $p$.
So (again I’m leaving out some proof details) we have a function that is a bijection between $\left\{0,1,2,\ldots,m-1\right\}$ and the set of possible partnerings of $2n$ people. This is enough to show that there are $m$ such partnerings – and it’s reasonably easy to see (by taking the maximum possible value at each step in the procedure above) that the value of $m$ is exactly $(2n-1)(2n-3)\cdots 1$ as you already knew.