Tuesday, June 20, 2006

Leading off

For some reason I've decided to join the late '90s and start one of these. There always seemed to me something rather pointless about putting my ramblings out there into the uncaring ether, but here I am.

First I suppose I should explain the title of this blog. It's both hopelessly random and nerdy since it's an obscure mathematical concept that the impatient can read up on here. For the rest of you the story goes something like this:

Years ago I was dating a high school teacher who had some exceptionally dull students. She started giving progressively easier exams until she was reduced to that exercise where you match up the elements in each of columns. One time while hanging around while she was grading these tests I wondered how many you could expect to get right if you just matched them up at random. It was something I didn't think would take very much effort to figure out but after an hour I gave up. Much harder than I expected...

Time goes by, we break up, but every 6 months or so something would remind of that problem and I'd doodle on it for 30 minutes or so before moving onto something else.

Recently though I gave my two weeks notice at a job I was working and found myself with a lot of free time and I decided to really figure it out. After once again spending a fruitless half-hour I decided to write a program that would just brute force the answer for N up to 10 or so to see if any patterns popped up that might give me a hint.

Shocker! The answer is exactly 1 for any value of N (N < size="2">Aside: I swear this isn't going to be a blog about math, but this is the story. Please bear with me.

Anyway, this result, some hints to myself from the way I wrote that program, and a little lucky googling led me to the page I linked earlier and after that the problem fell apart rather quickly. For those that are interested here's the expression that could be translated as "Given random arrangements of N elements on average exactly one element will be in it's natural place". Or to put it another way, "If you're dumb as rocks and staring at a matching problem you may as well go home since guessing will only get you one right (on average)".
Well there you go. The origin of subfactorial (that's that leading "!" for those of you who didn't go through the bother of following the earlier link. Fascinating I know.

For those who can't get enough of the hot math action you may have to wait for a while. Next will probably have something to do with the job I started this week or the new hunt for a roommate so that I will not be spending obscene amounts of money for a place to myself (as nice as that has been).