第3章 问题求解(第1节 组合数学初步)

第三章11772[n]pnp亦延用至今。按此法，nPnn!。nHrm2nmnN＝m1＋m2＋m3＋…＋mnm1×m2×m3×…×mnn排列：从nm(m≤n)个元素，按照一定的顺序排成一列，叫做nmnPmn

(n组合：从nm(m≤n)nmnm(m≤n)个元素，C(n,k)P(5,5)种站法；4*4*P(4,4)种站法；P(5,5)+4*4*P(4,4)种站法。3*P(4,4)种方法。4*P(4,4)P(4,4)+3*P(4,4)+4*P(4,4)+P(3,3)*P(4,4)=312(1分析：（1）7P(7,7)*2-P(6,6)*2*2P(5,2)。763例：求方程的正整数解的个例：求方程的非负整数解的个数Catalan个三角形，设所有满足条件的方案数是，定义，求。我们试图找出，数列就是著名的Catalan数列，在组合数学的许多问题上都有很重要的应用Catalan数列的递推关系正如上式，再加上一点生成函数的知识就可以推导出它的通项公《IntroductoryCombinatoricsRichardA．Brualdi）78CatalanCatalan定理：n个+1和n个-1构成的2n项，并且其部分和满knCatalann+1n10，则称其为可接受的，否则个数。我们尝试计算出的值和的值以得到的值任意一个有n112n对于任意一个不可接受的数列中一定存在一个最小的k，使得Catalan（2由乘法原理可知这个问题满足递推关系（1Catalan分析：2、3n1n1总数（模型的转换希望读者认真思考Catalan有n2StirlingStirling数的相关知识完全略去，请有兴趣的读者参考《组合数学》《IntroductoryCombinatorics，RichardABrualdi）822S(n,k)k*S(n-1,k)S(n-1,k-1)；S(n,1)=1（n≥1），S(n,n)=1n-1nk*S(n-1,k)。StirlingS(6,3)n=3231312设表示i这个数在原来位置上的排列的集合，则错位排列的个现在我们来算n-1C(n,1)*(n-1)!=n!种情况。1k，k>1外的n-1个数的一个错位排列，方案数为。事实上在n较小的时候，计算更多的是通过递推关系而不是通项公式，但是通项公72（没有儿子的结点分析：设S表示二叉树的结点总数，表示有i个儿子的结点的个数。两次计算结果相互对照可以得出，于是例题的答案是8CAC化的技巧得到了的值。nn+12k+1令，如果n个笼子至少有个鸽子。k-11112证明：令表示第123此外，，而且由于每周下棋最多是12盘，即。因此，我们有此外，序列也是一个严格递增的序列154j+1，j+2，j+3，……，i21列T中的数之和恰好为9，那么n的最小值是 设表示前i个数的和，并规定，事实上原题要求出最小的n，使得存满足。于是我们可以把S数组看做鸽子，用不能同时取的一组（即9{20,29}{21,30}{22,31}{23,32}{24}{25}{26}n=18（S19）一定满足条件。n=17下不合法的序列：111111111011111111。n18SGf[N]Nf[N]可以转移f[N-1]到f[N-M]，f[N]就必胜否则必败。02，SG1。SG函数后我们之前递推判断必胜必败的规则也可用于#include<iostream>usingnamespacestd;constintNUM=5;intr(intn){inti;if(n<=NUM)returnn;for(i=1;i<=NUM;i++)if(r(n-i)<0)returni;return-1;}intintn; return0;}输入输出 4。Nim的SG函数为。根据SG函数的定义举一个简单的例子，axorb=cbxorc=aaxorc=b下面我们用反证法进行证明，假设存在一个状态的SG函数和它的一个后继状态的SG ，即除xorx数就是它本身，于是可知，从而x=0，与游戏者不能不取的条件矛盾，故原命Nim替x作为第k堆的石子数之后所有石子堆的石子数xor的值为0于是我们只需证明s1cxorx1所以我们甚至无需继续比较就可以得出结论：例题【NOIP2006普及组】现有5堆石子,石子数依次为3，5，7，19，50，甲乙两人轮 3^5^7^19^50=32>0，所以当前的状态是必胜态，先手有必胜策略。而石子的个数中，5061，50xor3218G=(V,E)是一个无向图，如果顶jiinA,jinB)，Gxy x(7-x)x12。顺序排列，每次可以交换任意两个元素，最少需要交换（）次。A．4B．5C．64，于是做一次交换。此时序列变成{-5，4，23，16，77，8，53，100}。然X1NX其中，用行列式可以表示k-1N-置换环的个数。ij，iji>