完美信息教室讲义计数问题上

【SOL给可爱的第4届学生准备的讲义计数问题（上2...M-112...M-12...M-112...M-2MM-况，然后试图寻找其中的规律：第一项有N中可选方案；且无论第一何选择，第二项都有-1有-2种选择方案……无论前-1第i有i1。×NM1)，也就是!)÷NM!)宙了界？代数系统、半群、群、首先，由集合G与定义在其上的若干一元或二元运算f1、f2、...组成的多元<G,f1,f2,...>称作代数系统（注意，运算f定义在G上，是指运算的所有参数和取值范围都是G的子集，我们称这一特性为。于任何a,b,c∈G,f(f(a,b),c)=f(a,f(b,c))，则<G,f>是一个半群。再次，如果一个半群<G,f>中（有且仅有一个e∈G，对于任何a∈G，均有f(a,e)=f(e,a)=a，此时我们称e为幺元<G,f>是一个幺半群。还有，如果一个幺半群<G,F>的每一个元素（若a,b∈G，且f(a,b)=e，则bab=a-1）<G,f>是一个群。a,b∈Gf(a,b)=f(b,a)，则我们称<G,f>是一个交换群，又称作群另外，在一个半群<G,f>中，如果存xa∈Gf(x,a)=x，x为半群<G,f>的零元。。从群论观点看取RR,->以构造群<-{},>和<-{},÷（想素0？在取加法）或{x|x∈Z,0＜x＜m}（对于乘法）的形式（其中m为模数，其简记作Zm。特别注意，形如<,×>的代数系统并不一定是群；若m不是质数，则并非所有元素Z×在代数系统Z,×>中，我们以一个元素a为底数开始进行自乘；容易发现，在一些am=7且a=6，周期为6,1（长度为。我们定义，像a=3m=7一样，若底数a能够通过自乘遍历Zm中的每一个元（此时Z,+>0m)（而不是证明）费马小定理：若一个整数pmpZ×>p1。告诉我们，实数乘法群<R-{0},×>和模乘法群<Zm,×m>中的幺元都 1。然而<R-{0},×>中，x的逆元应为1/x；那在<Zm,×m>中呢我们还是根据逆元的定f(a,b)=a×mb=1，则b=a-1。联想数论中模线性方程：给定ax=1(modm)，已知a,m求解x；实际上，x就是a的乘法逆元，使用扩展欧几里得算法处理形如ax-my=1的线性方程即可直接求取。为了方便描述，我们形象地定义乘法逆元运算为另外值得一提的是，当m是一个质数时，代数系统<Zm,×m>构成群；我们可以使用费同时，若m不是质数，则绝不能用乘方法、只能使用扩展得算法求逆元（不存在生可以直接套用，而不必亲自枚举到世界（可能还枚举不完？）了。此处默认读者已经熟练掌握了加法原理、乘法原理排列排列数的含义为：从包含n个（互不相同）元素的集合中，取出m个构成的不同序不同”是指至少存在一个元素不相等，下同）的数目P(n,m)。引言中，我们用了从现在到宇宙那么久的时间得出了结论：组合组合数的含义为：从包含n个（互不相同）元素的集合中，取出m个构成的不同子集的数目，记C(n,m)。通项相包含m个元素的集合可以对应m!种不同的排列，因此我们可以写出C关于P的表达式：C(n,m)=P(n,m)/m!=n!/(m!(n-同时，如果不考虑进位的影响，11n的第i位即为C(n,i)递推相我们再从另外一个角度考虑。假设我们在一个包含1个元素的集合之中，选出了一个大小为-1的子集。现在我们在集合中加入一个新的元素，那么我们要选出的子集有两第m个元素恰为新加入的元素，方案数为C(n-1,m-1)C(n,m)=C(n-1,m-1)+C(n-1,m)。递推法适合小范围预处理；在O(n2)计算出组合鼠标后，便可以直接查表回答查询。另外，在三角中，第i行第j项等于第i-1行第j-1项和第j项之和，前两行共3项的值均为1。实际上不难发现，三角的初值与递推式与组合数是完全一致的n大家可能已经知道，(ab)nCniaibni。无论是通过数学组合、还 拆开号的方法，不难验证上述的正确性。这个被称作二项式定理。Stirling和思想上都是类似的；实际上，它们可以不过是对同一个问题的两个不同的角度罢了。第一类Stirling第一类Stirling数的含义为：将包含n个元素的集合划分为m个环（环由排列首尾相接而得，从环中任意位置起的排列均视为相同）的方案数，为方便起见记 S1(n,m)类似组合数的递推方式，假设我们已经将一个包n-1个元素的集合划分为m-1个环，现新的元素独成为一个环，情况数为S1(n-1,m-1)n-1种位置可供选择，情况数为(n-1)*S1(n-1,m)。S1(n,m)=S1(n-1,m-1)+(n-1)*S1(n-1,m)。第二类Stirling为方便起见记作S2(n,m)。同样类似组合数的递推方式，假设我们已经将一个包含n-1个元素的集合划分为m-个环，现在需要再加入一个元素。此时，有两种可能新的元素独成为一个集合，情况数为S2(n-1,m-1)mm*S2(n-1,m)。S2(n,m)=S2(n-1,m-1)+m*S2(n-1,m)。CatalanCatalan数是一个应用较为广泛的模型，为方H(n)。n对括号的匹配括号包含n个节点为的r20一个长度为n的序列进入堆栈并按任意顺序离开可以生成的序列个数为包含n个满足结合律的运算符的算式添加括号的递推以求n个节点的不同二叉树的数目”为例，我们试图Catalan数的递推式。n个节点的二叉树中，我们可以有如下选择：左子树包含0个节点、右子树包含n-1个节点，方案数为F(0)F(n-1)左子树包含1个节点、右子树包含n-2个节点，方案数为F(1)F(n-2)n)n-1个节点、右子树包含0个节点，方案数为F(n-1)F(0)。F(n)=∑F(i)F(n-1-i)。另外，我们再观察“包含n对括号的匹配括号序列数”这个例子首先，我们已经知道长度为n-1的序列的括号序列数为F(n-1)。这个序列是由2n-22-)=4-4n21（最终，我们可以得到另一种递推序列：F(n)=F(n-