排列组合部分及应用

大家好，欢迎来到IT知识分享网。

组合数

意义

$n$个元素中取出$m(m\le n)$个元素，不考虑元素排列顺序，满足条件的方案数记为$C_{n}^{m}$
代数意义：$(x+1)^p$展开后的系数

写法

$C_{n}^{m}$可以记为$nCm$或$C(n,m)$或$\binom{n}{k}$

公式

$$C_{n}^{m}=\frac{P_{n}^{m}}{m!}=\frac{n!}{m!(n-m)!}=C_{n}^{n-m}=C_{n-1}^{m-1}+C_{n-1}^{m}$$

特殊地 $C_{n}^{0}=1$

应用

·若有$k$类元素，每类个数无限，取$m$个元素的方案数为 $C_{m+k-1}^{m}$
·$x_1+x_2+x_3+……+x_n=m(n\le m)$正整数解的方案数
可以看成$m$个小球中插了$n-1$个隔板，而$m$个小球中有$m-1$个空可以插入隔板，所以方案数为$C_{m-1}^{n-1}$
·$x_1+x_2+x_3+……+x_n=m(n\le m)$整数解的方案数
把$x_i+1$，且$m+n$，等式仍成立，原题就转化成：
$x_1+x_2+x_3+……+x_n=m+n(n\le m)$正整数解的方案数
所以方案数为$C_{n+m-1}^{n-1}$
·$x_1+x_2+x_3+……+x_n\le m(n\le m)$正整数解的方案数
可以多用一个隔板把小球分割成两个部分，其中一边已经插入了$n-1$个隔板，若这个隔板插在小球的外围而非小球之间，则求出的恰好是$x_1+x_2+x_3+……+x_n=m(n\le m)$的情况，反之，若在两小球之间，则求出的是$x_1+x_2+x_3+……+x_n <m(n\le m)<="" script=""> 的情况，故可以转化为在 <span class="MathJax_Preview"></span> <span class="MathJax" id="MathJax-Element-29-Frame"> <span class="math" id="MathJax-Span-393" style="width: 1.176em; display: inline-block;"><span style="display: inline-block; position: relative; width: 0.909em; height: 0px; font-size: 125%;"><span style="position: absolute; clip: rect(1.976em 1000em 2.723em -0.477em); top: -2.557em; left: 0.003em;"><span class="mrow" id="MathJax-Span-394"><span class="mi" id="MathJax-Span-395" style="font-family: MathJax_Math-italic;">m</span></span><span style="display: inline-block; width: 0px; height: 2.563em;"></span></span></span><span style="border-left-width: 0.003em; border-left-style: solid; display: inline-block; overflow: hidden; width: 0px; height: 0.67em; vertical-align: -0.063em;"></span></span> </span> <script type="math/tex" id="MathJax-Element-29">m$个空中插入



n

$n$个隔板，答案为

Cnm
$C_m^n$

排列数

意义

$n$个元素中取出$m(m\le n)$个元素，考虑元素排列顺序，满足条件的方案数记为$P_{n}^{m}$

写法

$P_{n}^{m}$可以记为$A_{n}^{m}$或$nPm$或$nAm$或$A(n,m)$或$P(n,m)$

公式

$$P_{n}^{m}=\frac{n!}{(n-m)!}$$

特殊地 $P_n^0$成为 $n$的全排列

应用

·有$n$个元素，分为 $k(k\le n)$类，第 $i(1&lt;=i&lt;=k)$类元素个数为 $n_i$，这 $n$个元素的全排列为

$$\frac{n!}{\prod\limits_{i=1}^kn_i!}$$

错排

意义

$n$个小球放在$n$个位置，现在把$n$个小球打乱位置，使每个小球都不在最初的位置，满足条件的方案数记为$D_n$

公式

$$D_n=n!*(\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}……\frac{(-1)^n}{n!})=n!*\sum_{i=0}^n\frac{(-1)^i}{i!}$$

递推式

$$D_n=(n-1)*(D_{n-1}+D_{n-2})$$
特殊地 $D_0=1,D_1=0$
错排递推式推导： 传送门

卡特兰数

数列

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862……，令其第$n$项为$h_n$

公式

$$h_n=\sum_{i=0}^{n-1}h_i*h_{n-1-i}=\frac{h_{n-1}*(4*n-2)}{n+1}=\frac{C_{2n}^n}{n+1}=C_{2n}^{n}-C_{2n}^{n-1}$$

特殊地 $h_0=0,h_1=1$
关于卡特兰数： 传送门

应用

二项式定理

意义

二项式展开后的系数

公式

$$(a+b)^n=\sum_{i=0}^nC_n^i*a^{n-i}*b^i$$ 递推式：杨辉三角

未完\w/