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

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

容斥原理：

假设一个班里有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)ⁿ的各项系数。

由定理可知 C(n,k)a^n-kb^k(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! = n₁!n₂!...n_k! *x

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

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

例：n = 3,k=2,（1，1）（1,2）（1,3）（2,2）（2,3） （3,3）

第i个元素选x_i个，则：

X₁+ X₂+... + Xn = k

令y_i= x_i+1;

就有Y₁+ Y₂+... + Y_n= k + n;

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

问题6：单色三角形

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

反着来：求异色三角形。

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

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

原文链接: https://www.cnblogs.com/TreeDream/p/6384657.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍