排列组合经典模型

捆绑法[要求元素相邻]

插空法[要求元素不相邻]

相同元素分组问题

每组最少一个元素 分为m组, 插入m-1 个插板

EX1

ABCDE 五人排队, AB 相邻 CD 相邻

求排列数

捆绑法

$3!A_2^2A_2^2$

EX2

ABCDEFG 七人排队, ABC 互不相邻

求排列数

隔板法

$4!A_5^3$

EX3

电视上有3个节目,保持原顺序,再插入2个新节目的方案数

隔板法+捆绑法

$A_4^2+C_4^1A_2^2$

EX4

n个小球放到m个盒子中,每个盒子不为空

求方案数

隔板法

$C_{n-1}^{m-1}$

数学公式
$$ x_1+x_2+\dots+x_m=n \quad(x_i\ge1) $$

EX5

n个小球放到m个盒子中,每个盒子可以为空

求方案数

数学公式
$$ \begin{align} x_1+x_2+\dots+x_m&=n \quad(x_i\ge0)\\ x_1+x_2+\dots+x_m+m&=n +m\quad(x_i\ge0)\\ (x_1+1)+(x_2+1)+\dots+(x_m+1)&=n+m\quad(x_i\ge0)\\ y_1+y_2+\dots+y_m&=n +m\quad(y_i\ge1)\\ \end{align} $$
转换成了上一题的模型 $C^{m-1}_{n+m-1}$

EX6

$x_1+x_2+\dots+x_m=n$

求方案数

数学公式

$C_{n+m-1}^{m-1}$

EX7

$x_1+x_2+\dots+x_m\le n$

求方案数

数学公式

转换为
$$ \begin{align} x_1+x_2+\dots+x_m&\le n\\ x_1+x_2+\dots+x_m+x_{m+1}&=n \end{align} $$

$C_{n+m}^{m}$

EX8

$x_1+x_2+x_3=13$ 其中 $x_1< 6,x_2< 6,x_3<6$

求方案数

数学公式

A: x1>=6 方案数

B: x2>=6 方案数

C: x3>=6 方案数

总方案数$C_{n+m-1}^{m-1}$ = $C_{15}^2$
$$ \begin{align} &C_{15}^2-|A\cup B\cup C|\\ =&C_{15}^2-\{|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|\}\\ =&C_{15}^2-\{3\times C_{9}^{2}-3\times C_{3}^{2}+0\}\\ =&C_{15}^2-3\times C_{9}^{2}+3\times C_{3}^{2}\\ \end{align} $$