How to estimate the number of recursive calls

[nuzzle]

where is the factorial in this formula?

Pascal's triangle consists of binominal coefficients (n|k) defined as n! / (k! * (n-k)!) so there are lots of factorials in the solution. I wouldn't say that hinting at factorials is such a great help really but maybe the author has some other solution approach in mind where they play a more prominent role.

In my solution binominals appear because they have a combinatorial interpretation. (n|k) tells how many ways there are to order k of n elements. There may be a deeper reason why they appear as a subtriangle of Pascal's triangle or maybe it's just coincidental. I couldn't say but it's interesting.