public class RecBinomial{

    private static long bin(int n,int k){
	if (k == 0) return 1;
	if (n == 0) return 0;
	if (n == k) return 1;
	if (k == 1) return n;
	return bin(n-1,k-1) + bin(n-1,k);
    }

    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        int K = Integer.parseInt(args[1]);
	System.out.println(bin(N,K));

    }
}

/*

Why is the above correct? Just a reminder bin(n,k) is the same thing as 
choose(n,k), i.e. how many ways can I choose k objects from n with order
of no concern. bin(10,2) is how many pairs choosing from 10, bin(10,3) how
many triples choosing from 10 objects, ... i.e. n!/(k!(n-k)!) It's also
called the binomial coefficient.

So, why is bin(n,k) = bin(n-1,k-1) + bin(n-1,k)? This is "Pacal's rule" and
we give a combinatorial proof as follows ...

Adopt the mind set of the power set ... To choose k objects from n do as follows

(a) given the set S, select and remove an object and call it X 
(b.1) generate all possible k-1 tuples from S
(b.2) add X to each of these k-1 tuples to produce k tuples
(c.1) generate all possible k tuples from S, none of which contain X
(d.1) combine the k tuples in (b.2) with those in (c.1)

Therefore in the (b) steps we generate bin(n-1,k-1) k-tuples 
and in (c) step we generate bin(n-1,k) tuples. Consequently

   bin(n,k) = bin(n-1,k-1) + bin(n-1,k)

But how many recursive calls are performed? And can we do this more efficiently?
To answer the 1st question in main set count to 0 and in bin add count++. Print
count as we print out the result. Or just call RecBinomial 100 50 and ... wait.

Now go look at Binomial ... this is another example of dynamic programming.
Look at the wiki on Dynamic Programming: "The key part of the wiki is as follows:
The key idea behind dynamic programming is quite simple. In general, to solve a given problem, 
we need to solve different parts of the problem (subproblems), then combine the solutions of the 
subproblems to reach an overall solution. Often, many of these subproblems are really the same. 
The dynamic programming approach seeks to solve each subproblem only once, thus reducing the number 
of computations: once the solution to a given subproblem has been computed, it is stored or "memo-ized": 
the next time the same solution is needed, it is simply looked up. This approach is especially useful 
when the number of repeating subproblems grows exponentially as a function of the size of the input."

This is exactly what we see in Binomial.java and in FibDP.java!

*/