各种公式

斯特林公式

斯特林公式（Stirling's approximation）是一个用来求 n 的阶乘的近似值的公式

$$n!\approx \sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n$$

卡特兰数

1. 有 $2n$ 个人排成一行进入剧场。入场费 5 元。其中只有 $n$ 个人有一张 5 元钞票，另外 $n$ 人只有 10 元钞票，剧院无其它钞票，问有多少种方法使得只要有 10 元的人买票，售票处就有 5 元的钞票找零？
2. 一位大城市的律师在她住所以北 $n$ 个街区和以东 $n$ 个街区处工作。每天她走 $2n$ 个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
3. 在圆上选择 $2n$ 个点, 将这些点成对连接起来使得所得到的 $n$ 条线段不相交的方法数？
4. 对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数？
5. 一个栈 (无穷大) 的进栈序列为 $1,2,3,\cdots ,n$ 有多少个不同的出栈序列？
6. $n$ 个结点可构造多少个不同的二叉树？
7. $n$ 个不同的数依次进栈，求不同的出栈结果的种数？
8. $n$ 个 $+1$ 和 $n$ 个 $-1$ 构成 $2n$ 项 $a_1,a_2,\cdots ,a_{2n}$，其部分和满足 $a_1+a_2+\cdots +a_k\ge 0(k=1,2,3,\cdots ,2n)$ 对于 $n$ 该数列为？

该递推关系的解为:$$H_n=\frac{C_{2n}^{n}}{n+1}(n=0,1,2,\cdots)$$

日期问题--基姆拉尔森公式

通过日期可以推算出星期几:

int day(int y,int m,int d)  
{  
    if(m==1||m==2)  
    {  
        m+=12;  
        y-=1;  
    }  
    int w=(d+2*m+3*(m+1)/5+y+y/4-y/100+y/400+1)%7;  
    return w;  
}  
int runnian(int a)  
{  
    if((a % 4 == 0 && a % 100 != 0) || a % 400 == 0)  
        return 1;  
    else  
        return 0;  
}

斐波那契通项

$$F_n=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2}{)}^n-(\frac{1-\sqrt{5}}{2}{)}^n]$$

排列数和组合数

$$A_n^m=\frac{n!}{(n-m)!}$$$$C_n^m=\frac{n!}{m!(n-m)!}$$$$C_n^m=C_{n-1}^{m-1}+C_{n-1}^m$$

其他常用公式

1. n 个点的无向图，任意三点之间不能两两相连（即不含三角形），最大边数为 $\lfloor n^2/4\rfloor =\lfloor n/2\rfloor \times \lceil n/2\rceil$