组合数学浅谈初步.pptx

组合数学浅谈彭天翼

什么是组合数学证明存在性求出方案

组合和排列阶乘：n!从n个球选m个球（和选的顺序相关）的方案从n个球选m个球（和选的顺序无关）的方案

组合公式C[n][m]=(n!)/[(n-m)!*m!]1.递推公式？C[n-1][m-1]+C[n-1][m]=C[n][m]2.和(a+b)^n的关系?

杨辉三角11112113311464115101051从0开始标号（第i-1行的第j-1列）+（第i-1行的第j列）=第i行的第j列

杨辉三角11112113311464115101051观察每一行的对称性：C[n][m]=C[n][n-m]

杨辉三角11112113311464115101051观察每一行的增减性:C[n][0]=C[n][1]=C[n][2]=…=C[n][n/2]

杨辉三角11112113311464115101051每一行的和：C[n][0]+C[n][1]+C[n][2]…+C[n][n]=C[n][0]*1^0*1^(n-0)+C[n][1]*1^1*1^(n-1)…+.=(1+1)^n=2^n奇数项和=偶数项和：C[n][k]*(-1)^k*(1)^(n-k)Sum(C[n][k]*2^k)(0=k=n)=(2+1)^n

杨辉三角11112113311464115101051C[m][0]+C[m+1][1]+C[m+2][2]…+C[n][n-m]=?C[n+1][n-m]

杨辉三角11112113311464115101051C[m][m]+C[m+1][m]+C[m+2][m]…+C[n][m]=?C[n+1][n-m]

求不定方程解的整数解个数x1+x2+x3...+xn=m其中x1,x2,x3..xn=1且为整数问方案数。思想：用杆子分隔小球C[m-1][n-1]

拓展1.非负整数解的个数

拓展2.x1+x2+x3...+xn=m（正整数解）一种新的思路:令Si=S(i-1)+xi，S0=0，则SiS(i-1)，且Sn=m，即0S1S2S3…Sn=mSi的取值方案唯一地对应到xi的取值方案【正推，反推】Si的取值方案：C[m][n]

Fibonacci数列定义：F0=0,F1=1Fi=Fi-1+Fi-2

问题1Sn=S(n-1)+Fn则：Sn=F[n+2]–1证明：归纳法直觉：112358Fn-1Fn+1Fn+2

问题2怎么快速计算Fn？1.矩阵乘法+快速幂2.一个等价的做法：倍增Fn=a*F0+b*F1F(2n)=a*F(n)+b*F(n+1)….

问题3a=b1若b|a，则F[b]|F[a]证明：取模0123…bb+1b+2b+3…2b0112…0xx2x…0

卡特兰数列n个左括号，n个右括号，问不同括号序列的方案数

卡特兰数列n个左括号，n个右括号，问不同括号序列的方案数H[0]=1Dp:H[n]=ΣH[i-1]*H[n-i](1=i=n)通项公式：H[n]=C[2n][n]/(n+1)1,1,2,5,14,42....

变种n个元素的二叉查找树有多少种。凸n边形剖分成三角形的方法数。n个元素全部入栈并且全部出栈的所有可能顺序。

变种n*n棋盘从左下角走到右上角而不穿过主对角线的方案数。数学方法：C[2n][n]–C[2n][n+1]

容斥原理计算：|S1∪S2|=|S1|+|S2|-|S1∩S2||S1∪S2∪S3∪...Sn|=?

组合计数n个点的无向图，每个联通块都必须是链，问有多少种安排边的方法？

生成树计数

End