特殊处理方法

捆绑法

如果要求若干物品相邻，则可以将它们作为一个整体来进行计数。
$ABCDE$五个人要排队，$A$和$B$要相邻，$C$和$D$要相邻，求有多少种排列方法。

把$AB$看作一个整体，$CD$看成一个整体。再计算$AB$与$CD$内部的相对顺序。

方案数:$3!\times2!\times2!=24$。

插空法

如果要求若干物品两两不相邻，可以先将其他物品放好，然后将这些物品插入其中，进行计数。

$ABCDEFG$七个人要排队,$ABC$三个人两两不相邻，求方案数。

先将$DEFG$四个人排好，中间有$5$个空位（包括其两侧的）,$ABC$只能插入到空位中。

方案数：$4!\times A_5^3=1440$

隔板法

把个相同的苹果分给$k$个人，要求每个人至少分到一个，求方案数。

把$n$个苹果排成一排，在其中插入$k-1$块隔板，表示$k$个人分到的部分。

插隔板的方法与分苹果的方案是一一对应的，那么方案数为$\binom{n-1}{k-1}$

那么如果有人可以分到$0$个苹果呢？

我们给每个人多分一个苹果，使得每个人至少分配到一个苹果，在分配完之后再将每个人的苹果拿走一个。

那么方案数为$\binom{n+k-1}{k-1}$

隔板法与不定方程整数解问题

求不定方程$x_1+x_2+x_3+x_4+....+x_k=n$的解的个数，要求$x_i>d_i$

设$y_i=x_i-d_i>0$

那么有$y_1+y_2+y_3+y_4+....+y_k=n-(d_1+d_2+d_3+d_4+....+d_k)$

那么原问题就等价于“分苹果”的问题，即有$n-(d_1+d_2+d_3+d_4+....+d_k)$个苹果，分给$k$个人，要求每个人分到的苹果都大于$0$
那么方案数为。
$$ \binom{n-(d_1+d_2+d_3+d_4+....+d_k)-1}{k-1} $$

多重集的排列数与组合数

设$S=$ {$n_1a_1,n_2a_2,…,n_ka_k$}是由$n_1$个$a_1$，$n_2$个$a_2$，$n_k$个$a_k$组成的多重集。

多重集排列数

多重集$S$的全排列，不考虑相同的元素，其全排列个数为$(\sum_{i=1}^kn_i)!$，但是因为存在若干个相同的元素，因此要把相同元素的贡献给除掉。

对于每种排列的每个$a_{i,j}$，我们都可以从$n_i$个$a_i$中挑选任意一个，其对答案的贡献满足乘法原理为$n_i!$

因此方案数为
$$ \frac{(\sum_{i=1}^kn_i)!}{\prod_{i=0}^kn_i!} $$

多重集的组合数

求从多重集$S$中取$r$个元素的组合数的。

不考虑$n_i$个元素的限制，即从多重集$S’= ${$∞a_1,∞a_2,…,∞a_k$}中取$r$个元素的组合数。

我们设$a_i$取$x_i$个，那么原问题就等价于不定方程$\sum_{i=1}^kx_i=r\ (x≥0)$的解的个数。

等价于一共有$r$个苹果，分给$k$个人，可以有人拿$0$个苹果的方案数。

用隔板法计算，其方案为$\binom{r+k-1}{k-1}$

我们考虑第每个$a_i$的$n_i$的限制。

设不满足第$i$个限制的方案集合为$F_i$

那么答案即为$\binom{r+k-1}{k-1}-\left |\bigcup_{i=1}^nF_i \right |$

而$|\left |\bigcup_{i=1}^nF_i \right |$则可以用容斥原理计算。

类似[HAOI2008]硬币购物，我们先把$n_i+1$个拿出来，那么其余的我们不用管他，不管怎么安排，肯定都是非法方案。

显然有$\left|F_i\bigcap F_j \right|=\binom{r+k-1-(n_i+n_j+2)}{k-1}$

那么答案为
$$ \binom{r+k-1}{k-1}-\sum_{T \subseteq\{1,2,…,k\}}(-1)^{|T|-1}\binom{k+r-1-(\sum_{j \in T}n_j+|T|)}{k-1} $$