How to check if you are counting right?

Question

Combinatorics is "hard" even at the elementary level in that verifying answers becomes extremely tricky. While in algebra while a solution to an equation such as $$x^2+4x+3=0$$ is desired, the solution can be obtained and can be checked by plugging the solution by plugging the answer back into the equation.

Consider for instance, this problem.

Find the number of ways to create $5$ groups of exactly two among $10$ people such that no person belongs to two groups.

An incorrect solution: First select a group of two people from the $10$ people. There are ${10 \choose 2}$ of doing this. The next group can be selected in ${8 \choose 2}$ ways and so on. So by the multiplication principle, the total number of ways equal to the value of the following product.

$${10 \choose 2} \times {8 \choose 2} \times {6 \choose 2} \times {4 \choose 2}$$

The idea in the next (incorrect) solution is to create a bijection between the number of permutations of the people standing in a line and the number of groups that can be formed. Though this is the same idea that one possible correct solution uses the groups are overcounted.

Incorrect solution-2: There are $10!$ ways in which the $10$ people can stand in a line. The first and the second person, the third and the fourth and so on are placed in a single group. Since switching the first and second position will give another permutation but the same groups we need to divide by $2$. Similarly switching the third and the fourth position will give a different permutation but the same groups. Therefore ultimately, the total number of ways to form the $5$ groups will be $$\frac{10!}{2^{5}}$$

The solution which yields the correct answer is the following

Correct Solution-2: There are $10!$ ways in which the $10$ people can stand in a line. The first and the second person, the third and the fourth and so on are placed in a single group. Since switching the first and second position will give another permutation but the same groups, we need to divide by $2$. Similarly switching the third and the fourth position will give a different permutation but the same groups. Also consider the following fact. If the people (indicated by letters) are arranged in one permutation as follows, ABCDEFGHIJ then the permutation CDABIJGHEF also correspond to the same set of groups which is why there is a need to divide by $5!$ as there are $5!$ ways to
Therefore ultimately, the total number of ways to form the $5$ groups will be $$\frac{10!}{2^{5}\times5!}$$

Questions concerning the correctness of a counting procedure adopted are quite common on this forum. ( I will add some links if you think it is necessary.) This is one reason this question,albeit subjective, has been asked.Also i have not come across any text which addresses how not to undercount or overcount. Any discussion of techniques on how to avoid undercounting/overcounting or how to check the enumeration will be highly appreciated.

Note:

1. The problems that I mean when i say combinatorics problems are enumerative combinatorics problems. This will perhaps narrow the scope of discussion by a considerable extent.
   2. Though counting in two ways is sometimes a nice way to check whether the solution obtained is right, it takes a lot of ingenuity to enumerate the answer to every problem in two ways. Which is why any answer to this question can avoid that technique and also not include listing out all the possibilities.

Answer 1

Verification of counting may be harder than verification of arithmetic, but the two incorrect solutions can't be blamed on this difference. They are incorrect interpretations of a word problem. This can just as easily happen in an algebra word problem. It's not clear that we can do better than heuristics like, "Where does order matter?", "Are those things labeled or not?", or "Did I overcount?" In practice, the suggestions in the comments are good diagnostics for humans doing counting problems.

In principle, however, verification is possible. Suppose we agree that the set in question is formalized best by a mathematically specified set $A$. Then we can formalize our solutions and verify.

Specifically, we verify answers with bijective proofs. This consists of constructing two sets $A$ and $B$ and a bijection $f:A \rightarrow B$. Then we prove that $f$ is a bijection. Once established, we've verified $|A| = |B|$.

For elementary counting problems, we're usually applying the multiplication or addition principles to already established counting formulas, which themselves can be established with these principles. The more formal version of applying the multiplication principle is to provide a bijection $f:A \rightarrow B \times C$ where $A,B,C$ are sets. For example, if you construct a set $A$ and believe it has $2^3 \cdot 3!$ elements, you can verify this by constructing a bijection from $A$ to $B_3 \times S_3$.

(In case you're unfamiliar, $S_3$ is the set of permutations of a 3-element set and $B_3$ is the set of all subsets of $\{1,2,3\}$.)

For the problem in question, we might (sloppily) formalize the set as $$A = \{\{G_1,G_2,\ldots,G_5\}: G_i \subseteq \{P_1,\ldots,P_{10}\}, |G_i| = 2, |G_i \cap G_j| = \emptyset \}$$

If we agree that's a decent translation, we can then verify there's a bijection $f:A \times B_5 \times S_5 \rightarrow S_{10}$. We can also verify that a specific function $f:A \times B_5 \rightarrow S_{10}$ is not a bijection. Or, if one prefers, the divisions can be captured with equivalence relations and again proceed to construct functions and verify.

While this is not as simple as substituting a proposed value into $x^2 + 4x + 3$ to check, proofs can be made so formal that they become verifiable calculations. It sounds like the paper "Tests and Proofs for Enumerative Combinatorics" goes down this path with computer proof assistants.

Answer 2

Many word problems are of the following form: "An object $x$ has the properties $P_i(x)={\rm true}$ $(1\leq i\leq n)$. What is $x$?"

The given conditions define a set $$S:=\{x\in X\>|\>P_i(x)\ (1\leq i\leq n)\}\ ,$$ whereby the "universe" $X$ of possible $x$ is understood by the problem setting. Solving such a problem one sets up a chain (or even a directed graph) of reasoning of the following type:

$$x\in S\Rightarrow\ldots\Rightarrow\ldots\Rightarrow\ldots\Rightarrow x\in\{x_1,x_2,\ldots x_r\}\ ,$$ or similar. Unless one has a "general theory" for this special kind of problems, which guarantees "exactly $r$", or, e.g., a "vector space of dimension $r$" of solutions one has to test each candidate $x_i$, $1\leq i\leq r$, whether $x_i$ is actually a solution of the original problem.

Now the counting problems are of a different nature. A certain set $X$ is defined, for all to see, and it is claimed that this set set has a certain property, e.g., that it has $9!$ elements. Maybe you have an "alleged proof" for this claim; but there is definitely no "easy check". Note that there is no easy proof for the claim that the nontrivial zeros of the zeta function are lying on the critical line.

Answer 3

This reminds me of this question I answered recently.

Yes, validating your answer is not easy when we have combinatorics or probability questions. There is no generic method one can "mindlessly" follow.

Monte Carlo simulation or brute force computing can help, provided you have understood the question correctly and your model/program is correct. Keep in mind that some questions are easier to validate with this method because they have a straightforward simulation/computation model, while others are more difficult because the model is not apparent or it is difficult to program (and then you worry about validating your program :)).

For example, think about this question: Three people roll a pair of dice each. What's the probability that one person has rolled at least one $1$, while the other two don't have a die with $3$ or below? This would be relatively straightforward to model and simulate. You simulate many rolls of three pairs of dice and you check whether these conditions hold in each try. You count the times they held and divide them by the total number of tries.

On the other hand, how would you simulate/compute the problem at hand (counting the pairings)? I can think of the following brute force computation approach: list all permutations of 10 people, each time grouping them into pairs (1st and 2nd is one pair, 3rd and 4th is another, etc). If a permutation results in a configuration of pairings we have already encountered then we do not count it. It is certainly doable, but there is plenty of room for programming mistakes when trying to find if two pair groupings are the same. Moreover, if we had 100 people instead of 10, computing time would explode using this method. The takeaway message is that even though simulation or brute-force computation can help in some cases, they are not a cure-for-all.

Trying your solution for small values can also help. But be careful. Sometimes wrong formulas give the right answer for small numbers. For our specific question, this is not the case (the wrong formula produces wrong results even for small values) so we could have actually gotten some help if we tried this method. Let's say we have $4$ people instead of $10$. The first (i.e., incorrect) method would yield ${4 \choose 2} = 6$ but when we try to enumerate all possible pairings manually, we get only $3$ ways. Looking into this we can get an insight about how we are double-counting.

But how do we know that there are only $3$ ways to pair $4$ items? What if we made a mistake in our manual counting? One way to feel more confident about our result is to notice that once we choose an item and we create all possible pairs with the 3 remaining items, then the last pair is 'forced' to be formed. This brings me to the crux of the validation issue.

The most helpful thing is to think of different ways of solving the problem. In the question you link, this is what the OP has done. They have realised that they can view the problem like this: Choose one person and then you have $9$ possibilities to pair them with someone. This is our first pair. Then choose another person (does not matter who) and they have $7$ possibilities to be paired. And so on with the rest. So the possible pairings should be: $9\cdot 7\cdot 5\cdot 3 = 945$. In the question, it's not clear that they saw the conflict with the result from the first formula (it seems they did not compute the result from the first formula) but they could have easily done that. This could have given them some insight about the problem. Once you find a mismatch you can start asking why. It's possible that one solution method is more intuitive to you (for example the method I just described seems more intuitive to me than thinking about combinations), so this can guide you to find the mistake in the other way. In any case, you can attack the problem from different angles and think about what your solutions do in small size problems to get some clarity of what's going on.

There is no guarantee that you will find an error, but attacking the problem from many angles is the best way I know. A great side effect of this process is that you gradually gain more insight in the mistakes you and other people do, and you become more confident about your solutions in future problems.