One of our math club leaders gave out this problem as the final problem of math club for the year. I had never seen it before, and after she handed it out, a number of math teachers were in a tizzy about finding the solution. So instead of planning for classes, we enjoyed working on this problem. But we got it! HUZZAH!
Here’s the problem:
In how many ways, counting ties, can eight horses cross the finishing line?
So we fully understand the problem, let me list all possibilities for three horses: Adam, Beatrice, and Candy. No, wait, those are better names for unicorns:
1st: A 2nd: B 3rd: C
1st: B 2nd: A 3rd: C
1st: A 2nd: C 3rd: B
1st: C 2nd: A 3rd: B
1st: B 2nd: C 3rd: A
1st: C 2nd: B 3rd: A
1st: AB (tie) 2nd: C
1st: AC (tie) 2nd: B
1st: BC (tie) 2nd: A
1st: A 2nd: BC (tie)
1st: B 2nd: AC (tie)
1st: C 2nd: BC (tie)
1st: ABC (tie)
That comes out to 13 different ways these horses unicorns can finish the race.
That’s the answer for 3 unicorns. What’s the answer for 8 unicorns?
(FYI: If you want to know if you’re on the right track… I have 541 for 5 unicorns…)
Continuous Everywhere but Differentiable Nowhere 
What a good problem! I’d be interested to hear if you got a closed form for the sequence, I only got a recurrence relation.
I got 541 as well and then googled the sequence. It has a Wikipedia page that I’m trying to avoid reading, at least for a day or two.
I figured pretty much immediately on an explicit formula in terms of Stirling numbers (specifically, that it’s the sum of numbers of the form k!S(n,k), where S(n,k) is the Stirling number of the second kind). Since I didn’t see anywhere easy to take that, I got lazy and put 1,3,13 into OEIS and got sequence A000670. Probably most of what’s knowable about these numbers is there.
I also have a recurrence relation, or maybe a summation involving Stirling numbers if you think that’s better than the recurrence. Nice problem, though!
Prior to this evening and the comments above, I had never heard of Stirling numbers, so I went with this approach:
Click to access An%20Animal%20Problem.pdf
According to http://oeis.org/A000670 I’m off by 2520. If anyone has any insight for how I came up short, I’d love to hear.
Thanks for the great problem, Sam!
Michael, a shorter approach is to figure out how to re-use the previous numbers in the list. Then, if you have the list up to 7 horses, it’s only a few computations to get the number for 8 horses. You can get up to 20 without too much tedium then.
I count 21 things in your list, and I think you need 22 (partition numbers, A000041 — that’s an A-number I know by heart, which I find a bit frightening!) … can I figure out which one you missed? AB,CD,EF,GH maybe? That seems to have 2520 possibilities, so I think I found it.
Maybe a better way to sort the partition numbers is biggest first, like
8
7 1
6 2
6 1 1
5 3
5 2 1
5 1 1 1
and so on. I find I’m less likely to skip one if I sort them that way (and if I list them with numbers like that instead of using the letters), but that may be just me.
Josh, thanks for the reply. I tried to go with a recursive approach first, but ran into a wall. Hence the semi-brute force approach. I’ll tinker with that some more to see what I can come up with. Thanks for finding the one I missed!