排列组合总结
排列组合
一、定义
1. 排列
定义
从 n n n 个不同元素中，取出 m m m 个元素并对其进行排序的情况数为排列数，记作 A n m A^m_n Anm ；
计算
对于第 1 个元素，有 n n n 种选择，对于第 2 个元素，由于第一个元素已经占了一位，则有 n − 1 n - 1 n−1 种选择，以此类推，则第 n n n 个元素，有 n − m + 1 n - m + 1 n−m+1 中选择；
所以有， A n m = n ∗ ( n − 1 ) ∗ . . . ∗ ( n − m + 1 ) = n ! ( n − m ) ! A^m_n = n * (n - 1) * ... * (n - m + 1) = \frac{n!}{(n - m)!} Anm=n∗(n−1)∗...∗(n−m+1)=(n−m)!n! ；
2. 组合
定义
从 n n n 个不同元素中，取出 m m m 个元素不考虑顺序的情况数为排列数，记作 C n m C^m_n Cnm 或 ( m n ) \binom{m}{n} (nm) ；
计算
则在选出 m m m 个元素考虑排序的基础上去除掉因相同数字不同顺序的情况，即 m m m 个元素的全排列数量即可；
所以有， C n m = A n m m ! = n ! m ! ( n − m ) ! C^m_n = \frac{A^m_n}{m!} = \frac{n!}{m!(n - m)!} Cnm=m!Anm=m!(n−m)!n! ；
由于从 n n n 个元素中，取出 m m m 个元素不考虑顺序等同于从 n n n 个元素中，保留 n − m n - m n−m 个元素不考虑顺序；
所以有， C n m = C m n − m C^m_n = C^{n - m}_m Cnm=Cmn−m ；
二、小球与盒子模型
在此模型中，共有 3 个关键要素，即球 (元素) ，盒 (容器) 与是否允许空盒，最终求放的不同情况数，相同的球或盒意为不用考虑相同方法的不同排列情况，不同的球或盒反之；
以 n n n 个球， m m m 个盒子为例；
1. 球相同，盒不同，不空盒
由于要求没有空的盒子，则可想象为 n n n 个小球被 m − 1 m - 1 m−1 个隔板分为 m m m 段，将每段放入一个盒子里，即在 n − 1 n - 1 n−1 个空隙中选择 m − 1 m - 1 m−1 个空放隔板；
答案即为 C n − 1 m − 1 C^{m - 1}_{n - 1} Cn−1m−1 ；
2. 球相同，盒不同，可空盒
即为可使用 m m m 个虚拟球先放入每个箱子里，则即转化为种类 1 的情况，即在 n + m − 1 n + m - 1 n+m−1 个球的空隙中选择 m − 1 m - 1 m−1 个空放隔板；
答案即为 C n + m − 1 m − 1 C^{m - 1}_{n + m - 1} Cn+m−1m−1 ；
3. 球不同，盒相同，不空盒
由于球不相同，则不能使用排列组合解决;
则即为将 n n n 个球分成 m m m 个非空集合的方案数量，则考虑 DP ；
状态
d p [ i ] [ j ] dp[i][j] dp[i][j] 表示 i i i 个球 j j j 个盒的不同情况数；
初始化
d p [ 0 ] [ 0 ] = 1 dp[0][0] = 1 dp[0][0]=1 ；
转移
则对于每一个新放的球 i i i 可分情况讨论，
-
若原 i − 1 i - 1 i−1 个球放入了 j − 1 j - 1 j−1 个盒子中，则对于第 i i i 个球，由于不能空盒，则直接放入 j j j 盒子中，即有 d p [ i − 1 ] [ j − 1 ] dp[i - 1][j - 1] dp[i−1][j−1] 情况；
-
若原 i − 1 i - 1 i−1 个球放入了 j j j 个盒子中，则对于第 i i i 个球，可放入前 j j j 个盒子中的任意 1 个，即有 d p [ i − 1 ] [ j ] ∗ j dp[i - 1][j] * j dp[i−1][j]∗j 种情况；
将两种情况数量相加即可；
则有状态转移方程，
d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + d p [ i − 1 ] [ j ] ∗ j dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] * j dp[i][j]=dp[i−1][j−1]+dp[i−1][j]∗j
最终总方案数量则为 d p [ n ] [ m ] dp[n][m] dp[n][m] ；
4. 球不同，盒相同，可空盒
可空盒的情况即为将 n n n 个球放在 1 , 2 , 3 , . . . , m 1, 2, 3, ... , m 1,2,3,...,m 个箱子里的情况数的总和；
答案即为 ∑ i = 1 m d p [ n ] [ i ] \sum_{i = 1}^{m}dp[n][i] ∑i=1mdp[n][i] ；
5. 球不同，盒不同，不空盒
则可在球相同的情况的基础上将球进行全排列后放入盒子；
答案即为 d p [ n ] [ m ] ∗ m ! dp[n][m] * m! dp[n][m]∗m! ；
6. 球不同，盒不同，可空盒
则对于每一个球均有 m m m 个盒子选择；
答案即为 m n m^n mn ；
7. 球相同，盒相同，不空盒
由于球与盒均相同，则不能使用排列组合解决，考虑 DP ；
状态
d p [ i ] [ j ] dp[i][j] dp[i][j] 表示 i i i 个球 j j j 个盒的不同情况数；
初始化
使用循环赋初值即可；
-
i == j时，即每个盒子放一个球，则只有一种放法，则 d p [ i ] [ i ] = 1 dp[i][i] = 1 dp[i][i]=1 ； -
j == 1时，即只有一个盒子，则只有一种放法，则 d p [ i ] [ 1 ] = 1 dp[i][1] = 1 dp[i][1]=1 ；
转移
由于不能空盒，所以对于 d p [ i ] [ j ] dp[i][j] dp[i][j] 应先用 j j j 个球使盒子不为空，则对于原来的 i − j i - j i−j 个球可放到 1 , 2 , . . . , j 1, 2, ..., j 1,2,...,j 个箱子里；
则有状态转移方程，
d p [ i ] [ j ] = ∑ k = 1 j d p [ i − j ] [ k ] dp[i][j] = \sum_{k = 1}^{j}dp[i - j][k] dp[i][j]=k=1∑jdp[i−j][k]
注意 i , j i, j i,j 的范围， i ∈ [ 1 , n ] , j ∈ [ 2 , i ] i \in [1, n], j \in [2, i] i∈[1,n],j∈[2,i] ；
答案则为 d p [ n ] [ m ] dp[n][m] dp[n][m] ；
8. 球相同，盒相同，可空盒
则可先用 m m m 个球使盒子不为空，则对于剩下的 n − m n - m n−m 个球可做情况 8 处理；
答案即为 d p [ n − m ] [ n ] dp[n - m][n] dp[n−m][n] ；