知识点整理组合数学

定义&＃xff08;#86debe&＃xff09;

　　组合&＃xff1a;C(n,m)表示从n个元素中&＃xff0c;取任意的m个元素的方案数。

　　定义式&＃xff1a;  　　   递推式&＃xff1a;C(n,m)&＃61;C(n-1,m-1)&＃43;C(n-1,m)

　　排列&＃xff1a;A(n,m)表示从n个元素中&＃xff0c;取任意的m个元素并排列好的方案数

常用公式

1.　C(n,m)&＃61;C(n,n-m)

2.　∑C(n,i)&＃61;2^n

　　证明&＃xff1a;从n个元素中任意取i个(0<&＃61;i<&＃61;n)的所有不同方案。

　　　　　首先&＃xff0c;∑C(n,i)表示从n个元素中任意取0个的所有不同取法&＃43;从n个元素中任意取1个的所有不同取法&＃43;从n个元素中任意取2个的所有不同取法&＃43;……&＃43;从n个元素中任意取n个的所有不同取法的总和。

　　　　　其次考虑对于n个元素中的任意一个&＃xff0c;记作A&＃xff0c;则在每次取时&＃xff0c;A都有取或不取两种选择&＃xff0c;并对于A的选择是独立的&＃xff0c;与其他元素无关。所以∑C(n,i)&＃61;2^n。

3.　∑i*C(n,i)&＃61;n*2^(n-1)

　　意义&＃xff1a;i*C(n,i) 表示先从n个元素里取出i个元素&＃xff0c;再从这i个元素中取出一个元素。

　　证明&＃xff1a;参考公式2

4.　∑(i<&＃61;n)C(i,m)&＃61;C(n&＃43;1,m&＃43;1)

　　放到杨辉三角上就是紫色部分的和等于其右下角的值&＃xff08;粉色圈里&＃xff09;

 

5.　∑(i<&＃61;k)C(n,i)*C(m,k-i)&＃61;C(n&＃43;m,k)

卡特兰数

　　括号匹配&＃xff1a;包含2n个括号的合法括号序列有多少个

　　　　将左括号看作0&＃xff0c;右括号看作1&＃xff0c;本问题就变成了&＃xff1a;求序列任意前缀0的个数大于或等于1的个数

　　　　那么对于一个非法序列&＃xff0c;一定存在某个最短前缀中&＃xff0c;1的个数比0的个数多1。此时我们将此前缀01取反&＃xff0c;剩下的不变&＃xff0c;最后得到序列中有n&＃43;1个0和n-1个1。

　　　　得到的方案数C(2n,n-1)

　　　　另外&＃xff0c;此过程是可逆的&＃xff0c;也就意味着对于合法序列&＃xff0c;我们可以将其01取反变成非法序列。

　　通过网格&＃xff1a;从坐标(0,0)到(n,n)&＃xff0c;求不跨过对角线的方案数。

　　　　将向右走记作0&＃xff0c;向上走记作1&＃xff0c;同上。

　　三角划分&＃xff1a;给定一个凸N边形&＃xff0c;求将其三角形化的方案数&＃xff08;划分成N-2个三角形&＃xff09;

　　　　f 是方案数&＃xff0c;h是卡特兰数。

　　　　f(n)&＃61;h(n-2) (n&＃61;2&＃xff0c;3&＃xff0c;4&＃xff0c;……)

　　公式&＃xff1a;

　　1.递推式&＃xff1a;

　　　　　　

　　2.另类递推式&＃xff1a;

　　　　 　　

　　3.递推式的解&＃xff1a;

　　　　　　

　　4.另类递推式的解&＃xff1a;

　　　　　　

　　5.打表结果&＃xff1a;

　　　　1&＃xff0c;1&＃xff0c;2&＃xff0c;5&＃xff0c;14&＃xff0c;42&＃xff0c;132&＃xff0c;429&＃xff0c;1430……

　　例题&＃xff1a;bzoj1485--求catalan数第n项取模

Lucas定理

(待更新补充……&＃xff09;