6 组合分析

鸽巢原理

没什么好说的。

\[ (x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k \]

\[ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \]

具有 n 个物体的集合允许重复的 r 排列数是 $n^r$

例：26 个英文大写字母可以组成多少个 r 位字符串？

答：$ 26^r$ 个。

星条原理（Stars And Bars）： $$ C(n+r-1,r) $$ 例 1：一家甜点店有 4 种不同类型的甜点,那么从中选6块甜点有多少种不同的方式？假定只关心甜点的类型，而不管是哪一块甜点或者选择的次序。

答：$C(4+6-1, 6) = 84$ 个选择。

例 2：$x_1 + x_2 + x_3 = 11$ 有多少个解？三者均是非负整数。如果加上限制条件 $x_1 \geq 1, x_2 \geq 2, x_3 \geq 3$ 呢？

例：重新排序单词 SUCCESS 中的字母能构成多少个不同的串？

答：$C(7,3)C(4,2)C(2,1)C(1,1)=420$。

例：有多少种方式把 52 张标准的扑克牌发给 4 个人使得每个人有 5 张牌？

答：$C(52,5)C(47,5)C(42,5)C(37,5) = 420$。

例：将 10 个不可辨别的球放人 8 个可辨别的桶里，共有多少种方法？

答：星条原理。$C(10 + 8 -1, \bold{10})$ → 8 种不同类型糕点，选出 10 个。

例：将 4 个不同的雇员安排在 3 间不可辨别的办公室，有多少种方式？其中每间办公室可以安排任意个数的雇员。

答：分类成无空办公室、1 间空办公室、2 间空办公室。

例：将同一本书的 6 个副本放到 4 个相同的盒子里，其中每个盒子都能容纳 6 个副本。有多少种不同的方式？

答：

$$ 6, (5,1) (4,2) (4,1,1) (3,3) (3,1,1,1) (3,2,1) (2,2) (2,2,1,1) $$ 共九种。