绪论：加法原理、乘法原理分类计数原理：做一件事，有n类办法，在第1类办法中有m1种不同的方法，在第2类办法中有m2种不同的方法，…，在第n类办法中有mn种不同的方法，那么完成这件事共有N=m1+m2+…+mn种不同的方法。 分步计数原理：完成一件事，需要分成n个步骤，做第1步有m1种不同的方法，做第2步有m2种不同的方法，…，做第n步有mn种不同的方法,那么完成这件事共有N=m1×m2×⋯×mn种不同的方法。 区别：分类计数原理是加法原理，不同的类加起来就是我要得到的总数；分步计数原理是乘法原理，是同一事件分成若干步骤，每个步骤的方法数相乘才是总数。 排列问题排列数从n个不同元素种取出m(m≤n)个元素的所有不同排列的个数，叫做从n个不同元素种取出m个元素的排列数，用符号Amn表示。 排列数公式Amn=n(n−1)(n−2)⋯(n−m+1)=n!(n−m)!,n,m∈N∗,并且m≤n 推导：把n个不同的元素任选m个排序，按计数原理分步进行： 取第一个：有n种取法； 根据分步乘法原理，得出上述公式。 排列数性质Amn=nAm−1n−1 可理解为“某特定位置”先安排，再安排其余位置。 Amn=mAm−1n−1+Amn−1 可理解为：含特定元素的排列有mAm−1n−1，不含特定元素的排列为Amn−1。 组合问题组合数从n个不同元素种取出m(m≤n)个元素的所有不同组合的个数，叫做从n个不同元素种取出m个元素的组合数，用符号Cmn表示。 组合数公式Cmn=AmnAmm=n(n−1)(n−2)⋯(n−m+1)m!=n!m!(n−m)!,n,m∈N∗,并且m≤n C0n=Cnn=1 证明：利用排列和组合之间的关系以及排列的公式来推导证明。 将部分排列问题Amn分解为两个步骤： 第一步，就是从n个球中抽m个出来，先不排序，此即组合数问题Cmn； 第二步，则是把这m个被抽出来的球排序，即全排列Amm。 根据乘法原理，Amn=CmnAmm，那么 组合数的性质Cmn=Cn−mn 可以理解为：将原本的每个组合都反转，把原来没选的选上，原来选了的去掉，这样就变成从n个元素种取出n−m个元素，显然方案数是相等的。 递推公式Cmn=Cmn−1+Cm−1n−1 可理解为：含特定元素的组合有Cm−1n−1，不含特定元素的排列为Cmn−1。还不懂？看下面。 Example 从1，2，3，4，5（n=5）中取出2（m=2）个元素的组合（Cmn）： 12 13 14 15 23 24 25 34 35 45 显然，这些组合中要么含有元素“1”，要么不含。
而总方案数等于上面两种情况方案数之和，即Cmn=Cmn−1+Cm−1n−1。 组合数求和公式C0n+C1n+C2n+⋯+Cnn=2n 我们感性认知一下，上面这个式子的左边表示什么呢？ 把从n个球中抽出0个球的组合数（值为1）、抽出1个球的组合数、抽出2个球的组合数、……、抽出n个球的组合数相加。 换句话说，就是从n个球中随便抽出一些不定个数球，问一共有多少种组合。 对于第1个球，可以选，也可以不选，有2种情况。 根据乘法原理，一共2×2×⋯×2⏟n个2相乘=2n种组合。 想要严谨的证明？数学归纳法：
也可偷懒地用二项式定理证明（其实二项式定理也是用数学归纳法证明的）： (a+b)n=n∑k=0Cknan−kbk 类似的公式（由Cmn=Cn−mn推导）： C0n+C2n+C4n+⋯=C1n+C3n+C5n+⋯=2n−1 杨辉三角这个神奇的图形和组合数、二项式定理密切相关。 杨辉三角可以帮助你更好地理解和记忆组合数的性质：
以下来自维基百科（我只是随便贴这） 二项式系数 二项式系数可排列成帕斯卡三角形。 二项式系数常见于各数学领域中，尤其是组合数学。事实上，可以被理解为从n个相异元素中取出k个元素的方法数，所以大多读作「n取k」。二项式系数的定义可以推广至n是复数的情况，而且仍然被称为二项式系数。 二项式系数亦有不同的符号表达方式，包括：C(n,k)、_nC_k、^nC_k、、[注3]，其中的C代表组合（combinations）或选择（choices）。很多计算机使用含有C的变种记号，使得算式只占一行的空间，相同理由也发生在置换数，例如写作P( n , k )。 {\displaystyle C_{n}^{k}}{\displaystyle C_{k}^{n}}{\displaystyle P_{k}^{n}} 定义及概念 {\displaystyle (1+x)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}={\binom {n}{0} }+{\binom {n}{1}}x+\cdots +{\binom {n}{n}}x^{n}} (x+y)^n=\sum_{k=0}^n\binom nk x^{nk}y^k 此数的另一出处在组合数学，表达了从n物中，不计较次序取k物有多少方式，亦即从一n元素集合中所能组成k元素子集的数量。 计算二项式系数 除展开二项式或点算组合数量之外，尚有多种方式计算的值。 \tbinom nk 递归公式 \binom nk = \binom{n-1}{k-1} + \binom{n-1}k \quad \forall n,k\in\N 其中特别指定： \binom n0 = 1 \quad \forall n\in\N\cup\{0\}, \binom 0k = 0 \quad \forall k\in\N. 此公式可由计算(1 + X ) n −1 (1 + X )中的X k项，或点算集合{1, 2, ..., n }的k个元素组合中包含n与不包含n的数量得出。 显然，如果k > n，则。而且对所有n，，故此上述递归公式可于此等情况下中断。递归公式可用作建构帕斯卡三角形。 \tbinom nk=0\tbinom nn=1 帕斯卡三角形(杨辉三角) 有关二项式系数的恒等式 关系式 阶乘公式能联系相邻的二项式系数，例如在k是正整数时，对任意n有： {\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}} \binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1} \binom {n-1}{k} - \binom{n-1}{k-1} = \frac{n-2k}{n} \binom{n}{k}. 两个组合数相乘可作变换： \binom ni \binom im=\binom nm \binom {nm}{im} \sum_{r=0}^n \binom nr = 2^{n} {\displaystyle \sum _{r=0}^{k}{\binom {n+r-1}{r}}={\binom {n+k}{k}}} {\displaystyle \sum _{r=0}^{nk}{\frac {(-1)^{r}(n+1)}{k+r+1}}{\binom {nk}{r} }={\binom {n}{k}}^{-1}} \sum_{r=0}^n \binom {dn}{dr}=\frac{1}{d}\sum_{r=1}^d (1+e^{\frac{2 \pi ri}{ d}})^{dn} \sum_{i=m}^n \binom {a+i}{i} = \binom {a+n+1}{n} - \binom {a+m}{m-1} \binom {a+m}{m-1} + \binom {a+m}{m} + \binom {a+m+1}{m+1} + ... + \binom {a+n} {n} = \binom {a+n+1}{n} F_n=\sum_{i=0}^{\infty} \binom {ni}{i} F_{n-1}+F_n=\sum_{i=0}^{\infty} \binom {n-1-i}{i}+\sum_{i=0}^{\infty} \binom {ni }{i}=1+\sum_{i=1}^{\infty} \binom {ni}{i-1}+\sum_{i=1}^{\infty} \binom {ni}{i} =1+\sum_{i=1}^{\infty} \binom {n+1-i}{i}=\sum_{i=0}^{\infty} \binom {n+1-i}{ i}=F_{n+1} |
|
|
