排列组合学习笔记-JZTXT

加法原理

有$n$类办法,$a_i(1 \le i \le n)$代表第$i$类方法的数目。那么共有$S=a_1+a_2+\cdots+a_n$种方法

乘法原理

分$n$个步骤,$a_i(1 \le i \le n)$代表第$i$个步骤的方法数目。那么共有$S=a_1\times a_2 \times\cdots\times a_n$种方法

排列数

从 $n$ 个不同元素中，任取 $m $（ $m\leq n$ ，$m,n$ 均为自然数）个元素按照一定的顺序排成一列，叫做从 $n$ 个不同元素中取出 $m$ 个元素的一个排列；从 $n$ 个不同元素中取出 $m$ ( $m\leq n$ ) 个元素的排列的个数，叫做从 $n$ 个不同元素中取出 $m$ 个元素的排列数

记作$A_n^m$

\[A_n^m=n\times(n-1)\times(n-2)\times\cdots\times(n-m+1)=\frac{n!}{(n-m)!} \]

特殊的，对于$A_n^n$称作全排列

\[A_n^n=n\times(n-1)\times(n-2)\times\cdots\times2\times1=n! \]

组合数

从 $n$ 个不同元素中，取 $m \leq n$ 个元素组成一个集合称作从 $n$ 个不同元素中取出 $m$ 个元素的一个组合；从 $n$ 个不同元素中取出 $m \leq n$ 个元素的所有组合的个数称作从 $n$ 个不同元素中取出 $m$ 个元素的组合数

记作$\dbinom{n}{m}$或者$C_m^n$

\[C_m^n=\dbinom{n}{m}=\frac{A_m^n}{m!}=\frac{n!}{m!\times (n-m)!} \]

公式是这样推出来的

首先，排列数考虑顺序而组合数不考虑顺序

而我们可以很轻易的用全排列推出来$A_m^m=m!$

而这在组合数中只记作一种情况

那么就是说只要在$A_m^n$的基础上$÷(m!)$即可得到答案

排列数性质

\[\dbinom{n}{m}=\dbinom{m-n}{m}\tag{1} \]

\[\dbinom{n}{k} = \frac{n}{k} \dbinom{n-1}{k-1}\tag{2} \]

\[\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}\tag{3} \]

\[\dbinom{n}{0}+\dbinom{n}{1}+\cdots+\dbinom{n}{n}=\sum_{i=0}^n\dbinom{n}{i}=2^n\tag{4} \]

二项式定理

该定理给出两个数之和的整数次幂诸如展开为类似项之和的恒等式。

二项式定理可以推广到任意实数次幂，即广义二项式定理

\[(a+b)^n=\dbinom{n}{0}\times x^n y^0+\dbinom{n}{1}\times x^{n-1} y^1+\cdots+\dbinom{n}{n-1}\times x^1 y^{n-1}=\sum_{i=0}^n\dbinom{n}{i}\times a^{n-i}\times b^i \]

矩阵形式(根据$\mathrm{K8He}$所说没啥用，$\mathrm {stO}\ \mathrm {K8He}\ \mathrm {Orz}$)

\[(a+b)^n=[a^0\cdots a^n]\left[\begin{matrix} \binom{n}{0}&&\\&\cdots&\\&&\binom{n}{n}\\\end{matrix}\right]\left[\begin{matrix} &&1\\&\cdots&\\1&&\\\end{matrix}\right]\left[\begin{matrix} 1\\\cdots\\1\\\end{matrix}\right]\]