6
$\begingroup$

Combinatorics problems (combinations and permutations) are an absolutely maddening subject for me. I can seem to work my way to the answer, provided I already know the correct answer. However, I can only rarely get the correct answer on the first try. This is obviously a problem on tests.

In algebra and calculus I can usually verify that an answer is correct by working backwards or plugging the result back in to the original equation.

Is there some way to do the same for enumeration problems?

$\endgroup$
5
$\begingroup$

One of the most important things is that you understand exactly which structures you want to count (making sure when two of them are the same for example). Once you know this you can test if your formula works for small cases which you can work out by hand.

$\endgroup$
5
$\begingroup$

I try to write down a sentence explaining what exactly I'm counting on both sides of the equality, to convince myself that they are the same. For example, for the identity

${n \choose k} + {n \choose k+1} = {n+1 \choose k+1}$

I would write down the the left hand side first counts all subsets of $[n+1]$ of size $k+1$ that include the element $n+1$, plus the number of subsets of $n+1$ that don't include $n+1$. The right hand side on the other hand counts the number of subsets of $[n+1]$ of size $k+1$.

While the original identity does not necessarily seem obvious, when it's written down in text it seems almost trivial. Doing this takes a lot of practise, but when it 'clicks' and you can easily write down descriptions like this, it is very easy to check your answers in combinatorics.

$\endgroup$
4
$\begingroup$

My best suggestion for enumeration problems is to set it up as a sequence of explicitly defined steps being multiplied by multiplication principle (or adding a disjoint set by addition principle). Then, check your steps by mock answering them. See then also if there is a different sequence of choices that arrives at the same answer. If there is, then you may need to divide to account for overcounting (assuming the same problem occurs for any sequence of choices).

For example: How many different Two-Pair hands exist in a 5card hand from a standard 52 card deck of playing cards. (a two-pair consists in this case of three distinct numbers, two of which are repeated, example: $J\heartsuit J\spadesuit 5\heartsuit 3\clubsuit 3\diamondsuit$)

You might answer it in the following way: (note this is slightly incorrect as shown later)

Step 1: Pick the number for the first pair: $\binom{13}{1}$

Step 2: Pick the suits for the first pair: $\binom{4}{2}$

Step 3: Pick the number for the second pair: $\binom{12}{1}$

Step 4: Pick the suits for the second pair: $\binom{4}{2}$

Step 5: Pick the number for the singleton: $\binom{11}{1}$

Step 6: Pick the suit for the singleton: $\binom{4}{1}$

A specific sequence of choices should lead to a unique result, meaning if at least one choice is changed, it should lead to a different result.

Consider the answers to the steps: $(J)(\heartsuit \spadesuit)(3)(\clubsuit \diamondsuit)(5)(\heartsuit)$. Compare this to $(3)(\clubsuit \diamondsuit)(J)(\heartsuit \spadesuit)(5)(\heartsuit)$. Since the answer to the first question is different, we would have counted each of these sequences of answers separately, however notice that they both describe the exact same poker hand (since order of cards in the hand does not matter). In general for this problem, whatever choices you make in steps 1 and 2 can swap places with the choices made in steps 3 and 4 to arrive at the exact same hand. As such we counted each hand (at least) twice. You can convince yourself that you counted each hand only twice. As such, you may divide by 2 due to the symmetry to arrive at the correct answer.

This extends to other types of combinations and permutations problems beyond poker-hand problems. Ask yourself if by shuffling around the answers you get to "same" or "different" outcomes, and ask yourself if there is more than one way to get to the same outcome from a sequence of choices, or if there are any outcomes that cannot be reached by any sequence of choices.

$\endgroup$
0
$\begingroup$

While I appreciate the answers given by others, my question was whether there is a way to directly check the validity of an answer to enumeration problems.

What others have helpfully suggested are more or less heuristics for arriving at the correct answer.

After thinking about this for some time, I've come to the conclusion that simulation is the only suitable answer for directly ascertaining correctness. While this is impossible for some problems due to the enormous amount of computation required to check all possibilities, reducing the problem size should allow one to check a reasonable subset of the problem.

$\endgroup$

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.