Deranged

No, I’m not checking into a psych ward. A derangement is the mathematical term for a question, such as this, that appeared in my twitter feed:

How many ways can I rearrange the letters ABCDEFGH so that no letter is in its original position? What a deceptively simple question!

We eventually found the answer (14833), but the more interesting point is how we found the answer. R. Wright had an analytical solution, while Andy Rundquist used brute force. I, however, saw this as a member of a set of problems, namely, how can I rearrange the first n letters of the alphabet so each one gets moved? I then proceeded to try small values of n.

For n=1, you’re stuck with A, so f(1)=0. For n=2, AB, becomes BA, so f(2)=1. For n=3, ABC becomes CAB and BCA, so f(3)=2. But {0,1,2…} isn’t distinct enough. I needed another term.

I started writing an organized list: ABCD, ABDC, ADBC, ADCB… but I got bored so I googled and found someone had already typed up all 24 permutations. So I copied them into a text document and eliminated the bad ones, the same process I was going to do on paper. I was left with nine.

Then I surfed over to oeis.org, the Online Encyclopedia or Integer Sequences, and entered 1,2,9. The first item to come up was sequence 000166. There was, as usual for the OEIS, a lot of math jargon, and I didn’t know the term derangement yet. I could tell the sequence had something to do with factorials and combinatorics and had a recursive definition, but I wasn’t sure, so I checked the next sequence. I knew the correct sequence would have to increase O(n!), never dropping to 0 nor exceeding n! as n got big. The second sequence listed was not bounded above by n!, which meant it said there were more permutations meeting the no repeats criteria than there were permutations total, so that couldn’t be it. The next sequences had the numbers in no particular order, so they were out too. I tweeted that I “suspected” the first sequence. If I had thought to google “subfactorial” or “derangements”, I could have found less technical information telling me this was indeed the case.

We live in the 21st century. There has been a lot discovered already, and in the last 10 years a lot of it has been put online for all to see. We do not need to reinvent the wheel, as long as we know when to ignore the used wheel salesman. (“Ugg not sure about square. That work?”) Notice how my thought process includes sanity checks, broadening or narrowing as appropriate, and using existing resources? I call this the exploration of the known. (Known to humanity, but not to you.)

The truth is out there. You just have to know where and how to look.

Advertisements

3 responses to this post.

  1. I’ve made a note of this post over at my place. There are some aspects of what you’ve done here that I’d like to understand better, so I have a few questions, if I may:

    1. Do you think that the problem of counting derangements is important? Why (or why not)?
    2. Why do you think the general problem of counting derangements was first posed?
    3. Why do you think I posed such a specific problem (8 letters)?
    4. Would my original question have been better or worse if I had used the word “derangement” in it somehow?
    5. What did you learn in the process of answering the question?

    That’s all I can think of now.

    Reply

  2. 1. It’s a curiosity. “Oh, that’s neat, we can explain that.” If there was a practical application, it would become more important.
    2. If my point is that reading the right bit of existing knowledge can be very helpful, here’s more support. I read that it had to do with hat checks, where if the hats were not labelled the clerk would have to guess whose hat was whose, and a derangement would be the worst case scenario. It also comes up in a card game where an entire deck is laid out, and another right beneath it. What’s the probability that no pairs of card are the same card?
    3. Perhaps there is a practical application involving eight letters. More likely you wanted a problem that could not be done by brute force, and figure going through 8!=40320 permutations would be a sufficient deterrent. Foiled on two fronts: Andy Rundquist got a computer to crunch the numbers, and I solved the simpler problem.
    4. I like to say that one should not define one’s terms but label one’s concepts. The question would have been worse, because I could have googled that straight away. Instead, I became involved and invested in the question. I built the concept first, and applied the label “derangement” as the capstone. I will remember the problem and its solution for far longer if it had been something to “get through” in a textbook.
    5. There are different approaches to a problem, and if you try to set up one path, someone will game the system. However, because that requires more work and a deeper understanding of the problem, it is likely to be at least as effective pedagogy. Many problems have a solution that exists already, but unless one creates a suitable foundation for it, it won’t stick.

    And a question for you: what did you hope to learn from my responses to those questions?

    Reply

  3. To be honest, I’m partially still working to pin down exactly what it is I’m trying to understand, if that makes sense. All I can say for sure is that it has something to do with your motivations. A few follow-up questions may help:

    The question would have been worse, because I could have googled that straight away.

    So would it have been even better if it were a problem that didn’t have an OEIS sequence (or Wikipedia entry, etc.) but were still accessible to undergraduate students?

    I will remember the problem and its solution for far longer if it had been something to “get through” in a textbook.

    What benefit(s) do you see in remembering the general formula for the number of derangements?

    As a side note to #3, I picked n=8 so that it wouldn’t be doable by hand, but would still have a fairly small answer (I specifically used letters for pedagogical reasons). But I knew from the start that if it generated any interest, someone would brute-force it. Your approach was the surprising one, which is why I’m not asking Andy Rundquist any questions. 🙂

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: