首页 > 代码库 > 数学基础——基本计数方法

数学基础——基本计数方法

计数方法最基础的两个原理是:加法原理和乘法原理。

容斥原理:

假设一个班里有10个学生喜欢数学,15个学生喜欢语文,21个学生喜欢编程。那么班级总人数:

|A∪B∪C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|

一般的,任意多个集合,集合内的元素个数为奇数,前面的符号为正。

 

问题1:排列问题

n个不同的数,选k个排成1排,有多少种排法。

答案计做p(n,k) = n*(n-1)*(n-2)*...*(n-(k-1)) = n!/(n-k)!

 

问题2:组合问题

有n个不同的数,选出k个(顺序无关),有多少种选法。

答案计做C(n,k),则有P(n,k) = C(n,k)*P(k,k);

即:C(n,k) = n!/k!*(n-k)!

 

性质:

1,C(n,0) = C(n,n) = 1;

2,C(n,k) = C(n,n-k);

 

问题3:二项式定理

求(a+b)n的各项系数。

由定理可知 C(n,k)an-kbk  (k由0→n)

 

性质4:

C(n,k+1) = C(n,k)*(n-k)/(k+1)

由此可以计算组合数在O(n)的时间内。

或者根据第一个数要不要,也可以在O(n)递推:http://www.cnblogs.com/TreeDream/p/5346542.html

 1 #include <bits/stdc++.h> 2  3 using namespace std; 4  5 const int maxn = 100; 6  7 int c[maxn][maxn]; 8  9 int main()10 {11     for(int k=1;k<=10;k++) {12         c[k][0] = 1;13         for(int i=1;i<=k;i++)14             c[k][i] = c[k][i-1]*(k+1-i)/i;15     }16 17     for(int i=0;i<=9;i++)18         printf("%d\n",c[9][i]);19 20     return 0;21 }

 

问题4:有重复元素的全排列

有k个元素,第i个元素有ni个,全排列的方案数:

可以先将所有元素标记,答案计做 x

那么: n! = n1!*n2!*...nk! *x

 

问题5:可重复选择的组合

有n个不同元素,每个元素可以选多次,一共选k个。有多少种选法。

例:n = 3,k=2,(1,1)(1,2)(1,3)(2,2)(2,3) (3,3)

第i个元素选xi个,则:


X1 + X +... + Xn = k

令yi = xi+1;

就有Y1 + Y+... + Y = k + n;

就是k+n个 “1” ,从k+n-1根分割线中挑出n-1个→C(n+k-1,n-1)

 

问题6:单色三角形

n个点没有三点共线的情况,只有红色和黑色的线连接两点,求单色三角形的个数。

反着来:求异色三角形。

每个点,他有ai 条红边,n-1-ai条黑线。那么这就是一个异色三角形,这个点的异色三角形ai(n-1-ai)

总共就是1/2*∑ai(n-1-ai)

 

数学基础——基本计数方法