++tye for generating the excellent formula. Lots of interesting math involved in seemingly simple looking problem. Why the formula make sense is a very good question and I don't have answer at the moment.
I had suspected the factorials once I saw symmetry and little similarity with pascal's triangle, but tye came out faster even with the solution.