Tag Archives: combinatorics

Simple But Evil #9: Combinatorics — Order Doesn’t Matter

Leave a reply

You’re teaching a basic unit in combinatorics. You’ve covered the factorial and made a few jokes about \(!\) and that one shouldn’t shout \(5!\). Now you’re up to combinations and permutations and you have your standard speech prepared. Some mantra like this is typical.

Permutation means that order matters. Combination means that order doesn’t matter.

And maybe you have a standard set of introductory problems.

How many ways can you choose 3 objects from 5 if you don’t care about the order? If you did care about the order?

And at this point, you demonstrate the difference between the calculations of \({5 \choose 3} = \frac{5!}{3!2!}\) and \(\frac{5!}{2!}\) and what they mean. Usually — that is, textbook — the explanations are like this:

If we have 5 distinct objects, then there are a total of \(5!\) unique orderings. Now, for each ordering, if we are to retain only the first three objects, then we have \(\frac{5!}{2!}\) distinct ways of doing so since we didn’t care about the order of the last two objects. In other words, we divide by \(2!\) because each ordering of the first three objects had \(2!\) copies, hence we divide out that proportion. Now, if we retained the first three objects but were indifferent to how they were ordered, then we further divide by \(3!\) since that is the factor of overcounting. Thus, we arrive at \(\frac{5!}{3!2!}\). The former is a permutation, the latter a combination.

Ok, so this is fine and dandy.

But there’s a small linguistic problem.

Order doesn’t matter.

This standard phrase isn’t wrong, but it can be overemphasized. So let’s “Simple But Evil” this thing.

First, let’s poll the Twitterverse for a good candidate word.

Lori Wike wins this contest with APOTHEM.

Runners up were QUADRIC

and RHOMBUS

Exercise #1

Start with a standard exercise.

Q: How many ways can I pick 3 distinct letters from APOTHEM without caring about the order?

A: And of course, the answer is \({7 \choose 3} = 35\). Hooray! You win!

Exercise #2

Now let’s crank it up one notch.

Q: How many ways can I pick 3 distinct letters from APOTHEM so that the letters are arranged in alphabetical order?

A: Odds are your students’ brains are going to explode. The answer is \({7 \choose 3} = 35\) and now you are set for a debate. Doesn’t a combination mean order doesn’t matter? So then why is the solution \(7 \choose 3\) when we cared about alphabetical order?? Here’s where our language screwed the idea.

There are a few ways to reason around this without invoking the “order matters / doesn’t matter” language. Here’s one way:

If I am to choose 3 letters from \(APOTHEM\) (we’ll get to alphabetical ordering in a second), then there are \(7\times6\times5\) rearrangements because the first position had 7 choices available, the second position had six choices available, and the third position had five choices available. But this calculation is \(\frac{7!}{(7-3)!}\) (permutation!). Ok, but of those three letters chosen and their resulting rearrangements, I only CARED ABOUT ONE ORDERING — namely, an alphabetical ordering. Thus, if we alphabetized all \(\frac{7!}{(7-3)!}\) rearrangements, we would see that we have \(3!\) copies for each three-letter choice. For example, \(APO, AOP, PAO, POA, OAP, OPA\) really all represent \(AOP\). Since this is a “for each” kind of overcounting, we have division giving \(\frac{7!}{(7-3)!3!}\) rearrangements so that the letters are alphabetized.

Another way can be to recognize that once I have chosen my 3 letters, then by imposing the alphabetization rule, I am actually destroying all other orderings.

Perhaps better language is that

for permutations, all orderings matter and for combinations, only one ordering matters

Exercise #3

Did we learn anything?

Q: How many ways can I pick 3 distinct letters from APOTHEM so that the letters are arranged in alphabetical or reverse alphabetical order?

A: \(2\times{7 \choose 3}\) — note that each ordering is captured in \(7 \choose 3\) and we cared about two specific orderings!

Exercise #4

Brain melting in full force.

Q: How many ways can I pick 3 distinct letters from AEHMOPT without changing the initial ordering?

Answer is left to the reader.

How Was The Winner Decided?

The word that had the greatest total Levenshtein distance among all the submitted (valid) words was the winner. I’m using Levenshtein distance as a proxy for unique.


def levenshteinDistance(s1, s2):
    if len(s1) > len(s2):
        s1, s2 = s2, s1
    distances = range(len(s1) + 1)
    for i2, c2 in enumerate(s2):
        distances_ = [i2+1]
        for i1, c1 in enumerate(s1):
            if c1 == c2:
                distances_.append(distances[i1])
            else:
                distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1])))
        distances = distances_
    return distances[-1]

source: https://stackoverflow.com/questions/2460177/edit-distance-in-python

Now, collect the words


words = ["APOTHEM", "ARCSINE", "VECTORS", "NUMBERS", "HEXAGON", "DECAGON", "SURFACE", "PRODUCT", "LIMAÇON", "DECIMAL", "COMPLEX", "QUARTIC", "RHOMBUS", "FORMULA", "PROLATE", "PROJECT", "MODULAR", "MEDIANS", "SUPREMA", "SIMPLEX", "QUADRIC", "ORDINAL", "BRACKET"]
words = set(words)

Iterate over all cross products and sum the Levenshtein distance. Sure, \(lev(a,b) = lev(b,a)\) but it’s happening for all words, so if there is any concern of duplication, it’s irrelevant.


lev = {w: 0 for w in words}
for a,b in itertools.product(words, words):
    if len(set(list(a))) != 7:
        print("oops", a)
    if a != b:
        lev[a] += levenshteinDistance(a,b)

And the winner? A tie between APOTHEM, QUADRIC, and RHOMBUS. I’m the tiebreaker and gave the win to APOTHEM.


APOTHEM 144
ARCSINE 140
BRACKET 140
COMPLEX 137
DECAGON 139
DECIMAL 136
FORMULA 140
HEXAGON 143
LIMAÇON 143
MEDIANS 139
MODULAR 140
NUMBERS 140
ORDINAL 139
PRODUCT 135
PROJECT 137
PROLATE 135
QUADRIC 144
QUARTIC 142
RHOMBUS 144
SIMPLEX 138
SUPREMA 139
SURFACE 138
VECTORS 142