60
$\begingroup$

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?
$\endgroup$
  • 23
    $\begingroup$ Checking your answer for small $n$ (in cases where you can count manually) is a good sanity check. $\endgroup$ – angryavian Jun 28 '17 at 23:45
  • 63
    $\begingroup$ In 1962 in my sophomore Intro to Probability, my prof asked how many legs a cow had. Twelve, he explained: two in front, two in back, two on the left, two on the right and one at each corner. We did not think it was funny. A few weeks later he told the same joke and everyone laughed. $\endgroup$ – John Wayland Bales Jun 28 '17 at 23:46
  • 8
    $\begingroup$ Often, you can't be sure. And that's one reason I dislike combinatorics personally - I'm never sure if I've massively screwed up. :) $\endgroup$ – Deepak Jun 29 '17 at 0:06
  • 2
    $\begingroup$ I think it was in the preface to the 3rd edition of "Generatingfunctionology" where I read the most(?) bijective (read counting) proofs we know were first discovered from messing around with generating functions in the first place. And apparently "A = B" by Petkovsek (and others) provides a(the?) full-proof method/s of solving most any textbook problem of the kind you mentioned. Haven't read either yet, but google them and see for yourself. $\endgroup$ – user448692 Jun 29 '17 at 1:20
  • 2
    $\begingroup$ @Stephen If you divide that by $5!$: $$ \frac{ {10 \choose 2}{8 \choose 2}{6 \choose 2}{4 \choose 2}{2 \choose 2}}{5!}$$ you get the right answer. $\endgroup$ – Trevor Gunn Jun 29 '17 at 19:24
35
$\begingroup$

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.
$\endgroup$
  • 3
    $\begingroup$ Being a programmer, I think, "of course my hammer works on this nail", but intellectually I rebel against the idea that the best way to check my theory is to use a machine that didn't exist when the study of combinatorics was born... $\endgroup$ – Kristen Hammack Jun 29 '17 at 12:55
  • 8
    $\begingroup$ @KristenHammack - Why would that be a problem? Hammers and nails didn't exist when someone first had to figure out how to hold two pieces of wood together. But in most situations they are a superior solution to tying the wood together with braided grass or strips of leather. $\endgroup$ – Paul Sinclair Jun 29 '17 at 16:49
  • 1
    $\begingroup$ @PaulSinclair that's certainly an interesting way of looking at it. But I was wondering if maybe there was a more elegant "screwdriver" type of solution, with the brute force programming method being more like "let me hammer this screw into the wood", and a formal proof being "here's the perfectly-fitting screwdriver for this particular screw". I'm used to seeing that in CS. $\endgroup$ – Kristen Hammack Jun 29 '17 at 17:04
  • 1
    $\begingroup$ Plus a programming check probably won't give much extra intuition about why a solution is correct or incorrect. I am also a programmer and wouldn't hesitate to write a program to do the check if I needed it, but it wouldn't be my first choice. $\endgroup$ – Stephen Jun 29 '17 at 21:42
  • 5
    $\begingroup$ @KristenHammack But the question is not about "how do you figure this out". It is about "I think I have it solved, but I want to double-check that I haven't missed something". For this, "experimental mathematics" is and always has been a tool-of-choice. And computers vastly increase the amount of experimentation that is feasible. And for Stephen's comment, even if you are still trying to figure it out, having a good sample of actual solutions can be a godsend for better understanding the behavior. Computer proofs may be boring, but they are excellent mathematical telescopes. $\endgroup$ – Paul Sinclair Jun 29 '17 at 23:10
12
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Having somebody look over work is a very good suggestion. Fortunately I am in a programming context where code review is de rigeur $\endgroup$ – Stephen Jun 29 '17 at 1:34
9
$\begingroup$

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:

  • For all $m$: $p(p(m)) = m$ (i.e. a person's partner is paired with the person)
  • For all $m$: $p(m) \neq m$ (i.e. nobody is partnered with themself)

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:

  • Consider the person from $U_k$ with the smallest number – call them $g_k$.
  • Find out who they're partnered with – that is, evaluate $p(g_k)$ - and find that person's "rank" in $U_k\setminus g_k$ starting from 0. That is, if (of all people other than $g_k$ who are so far unpartnered) $p(g_k)$ has the lowest number, call them rank 0, and if there are three with numbers lower than $p(g_k)$ that are unpartnered, call them rank 3, and so on. Call that rank $r_k$.
  • Set $U_{k+1} = U_k \setminus \{g_k, p(g_k)\}$ and $v_{k+1} = v_k\left|U_k-1\right| + r_k$. That is, take out the two people we just partnered, and calculate a new value from the previous step's value and the rank of the person we just partnered with $g_k$.

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.

$\endgroup$
  • $\begingroup$ It's good to be able to do things with symbols like this; it's seldom necessary. Excellent mathematics uses symbols to convey an intuitive understanding. Mediocre mathematics uses symbols in place of intuitive understanding. Poor mathematics uses symbols to disguise the total absence of intuitive understanding. $\endgroup$ – Wildcard Jun 29 '17 at 19:37
  • 3
    $\begingroup$ @Wildcard: I don't think anyone said it was necessary! The point is that it is possible to achieve a high degree of rigour in combinatorics. The OP was asking about how to be more sure about one's answers; symbolic reasoning is a powerful tool that can help with that. $\endgroup$ – psmears Jun 29 '17 at 20:08
  • 1
    $\begingroup$ psmears upvoted for your efforts. I didn't quite understand it, but I will come back to it once my math is a bit stronger (specifically once I understand bijections). Also @Wildcard that is quite funny. $\endgroup$ – Stephen Jun 29 '17 at 23:52
  • $\begingroup$ @Stephen:Sorry--it's hard to know what level to go for! A "bijection" is a fancy name for a function that is invertible: the basic idea above is to find a way of giving each possible partnering a unique number, such that given a partnering you can find its number, and given a number you can find the corresponding partnering. Once that's done, if the partnerings are numbered 0 to $m-1$, you know there are $m$ partnerings in total. The advantage is everything (after the initial definition) can be 100% rigorous--but that's a lot of work (my long answer omits many details), hence it's rarely done! $\endgroup$ – psmears Jun 30 '17 at 9:38
  • $\begingroup$ This is an enlightening answer. We go to a lot of trouble to develop other subjects rigorousIy, we should know how to do it for combinatorics as well. I especially like your emphasis on the modeling step, which I think is often glossed over in combinatorics books. $\endgroup$ – littleO Jul 6 '17 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.