组合数学常用内容——基础内容+莫比乌斯反演

组合数学常用公式

A(n,r)=n(n-1)…(n-r+1)=n!/(n-r)! C(n,r)=A(n,r)/r!=n!/((n-r)r!) C(n,r)=C(n,n-r) C(n,r)=C(n-1,r)+C(n-1,r-1) C(n+r+1,r)=C(n+r,r)+C(n+r-1,r-1)+…+C(n+1,1)+C(n,0) C(n,k)C(k,r)=C(n,r)C(n-r,k-r) C(n,k+1)=C(n,k)*(n-k)/(k+1) 重复排列：n^r; 可重复组合：C(n+r-1,r) 不相邻组合：C(n-r+1,r) 圆周排列：A(n,r)/r 项链排列：A(n,r)/2r 多重全排列（r1个a1,r2个a2……组成n位串）：n!/(r1!*r2!*…) 多项式的n次方的某项系数：(a1+a2+…+at)^n=∑n!/(r1!r2!…rt!)*(a1^r1*a2^r2*…*at^rt) 错排递归公式：f(i) = (i - 1) * (f(i - 1) + f(i - 2)); i >= 4 (f(0) = 0, f(1) = 0, f(2) = 1, f(3) = 2) （错排：n个节点它们原来的位置为i，然后让你把它们从新排列使得它们都不在它们原来的位置上。）

组合数预处理

typedef long long ll; const int MAXN = 42; ll c[MAXN][MAXN]; void init(){ c[0][0]=1; for(int i=1;i<MAXN;i++){ c[i][i]=c[i][0]=1; for(int j=1;j<MAXN;j++){ c[i][j]=c[i-1][j]+c[i-1][j-1]; } } }

母函数

母函数讲解详见： http://blog.csdn.net/vsooda/article/details/7975485

这里直接贴出我的模板，注释非常详细，知道母函数概念，下面的代码根据注释就可以理解了

int main(){ int T; cin >> T; while (T--){ int n, m, sub[10], num[10];//sub对应背包中的体积/重量，num对应背包中的价值 int c1[41], c2[41]; //c1存储系数，也就是方案数，c2存储运算中间数据提供给c1更新 cin >> n >> m; for (int i = 1;i <= m;i++){ cin >> sub[i] >> num[i]; } clean(c1, 0); //对c1初始化，由第一个表达式初始化，把从1*sub[1]到num[1]*sub[1]各项（或从1*sub[1]到num[1]*sub[1]各项中直到能达到学分要求的项）的系数都赋成1 for (int i = 0, t = 0;i <= n&&t <= num[1];i=i+sub[1],t++){ c1[i] = 1; } //对c2初始化，全部赋0 for (int i = 0;i <= n;i++){ c2[i] = 0; } //从第二个式子开始，直到遍历完m个式子 for (int i = 2;i <= m;i++){ //j就是第i个表达式前面那个式子里的第j个变量，如：(1+x)(1+x^2)(1+x^3)，c1[j]先指示的是1和x的系数，i=2执行完之后变为（1+x+x^2+x^3）(1+x^3)，这时候c1[j]应该指示的是合并后的第一个括号的四个变量的系数 for (int j = 0;j <= n;j++){ //k是第j个的指数，k每次增加sub[i] for (int k = 0, t = 0;(t <= num[i]) && (j + k <= n);k=k+sub[i], t++){ c2[j + k] += c1[j]; //这里j+k是保证从sub[i]+j到sub[i]*num[i]+j都加到c2里面，以便后面c1更新数据的时候直接拷贝c2里面的数 } } //把c2的值赋给c1，把c2赋成0，因为c2每次是从一个表达式中开始的 for (int j = 0;j <= n;j++){ c1[j] = c2[j]; c2[j] = 0; } } cout << c1[n] << endl; } return 0; }

莫比乌斯反演

这里我就不班门弄斧了，献祭出我学习莫比乌斯反演的博客： http://blog.csdn.net/acdreamers/article/details/8542292

下面贴出一种常见的用莫比乌斯反演来解决的问题的代码：

//莫比乌斯反演求x小于等于m，y小于等于n，且gcd(x,y)为素数的对数； typedef long long LL; const int MAXN = 1000000; bool check[MAXN+10]; int prime[MAXN+10]; int mu[MAXN+10]; int tot; void Mobius(){ memset(check,false,sizeof(check)); mu[1]=1; tot=0; for(int i=2;i<=MAXN;i++){ if(!check[i]){ prime[tot++]=i; mu[i]=-1; } for(int j=0;j<tot;j++){ if(i*prime[j]>MAXN) break; check[i*prime[j]]=true; if(i%prime[j]==0){ mu[i*prime[j]]=0; break; } else{ mu[i*prime[j]]=-mu[i]; } } } } int main(){ int T; int a,b,c,d,k; Mobius(); scanf("%d",&T); for(int cas=1;cas<=T;cas++){ scanf("%d %d %d %d %d",&a,&b,&c,&d,&k); if(k==0){ printf("Case %d: 0\n",cas); continue; } b/=k; d/=k; if(b>d) swap(b,d); LL ans1=0; //粗算，求出莫比乌斯函数的值 for(int i=1;i<=b;i++){ ans1+=(LL)mu[i]*(b/i)*(d/i); } LL ans2=0; //排除b,d相同的情况 for(int i=1;i<=b;i++){ ans2+=(LL)mu[i]*(b/i)*(b/i); } ans1-=ans2/2; printf("Case %d: %lld\n",cas,ans1); } return 0; }

斐波那契数列（Fibonacci sequence）

通项公式：[((1+sqrt(5)/2)^n-((1-sqrt(5)/2)^n]/sqrt(5) 1. gcd(fib(n),fib(m))=fib(gcd(n,m)) 2. 如果fib(k)能被x整除，则fib(k*i)都可以被x整除 3. fib(0)+fib(1)+…+fib(n)=fib(n+2)-1 4. fib(1)+fib(3)+…+fib(2n-1)=fib(2n) 5. fib(2)+fib(4)+…+fib(2n)=fib(2n+1)-1 6. fib(0)^2+fib(1)^2+…+fib(n)^2=fib(n)*fib(n+1) 7. fib(0)-fib(1)+fib(2)-…+(-1)^n*fib(n)=(-1)^n*[fib(n+1)-fib(n)]+1 8. fib(n+m)=fib(n+1)*fib(m)+fib(n)*fib(m-1) 9. fib(n)^2=(-1)^(n-1)+fib(n-1)*fib(n+1) 10. fib(2n-1)=fib(n)^2-fib(n-2)^2 11. 3fib(n)=fib(n+2)+fib(n-2) 12. Fib(2n-2m-2)*[fib(2n)+fib(2n+2)]=fib(2m+2)+fib(4n-2m)[n>m>=-1&&n>=1]

卡特兰数（Catalan sequence）

前几项

1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700……

等价公式

h(n)=h(0)*h(n-1)+h(1)*h(n-2)+…+h(n-1)h(0)[n>=2] h(n)=h(n-1)*(4*n-2)/(n+1) h(n)=C(2n,n)/(n+1)[n=1,2,3…] h(n)=C(2n,n)-C(2n,n+1)[n=1,2,3…] h(n+1)=2(2n+1)/(n+2)*h(n) h(n+1)=sum(h(i)*h(n-i))[0<=i<=n] h(n)=sum(C(n,i)*C(n,i))/(n+1)[0<=i<=n] h(n)=4^n/(n^1.5*sqrt(pi))

应用

1. n个数的不同出栈序列 2. n个+1和n个-1构成2n项a1a2…an，其部分和满足a1+a2+a3…+an>=0,0<=k<=2n满足这个序列的个数等于第n个卡特兰数 3. 括号匹配的合法个数 4. 连乘的选择个数 5. n个节点的二叉树的树的形态个数 6. n个非叶子节点的满二叉树的形态数 7. n*n的矩阵中，从右下到左上角的走法 8. 凸n+2边形进行三角分割数 9. n层的阶梯切割为n个矩阵的切割法数目 10. 在一个2*n的格子内填入1到2n，使得每个格子内的数值都比其右边和上边的所有数值都小的情况数