Or the even-less-computationally-intensive algorithm: http://en.wikipedia.org/wiki/Pascals_triangle#Calculating_an...

Thats what dspeyer did here: http://news.ycombinator.com/item?id=3431687 .

For an algorithms heavy job, I would hope a candidate would be able to derive this equation with a little guidance (ie, reminding them about n choose k and how to write that with factorials)

Very nice but expecting the candidate to know that much about Pascals triangle upfront seems a bit too much ;)

Factorials risk integer overflow in the intermediate calculations, though something similar can work.

Yes, it seems a number of optimizations are possible. At least it is not necessary to calculate n!. Depending on the job discussing these strategies and whether they are worthwhile for some real world problem can be quite interesting.