Catalan numbers

This page uses content from Wikipedia. The original article was at Catalan numbers. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

Catalan numbers are a sequence of numbers which can be defined directly:

Catalan numbers is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

$C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\mbox{ for }}n\geq 0.$

Or recursively:

$C_{0}=1\quad {\mbox{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\text{for }}n\geq 0;$

Or alternatively (also recursive):

$C_{0}=1\quad {\mbox{and}}\quad C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n},$

Implement one or all of these algorithms and print out the first 15 Catalan numbers with each.

Java

Accuracy may be lost for larger n's due to double math (seen for C(15) here). <lang java5>import java.math.BigDecimal; import java.util.HashMap; import java.util.Map;

public class Catalan { private static final Map<Long, Double> facts = new HashMap<Long, Double>(); private static final Map<Long, Double> cats = new HashMap<Long, Double>();

static{//pre-load the memoization maps with some answers facts.put(0L, 1D); facts.put(1L, 1D); facts.put(2L, 2D);

cats.put(0L, 1D); }

private static double fact(long n){ if(facts.containsKey(n)){ return facts.get(n); } double fact = 1; for(long i = 2; i <= n; i++){ fact *= i; //could be further optimized, but it would probably be ugly } facts.put(n, fact); return fact; }

private static double catI(long n){ if(!cats.containsKey(n)){ cats.put(n, fact(2 * n)/(fact(n+1)*fact(n))); } return cats.get(n); }

private static double catR1(long n){ if(cats.containsKey(n)){ return cats.get(n); } double sum = 0; for(int i = 0; i < n; i++){ sum += catR1(i) * catR1(n - i); } cats.put(n, sum); return sum; }

private static double catR2(long n){ if(!cats.containsKey(n)){ cats.put(n, ((2.0*(2*n + 1))/(n + 2)) * catR2(n-1)); } return cats.get(n); }

public static void main(String[] args){ for(int i = 0; i <= 15; i++){ System.out.println(catI(i)); System.out.println(catR1(i)); System.out.println(catR2(i)); } } }</lang> Output:

1.0
1.0
1.0
1.0
1.0
1.0
2.0
2.0
2.0
5.0
5.0
5.0
14.0
14.0
14.0
42.0
42.0
42.0
132.0
132.0
132.0
429.0
429.0
429.0
1430.0
1430.0
1430.0
4862.0
4862.0
4862.0
16796.0
16796.0
16796.0
58786.0
58786.0
58786.0
208012.0
208012.0
208012.0
742900.0
742900.0
742900.0
2674439.9999999995
2674439.9999999995
2674439.9999999995
9694844.999999998
9694844.999999998
9694844.999999998