catalanカトラン数

catalanカトラン数:カトラン数は組合せ数学において種々のカウント問題によく現れる数例である.ベルギーの数学者オーイン・チャーリー・カタラン(1814-1894)によって命名された.カタラン数の一般的な公式はC(2 n,n)/(n+1)である.
一般的な計算式は、(再帰的):h(n)=(4 n−2)/(n+1)*h(n−1)(n>1)、h(0)=1である.
単一catalanのC++プログラムを計算します.

ll catalan(int n)
{
    if(n==0||n==1) return 1;
    ll sum=1;
    for(int i=2;i<=n;i++)
        sum=(4*i-2)*sum/(i+1);
    return sum;
}

複数のcatalanを計算する打表C++プログラム:

ll ca[100];
void catalan(int n)
{
    ca[0]=ca[1]=1;
    for(int i=2;i<=n;i++)
        ca[i]=(4*i-2)*ca[i-1]/(i+1);
}

30番目以降はcatalan数がlong longを超えているので、JAVA大数算のcatalan数を添付します.

import java.io.*;
import java.math.*;
import java.util.*;
public class Main 
{
	private static BigInteger four=BigInteger.valueOf(4);
	private static BigInteger two=BigInteger.valueOf(2);
	private static BigInteger []ca=new BigInteger[105];
	public static void catalan(int n)
	{
		ca[0]=ca[1]=BigInteger.ONE;
		for(int i=2;i<=n;i++)
		{
			BigInteger nn=BigInteger.valueOf(i);
			BigInteger mm=(four.multiply(nn)).subtract(two);
			BigInteger ii=nn.add(BigInteger.ONE);
			ca[i]=(mm.multiply(ca[i-1])).divide(ii);
		}
	}
    public static void main(String[] args) 
    {
        Scanner cin=new Scanner (new BufferedInputStream(System.in));
        catalan(100);
        while(cin.hasNextInt())
        {
        	int n=cin.nextInt();
        	System.out.println(ca[n]);
        }
        
    }
}

カトラン数の前項:1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700,17672631190,6564120,420,244666267020,91482563640,343059613650,12890414734,4861946401452,...
最もよく使われるcatalan数は、スタックの問題です.スタック(無限大)のスタックシーケンスは1,2,3です.n、いくつの異なるスタックシーケンスがありますか?catalan数に合致します.
wikioi 1086,3112,3113,3134.
また、2014マイクロソフトのプログラミングの美しさにはcatalan数がある.