Combinatorics – How to Verify Correct Counting in Combinatorial Problems

combinatoricssoft-question

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:

  • What are specific "habits of mind" that people in combinatorics use to avoid error?
  • What are specific validation techniques that such people use to check their work? (One does come to mind from my example: Calculate the same thing two ways and confirm equality)
  • Is there any formal list of questions that, if answered, should verify that one's approach is correct?

Best Answer

Here are some methods I have used. Some of these have already been suggested in the comments, and none of them are fool-proof.

  1. Work out a few small cases by hand, i.e. generate all the possibilities, and verify that your formula works in those cases. (Often working out the small cases will also suggest a method of solution.)
  2. Solve the problem by two different methods. For example, often a problem which is solved by the principle of inclusion/exclusion can also be solved by generating functions. Or it may be that you can derive a recurrence that the solution must satisfy, and verify that your solution satisfies the recurrence; if it is too hard to do the general case, verify the recurrence is satisfied for a few small cases.
  3. Write a computer program that solves a particular case of the problem by "brute force", i.e. enumerates all the possibilities, and check the count against your analytic answer. If you don't yet know how to program, this is one of many reasons why it's good to to learn how. For example, how many ways can you make change for a dollar? It's probably easier to write a program that generates all the ways than to solve this problem analytically.
  4. Sometimes a combinatoric problem can be reinterpreted as a probability problem. For example, the problem of counting all the poker hands that form a full house is closely connected to the probability of drawing a full house. In this case you can check your answer by Monte Carlo simulation: use a random number generator to simulate many computer hands and count the number which are full houses. Once again, this requires computer programming skills. You won't get an exact match against your analytic answer, but the proportion of full houses should be close to your analytic result. Here it helps to know some basic statistics, e.g. the Student's t test, so you can check to see if your answer falls in the range of plausible results.
Related Question