组合计数

### 加法原理 若完成一件事的方法有$n$类，其中第$i$类方法包括$a_i$种不同的方法，且这些方法互不重合，则完成这件事共有$a_1+a_2+\cdots+a_n$种不同的方法。 ### 乘法原理 若完成一件事需要$n$个步骤，其中第$i$个步骤有$a_i$种不同的完成方法，且这些步骤互不干扰，则完成这件事共有$a_1\times a_2\times\cdots\times a_n$种不同的方法。 ### 排列数 从$n$个不同元素中依次取出$m$个元素排成一列，产生的不同排列的数量为： $\ $ ### $\qquad P^m_n=\dfrac{n!}{(n-m)!}=n\times (n-1)\times\cdots\times (n-m+1)$ $\ $ ### 组合数 从$n$个不同元素中取出$m$个组成一个集合$($不考虑顺序$)$，产生的不同集合数量为： $\ $ ### $\qquad C^m_n=\dfrac{n!}{m!(n-m)!}=\dfrac{n\times(n-1)\times\cdots\times(n-m+1)}{m\times(m-1)\times\cdots\times 2\times 1}$ $\ $ #### 性质 $\ $ $1.\ C^m_n=C^{n-m}_n$ $2.\ C^m_n=C^m_{n-1}+C^{m-1}_{n-1}$ $3.\ C^0_n+C^1_n+C^2_n+\cdots+C^n_n=2^n$ $\ $ ### 二项式定理 $\ $ ### $\qquad (a+b)^n=\sum\limits_{k=0}^nC^k_na^kb^{n-k}$ $\ $ ### 多重数的排列数 多重集是指包含重复元素的广义集合。设$S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$是由$n_1$个$a_1$，$n_2$个$a_2\cdots n_k$个$a_k$组成的多重集。$S$的全排列个数为： $\ $ ### $\qquad \dfrac{n!}{n_1!n_2!\cdots n_k!}$ $\ $ ### 多重集的组合数$($特殊情况$)$ 设$S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$是由$n_1$个$a_1$，$n_2$个$a_2\cdots n_k$个$a_k$组成的多重集，设整数$r\le n_i\ (\forall i\in [1,k])$。从$S$中取出$r$个元素组成一个多重集$($不考虑顺序$)$，产生的不同多重集的数量为： $\ $ ### $\qquad C^{k-1}_{k+r-1}$ $\ $ ### 多重集的组合数(一般情况) 设$S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}$是由$n_1$个$a_1$，$n_2$个$a_2$，$\cdots$，$n_k$个$a_k$组成的多重集。设$n=\sum\limits^k_{i=1}n_i$，对于任意整数$r\le n$，从$S$中取出$r$个元素组成一个多重集$($不考虑顺序$)$，产生的不同多重集的数量为： $\ $ ### $\qquad C_{k+r-1}^{k-1}-\sum\limits^k_{i=1}C_{k+r-n_i-2}^{k-1}+\sum\limits_{1\le i<j\le k}C_{k+r-n_i-n_j-3}^{k-1}-\cdots+(-1)^kC_{k+r-\sum_{i=1}^kn_i-(k+1)}^{k-1}$ $\ $ ### $Lucas$定理 若$p$是质数，则对于任意整数$1\le m\le n$，有： $\ $ ### $\qquad C^m_n\equiv C^{m\%p}_{n\%p}\times C^{\lfloor{m/p}\rfloor}_{\lfloor{n/p}\rfloor}\ (mod\ p)$ $\ $ ### $Catalan$数列 给定$n$个$0$和$n$个$1$，它们按照某种顺序排成长度为$2n$的序列，满足任意前缀中$0$的个数都不少于$1$的个数的序列的数量为： $\ $ ### $\qquad Cat_n=\dfrac{C^n_{2n}}{n+1}$ $\ $ #### 推论 以下问题都与$Catalan$数列有关： $1.\ n$个左括号和$n$个右括号组成的合法括号序列的数量为$Cat_n$。 $2.\ 1,2,\cdots,n$经过一个栈，形成的合法出栈序列的数量为$Cat_n$。 $3.\ n$个节点构成的不同二叉树的数量为$Cat_n$。 $4.\ $在平面直角坐标系上，每一步只能向上或向右走，从$(0,0)$走到$(n,m)$并且除两个端点外不接触直线$y=x$的路线数量为$2Cat_{n-1}$。