I gave my kids in my Canada class a problem today that was basically like this: A monkey is throwing a ball labelled 1, 2, 3 into boxes labelled 1, 2, 3 randomly. What is the probability that none of the balls go into the right box?
For something with such small numbers, it's easy to do by hand. One student was trying to figure out the rigorous way to do it and asked me what the answer was, so I just laid it out by hand and finished it in a minute or so. But then he said, "But what if it's a bigger number?" So I started to work on it with, say, 20 boxes.
So I started to work on it in class, but didn't solve it. I went to dinner and thought a little bit about it, but didn't really make much progress and got distracted by Chinese and also food. So I started to work on it when I came back to my apartment, and it turned out that it was much more difficult than I had anticipated for n greater than 5 or so.
It turns out that you need to use a concept called derangements, which is basically when you find all of the permutations where nothing has been mapped to its proper spot. As in, 1 doesn't go in the first position, 2 doesn't go in the second position, etc. There was a famous problem that was equivalent to "define derangements" from a long time ago called the hat problem (or umbrella problem) where n people go to a party, and you want to find how many ways (or the probability) they leave with all the wrong umbrellas.
I eventually figured out and understood whatever I needed to know about it. !n = (n-1) x (!(n-1) + !(n-2)). Basically, imagine that the first guy at a party picks a hat, call it hat #k. Now think about what guy #k does. If guy #k picks the hat #1, then what's left is !(n-2). Since there are (n-1) ways that guy #1 can pick a guy #k, this is (n-1) x !(n-2). Now imagine that guy #k doesn't pick hat #1. So there are (n-1) ways that guy #1 can pick hat #k, and then we still need to derange !(n-1), so that's (n-1) x !(n-1).
It took me way too long to understand that paragraph above. I think most of the reason why is because I misread the Wikipedia summary of the explanation. I actually went so far as to edit it with my own misunderstanding, and then edit it back when I realized I misunderstood it and why. But anyway, after that, I was able to understand pretty much whatever else there was about it, including the summation formula and another proof via the inclusion-exclusion principle, which I wish I had seen first, sigh.
I don't really know why I wrote this. It was a little bit nice to do math for like 4 hours tonight, but also a little bit dumb and I felt pretty miserable with myself for taking so long to understand some of the things I was doing and solve some of the problems I was working on. I need to do more problem solving and programming, but also more Chinese, and also more music and guitar and drawing, aye...
Peace out.