// from Sedgewick and Wayne
// Note: not perfectly accurate since
//  *  roundoff from double to long.

public class Binomial {

   // return integer nearest to x
   static long nint(double x) {
      if (x < 0.0) return (long) Math.ceil(x - 0.5);
      return (long) Math.floor(x + 0.5);
   }

   // return log n!
   static double logFactorial(int n) {
      double ans = 0.0;
      for (int i = 1; i <= n; i++)
         ans += Math.log(i);
      return ans;
   }

   // return the binomial coefficient n choose k.
   static long binomial(int n, int k) {
      return nint(Math.exp(logFactorial(n) - logFactorial(k) - logFactorial(n-k)));
   }

   // analysis of raw materials
   // for derivative classic MAX-SAT((1,1) (2,0),p, s)
   // a = x / y
   // x = multiplicity of clauses of length 1
   // y = multiplicity of clauses of length 2
   //  
   static double goldenMean(int n, int a){
   // http://en.wikipedia.org/wiki/Fibonacci_number
   // for Fibonacci history.
      return (double)(a*a+binomial(n,2)-binomial(a,2)) /
      (double)(n*a + binomial(n,2));
   }
   // analysis of raw materials 
   // for derivative classic MAX-CSP((22), p, seller)
   // u = number of variables
   static double fourNineth(int u){
     System.out.println(
     u*binomial(2*u,2));
     System.out.println(
     binomial(3*u,3));
     return (double)(u*binomial(2*u,2))/(double) binomial(3*u,3);
   }

   static void p(String s){ System.out.println(s); }

   public static void main(String[] args) { 
     p(Binomial.fourNineth(3) + " for 3 " + "\n");
     p(Binomial.fourNineth(4) + " for 4 " + "\n");
      p(Binomial.fourNineth(10) +" for 10 " +  "\n");
         p(Binomial.fourNineth(100) + " for 100 " + "\n");
	    p(Binomial.fourNineth(1000) + " for 1000 " + "\n");
	       p(Binomial.fourNineth(1000000) + " for 1000000 " + "\n");
	          p(" limit " + (double) (4)/ (double) (9) + "\n");
     p("   goldenMean ======================= " +  "\n");
     p(goldenMean(3,2) + " for 3, 2 " + "\n");
     p(goldenMean(5,3) + " for 5, 3 " + "\n");
     p(goldenMean(8,5) + " for 8, 5 " + "\n");
     p(goldenMean(13,8) + " for 13, 8 " + "\n");
     p(goldenMean(21,13) + " for 21, 13 " + "\n");
     p(goldenMean(34,21) + " for 34, 21 " + "\n");
     p(goldenMean(6765,4181) + " for 6765, 4181 " + "\n");
     p(goldenMean(4181,6765) + " for 4181, 6765 ERROR " + "\n");
     p(" limit " + (Math.sqrt(5)-1)/2 + "\n");
//      int n = Integer.parseInt(args[0]);
//      int k = Integer.parseInt(args[1]);
//      if (n <= 0 || k > n || k < 0)
//         System.out.println("Illegal input.");
//      else
//         System.out.println(binomial(n, k));
   }

}