组合计数.pdf

组合计数基础加法原理：一件事有两类做法，第一类有m种做法，第二类有n种做法，则这件事共有m?n种做法。加法原理：一件事分两步做，第一步有m种做法，第二步有n种做法，则这件事共有mn种做法。排列：m件不同的物品中选取n件排成一排，排列方式的数目是?!?!组合：m件不同的物品中选取n件，选取方法的数目是?!?!?!?组合与排列不同的是，组合不计次序。可重复的排列m种不同的物品中选取n个，可重复选取，排成一排，排法的数目是mn.证明：n个位置，每个位置有m个选择方式。m种不同的物品总共n个，第i种物品有ni个，n个物品排成一排，排列方式的数目是?!?!?!?!?,?,?证明：n个位置中选取n1个放置第1种，在剩下n?n1位置中选取n2个放置第2种，.，总选取方式有?!?!?!?!?!?!?!?!?!?!?!?!可重复的组合m种不同的物品中选取n个，可重复选取设第i种物品选取xi个，选法的数目等于以下方程的正整数解的个数。x1?x2?xm?n，xi?0.也等于放法的数目n个相同的球放入m个同的盒子解是?1?证明：问题相当于n个相同的球排成一排，在其间插入m?1个隔板，将它们分成m堆。m?n?1个位置中选n个放置球。00 1 001 1 00上面“0”相当于球，”1”相当于隔板。球放入盒子n个同的球放入m个同的盒子，使得第i个盒子放入ni个求，总放法有?!?!?!?!n个同的球放入m个相同的盒子，相当于基数为n的集合，划分成m个部分，允许部分为空。解这个问题需要用到容斥原，结果比较麻烦。n个相同的球放入m个相同的盒子，相当于将n分拆成m个非负数之和，计次序。结果记为pm?n?，它是重要的数论函数，问题非常困难。多项式定理?,?,?x1?x2?xm?n?x1?x2?xm?x1?x2?xm?x1?x2?xm?常系数齐次线性递推方程常系数k阶齐次线性递推方程形如?0函数xn?f?n?若满足上述方程，则称其为方程的解。方程的一般解称为通解，有k个待定系数。完全确定的解称为特解，要得到一个特解，需要k个初始值确定通解中的k个待定系数。如上递推方程的特征方程是?0如果特征方程有t个不同根r1r2,rt,根的重数分别是m1,m2,mt,则递推方程的通解是?其中，pi?n?是n的mi?1次多项式，系数待定。示例例.求解递推 xn?6xn?1?9xn?2,x0?1,x1?6.解：特征方程为：x2?6x?9?0,它有 2重根 3，故通解为xn?a?bn?3n代入初值得，a?1,3?a?b?6解得，b?1.故原方程的解是xn?1?n?3n常系数非齐次线性递推方程常系数k阶非齐次线性递推方程形如?非齐次方程的解可写成非齐次方程的一个特解加上齐次方程的通解。如果F?n?Q?n?rn，设r是特征方程的m重根?如果r不是特征方程的根，m?0?，则非齐次方程有形如?的特解，其中P?n?是与Q?n?次数相同的多项式，系数待定。示例例.求解递推 xn?3xn?1?2n,a1?3.解：特征方程是：x?3?0,根：3F?n?2n?2n1n,1是特征根，故方程有特解形如xn?a?bn?1n?a?bn代入原式得a?bn?3?a?b?n?1?2n?2a?3b?2b?2?n?0解得，a?3/2,b?1原方程通解为：xn?3/2?n?c3n代入初值得，?3/2?1?3c?3,c?11/6方程的解是：xn?3/2?n?11/6?3n容斥原理|A1A2 An|?|Ai|?|AiAj|?|AiAjAk|?1?n?1|A1A2 An|证明：只需证明并集中的每个元素在右边恰好计数一次即可。设元素a属于诸Ai中恰好k个，那么a在|Ai|中计数C?k,1?次，在|AiAj|计数C?k,2?次，在|AiAjAk|计数C?k,3?次，故a在等式右边计数C?k,1?C?k,2?C?k,3?1?k?1C?k,k?1?1?C?k,1?C?k,2?C?k,3?1?kC?k,k?1?1?1?k?1满射的个数集合A,B，|A|?m,|B|?n,m?n，求A到B的满射的个数。解：设B?b1,b2,bn?,BA?f|f:A B?,Pi?f|bif?A?.A到B的满射为：P1P2 Pn?P1P2 Pn?|BA|?nm,|Pi|?n?1?m,|PiPj|?n?2?m,|PiPjAk|?n?3?m,由容斥原理得|P1P2 Pn|?C?n,1?n?1?m?C?n,2?n?2?m?1?n?2C?n,n?1?|P1P2 Pn|?nm?C?n,1?n?1?m?C?n,2?n?2?m?1?n?1C?n,n?1?此数除以n!，即是：m个同的球放入n个相同的盒子，每个盒子至少一求，放法的数目。错位排列编号1,2,n的n个球放入编号1,2,n的n个盒子，每个球均放入与其编号同的盒子，此即错位排。解：设Pi?第i球恰好放入第i个盒子?全排列数为n!，|Pi|?n?1?!,|PiPj|?n?2?!,|PiPjAk|?n?3?!,由容斥原理得|P1P2 Pn|?C?n,1?n?1?!?C?n,2?n?2?!?1?n?1C?n,n?0!?n!/1!?n!/2!?1?n?1n!/n!|P1P2 Pn|?n!?n!/1!?n!/2!?1?n?1n!/n!?n!?1/2!?1/3!?1?n1/n!?1/e?n!e?1?1?1/1!?1/2!?1/3!?1?n1/n!?常用符号?