C(n,r) = n!/(n-r)!r!
I discovered this in Wilf's book Combinatorial Algorithms: C(n,r) may be represented as C(n-1,r) + C (n-1,r-1).
C(7,4) = C(6,4) + C(6,3)
= C(5,4) + C(5,3) + C(5,3) + C(5,2)
= C(4,4) + C(4,1) + 3*C(3,3) + 3*C(3,1) + 6*C(2,1) + 6*C(2,2)
As you can see, there is no need for multiplication in the final result.
In every C(n,r) form, either n==r or r==1.
Here is an example of the code I used:
int foo(int n,int r)
if(n==r) return 1;
if(r==1) return n;
return foo(n-1,r) + foo(n-1,r-1);
Approach 2 has overlapping sub-problems where we use recursion to tackle the same sub-problems again.
Using Dynamic Programming, we can prevent this.
Which method is preferable for calculating C(n,r)?