组合数学作业1
组合数学作业1
组合数学作业1
题 1.2
题目：5个女生，7个男生进行排列
(1) 若女生在一起有多少种不同的排列？
- 分析过程： 采用捆绑法。因为要求5个女生必须在一起，我们可以把这5个女生看作一个整体（一个“大元素”）。 这个“大元素”与剩下的7个男生一起进行全排列，相当于对 $1 + 7 = 8$ 个元素进行全排列，共有 $8!$ 种排法。 而在那个“大元素”内部，这5个女生自身也可以互相交换位置，共有 $5!$ 种排法。 根据乘法原理，总的排列数是这两步的乘积。
- 结果式子： $8! \times 5!$
(2) 女生两两不相邻有多少种不同的排列？
- 分析过程： 采用插空法。要使女生两两不相邻，我们可以先将7个男生排好。 7个男生的全排列数为 $7!$。 男生排好后，他们之间以及两端会形成 8 个“空位”（即
_男_男_男_男_男_男_男_）。 我们要让女生两两不相邻，就需要将5个女生插入这8个空位中的5个。从8个空位中选出5个并排列这5个女生的方法数为排列数 $A_8^5$（或记作 $P(8,5)$）。 根据乘法原理，总的排列数是男生排法与女生插空排法的乘积。 - 结果式子： $7! \times A_8^5$ （或写为 $7! \times \frac{8!}{3!}$）
(3) 两男生 A 和 B 之间正好有 3 个女生的排列有多少种？
- 分析过程： 这是一个多步骤的组合与捆绑问题。 第一步：从5个女生中选出3个，安排在男生A和B之间。这3个女生自身有顺序，方法数为 $A_5^3$。 第二步：男生A和男生B在两端可以互换位置（A…B 或 B…A），方法数为 $2! = 2$ 种。 经过这两步，我们构造好了一个特殊的“大元素”：【A - 3个特定女生 - B】（或 B 在前 A 在后）。 第三步：将这个“大元素”与剩下的人（一共12人，用掉了A、B和3个女生共5人，还剩 $12 - 5 = 7$ 人）一起进行全排列。现在总共有 $1(\text{大元素}) + 7(\text{剩余人}) = 8$ 个元素进行全排列，方法数为 $8!$。 根据乘法原理，将各步相乘。
- 结果式子： $A_5^3 \times 2! \times 8!$ （或写为 $C_5^3 \times 3! \times 2 \times 8!$）
题 1.5
题目：求 3000～8000 之间的奇整数的数目，而且没有相同的数字。
- 分析过程： 设该四位数为 $d_1 d_2 d_3 d_4$。 根据题意有以下限制：
- 在3000～8000之间：千位 $d_1 \in {3, 4, 5, 6, 7}$。
- 是奇数：个位 $d_4 \in {1, 3, 5, 7, 9}$。
- 没有相同的数字：所有位上的数字互不相同。 因为首位 $d_1$ 和末位 $d_4$ 的可选集合有交集 ${3, 5, 7}$，我们需要分情况讨论，以防选数字时发生冲突。我们根据千位 $d_1$ 是奇数还是偶数来分类： 情况一：千位是偶数。 千位 $d_1$ 只能选 ${4, 6}$，有 2 种选法。 此时个位 $d_4$ 可以从 ${1, 3, 5, 7, 9}$ 任选，因为首位是偶数，不可能与个位冲突，有 5 种选法。 剩下的百位 $d_2$ 和十位 $d_3$ 从剩下的 $10 - 2 = 8$ 个数字中任选并排列，有 $A_8^2$ 种选法。 情况一的方法数：$2 \times 5 \times A_8^2$。 情况二：千位是奇数。 千位 $d_1$ 只能选 ${3, 5, 7}$，有 3 种选法。 此时个位 $d_4$ 必须从奇数集合 ${1, 3, 5, 7, 9}$ 中选，但不能选已经被千位用掉的那个奇数，所以有 $5 - 1 = 4$ 种选法。 百位 $d_2$ 和十位 $d_3$ 同样从剩下的 8 个数字中任选并排列，有 $A_8^2$ 种选法。 情况二的方法数：$3 \times 4 \times A_8^2$。 最后将两种互斥情况相加。
- 结果式子： $(2 \times 5 + 3 \times 4) \times A_8^2 = (10 + 12) \times 8 \times 7$
题 1.20
题目：甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志占5位。试问有多少种方案？
- 分析过程： 代表团总共7人，要求甲单位4人，那么乙单位必须出 $7 - 4 = 3$ 人。 又要求代表团共有5名男同志。我们设甲单位出的4人中有 $x$ 名男同志，乙单位出的3人中有 $y$ 名男同志。 则需要满足：$x + y = 5$。 同时，受各单位人数限制，甲单位最多出4人所以 $0 \le x \le 4$；乙单位出3人所以 $0 \le y \le 3$。 满足上述条件的整数解 $(x, y)$ 只有三种情况：$(x=2, y=3)$，$(x=3, y=2)$，$(x=4, y=1)$。 下面针对这三种情况分别计算： 情况一：甲出 2男2女，乙出 3男0女。 选法为：$C_{10}^2 \times C_4^2 \times C_{15}^3 \times C_{10}^0$ 情况二：甲出 3男1女，乙出 2男1女。 选法为：$C_{10}^3 \times C_4^1 \times C_{15}^2 \times C_{10}^1$ 情况三：甲出 4男0女，乙出 1男2女。 选法为：$C_{10}^4 \times C_4^0 \times C_{15}^1 \times C_{10}^2$ 根据加法原理，总方案数为这三种情况之和。
- 结果式子： $(C_{10}^2 \cdot C_4^2 \cdot C_{15}^3 \cdot C_{10}^0) + (C_{10}^3 \cdot C_4^1 \cdot C_{15}^2 \cdot C_{10}^1) + (C_{10}^4 \cdot C_4^0 \cdot C_{15}^1 \cdot C_{10}^2)$
题 1.22
题目：求图中从0到P的路径数：（假设网格起点 O 为 (0,0)，根据图示数格子，A 点坐标为 (4,1)，B 点为 (5,1)，C 点为 (6,2)，终点 P 为 (8,4)） 注：在格点图中，从 $(x_1, y_1)$ 只能向右或向上走到 $(x_2, y_2)$，总步数为 $(x_2-x_1)+(y_2-y_1)$，其中包含 $(x_2-x_1)$ 步向右，路径数为 $C_{(x_2-x_1)+(y_2-y_1)}^{x_2-x_1}$。
(1) 路径必须过 A 点
- 分析过程： 路径分为两段：从 O 到 A，再从 A 到 P。 从 $O(0,0)$ 到 $A(4,1)$ 的路径数：$C_{4+1}^4 = C_5^1$。 从 $A(4,1)$ 到 $P(8,4)$ 的路径数：需向右走 $8-4=4$ 步，向上走 $4-1=3$ 步，路径数为 $C_{4+3}^4 = C_7^4$。
- 结果式子： $C_5^1 \times C_7^4$
(2) 路径必须过道路 AB
- 分析过程： 路径分为三段：从 O 到 A，从 A 到 B，从 B 到 P。 从 O 到 A：$C_5^1$ 种。 从 A 到 B：因为 A 和 B 只有一格之隔，只有向右走 1 步这 1 种路径。 从 $B(5,1)$ 到 $P(8,4)$：需向右走 3 步，向上走 3 步，路径数为 $C_{3+3}^3 = C_6^3$ 种。
- 结果式子： $C_5^1 \times 1 \times C_6^3$
(3) 路径必须过 A 点和 C 点
- 分析过程： 路径分为三段：从 O 到 A，从 A 到 C，从 C 到 P。 从 O 到 A：$C_5^1$ 种。 从 $A(4,1)$ 到 $C(6,2)$：需向右走 2 步，向上走 1 步，路径数为 $C_{2+1}^2 = C_3^2$ 种。 从 $C(6,2)$ 到 $P(8,4)$：需向右走 2 步，向上走 2 步，路径数为 $C_{2+2}^2 = C_4^2$ 种。
- 结果式子： $C_5^1 \times C_3^2 \times C_4^2$
(4) 道路 AB 封锁（但 A,B 两点开放）
- 分析过程： 利用容斥原理（正难则反）。 总的无限制路径数是从 $O(0,0)$ 到 $P(8,4)$：总共走 $8+4=12$ 步，其中 8 步向右，路径数为 $C_{12}^8$（或 $C_{12}^4$）。 在这些总路径中，减去“必须经过道路 AB”的非法路径即可。而“必须经过道路 AB”的路径数我们在第(2)问中已经求出。
- 结果式子： $C_{12}^8 - (C_5^1 \times C_6^3)$
题 1.25
题目：平面上有15个点，其中5点共线，此外不存在3点共线。
(1) 求至少过15个点中两点的直线的数目；
- 分析过程： 如果不考虑共线问题，15个点中任意选取2个点就可以决定一条直线，共有 $C_{15}^2$ 条。 但是，题目中说有5个特定点是共线的，这5个点中任意选2个本应该产生 $C_5^2$ 条直线，但实际上它们在同一条直线上，即这 $C_5^2$ 条直线坍缩成了 1 条唯一的直线。 因此，我们需要从总数中减去重复多算的 $C_5^2$ 条，然后再把这5个点共同确定的那 1 条直线加回来。
- 结果式子： $C_{15}^2 - C_5^2 + 1$
(2) 求由15个点中的3点组成的三角形的数目。
- 分析过程： 构成三角形需要任意不共线的3个点。如果不考虑共线情况，从15个点中任选3点的组合数为 $C_{15}^3$。 但是，那共线的5个点中，任意选出3个点都无法构成三角形（它们构成的是线段）。因此我们需要把这部分非法的选法减去。由于除这5点外没有其他3点共线，所以只需减去从这5点中选3点的情况数即可。
- 结果式子： $C_{15}^3 - C_5^3$
题 1.37
题目：给出等式 $\binom{n}{m}\binom{r}{0} + \binom{n-1}{m-1}\binom{r+1}{1} + \dots + \binom{n-m}{0}\binom{r+m}{m} = \binom{n+r+1}{m}$ 的组合意义。
- 分析过程（组合意义的文字描述）： 我们可以将该等式看作是“从 $n+r+1$ 个排成一排的不同元素中选出 $m$ 个元素”的过程。 等式右边：$\binom{n+r+1}{m}$ 直接表示从总共 $n+r+1$ 个元素中选出 $m$ 个元素的总方法数。 等式左边：我们按照“从右向左数，第 $r+1$ 个未被选中的元素的位置”来进行分类统计。（注：选出 $m$ 个，意味着有 $n+r+1-m$ 个元素未被选中）。 我们将这 $n+r+1$ 个元素从左到右排好。假设在这个序列中，存在某个元素，它是从左往右数第 $r+k+1$ 个元素。如果它是我们要找的“倒数第 $r+1$ 个未被选中的元素”，这就意味着：
- 在这个元素之后（它的右边），必须恰好有 $r$ 个未被选中的元素。由于右边总共有 $(n+r+1) - (r+k+1) = n-k$ 个元素，其中 $r$ 个未被选中，那么右边必然有 $(n-k) - r$ 个元素被选中。等等，更直观的设定是从左向右看： 修正视角的组合构造： 设从排成一列的 $n+r+1$ 个球中选取 $m$ 个。我们根据第 $r+1$ 个未被选中的球所处的位置分类。 假设第 $r+1$ 个未被选中的球的前面，恰好有 $k$ 个被选中的球（$k$ 的范围是 $0$ 到 $m$）。 那么这个球的位置必然是：$k$ (被选中的) $+ r$ (在它前面的未被选中的) $+ 1$ (它自己) $= r+k+1$。 此时，要完成 $m$ 个球的选择：
- 在这个位置之前的 $r+k$ 个球中，我们需要选出 $k$ 个，方法数为 $\binom{r+k}{k}$。
- 这个位置的球本身不被选中。
- 在这个位置之后，还剩下 $(n+r+1) - (r+k+1) = n-k$ 个球。为了凑齐 $m$ 个球，我们还需要在这些剩下的球中选出 $m-k$ 个，方法数为 $\binom{n-k}{m-k}$。 根据乘法原理，满足这种情况的选法有 $\binom{r+k}{k} \binom{n-k}{m-k}$ 种。 当 $k$ 从 $0$ 取到 $m$ 时，就遍历了所有互斥且穷尽的情况。 将这些项累加：$\sum_{k=0}^{m} \binom{r+k}{k}\binom{n-k}{m-k}$。 令 $k = m - i$ （或者观察等式左边），当 $k=0$ 时得 $\binom{r}{0}\binom{n}{m}$，当 $k=m$ 时得 $\binom{r+m}{m}\binom{n-m}{0}$。这与题目左边给出的多项式求和序列完全一致。
- 在这个元素之后（它的右边），必须恰好有 $r$ 个未被选中的元素。由于右边总共有 $(n+r+1) - (r+k+1) = n-k$ 个元素，其中 $r$ 个未被选中，那么右边必然有 $(n-k) - r$ 个元素被选中。等等，更直观的设定是从左向右看： 修正视角的组合构造： 设从排成一列的 $n+r+1$ 个球中选取 $m$ 个。我们根据第 $r+1$ 个未被选中的球所处的位置分类。 假设第 $r+1$ 个未被选中的球的前面，恰好有 $k$ 个被选中的球（$k$ 的范围是 $0$ 到 $m$）。 那么这个球的位置必然是：$k$ (被选中的) $+ r$ (在它前面的未被选中的) $+ 1$ (它自己) $= r+k+1$。 此时，要完成 $m$ 个球的选择：
- 结论简述： 该等式的组合意义是将“从 $n+r+1$ 个物品中选取 $m$ 个物品”的所有方案，按照“第 $r+1$ 个未被选中的物品之前有多少个已被选中的物品（设为 $k$ 个，$k \in [0, m]$）”进行分类统计求和。
题 1.45
(1) 在 $2n$ 个球中，有 $n$ 个相同。求从这 $2n$ 个球中选取 $n$ 个的方案数。
- 分析过程： 因为总共有 $2n$ 个球，其中 $n$ 个完全相同，那么另外的 $(2n - n) = n$ 个球必然是两两互不相同的。 我们需要从中选出 $n$ 个球。可以根据“从那 $n$ 个不相同的球中选了多少个”来进行分类： 假设我们从 $n$ 个不同的球中选了 $k$ 个（$0 \le k \le n$），选法有 $C_n^k$ 种。 为了凑齐 $n$ 个，剩下的 $n-k$ 个必须从那 $n$ 个相同的球中选取。因为这 $n$ 个球是相同的，选 $n-k$ 个的方法永远只有 1 种。 所以选了 $k$ 个不同球的方案数就是 $C_n^k \times 1$。 把 $k$ 从 $0$ 到 $n$ 的所有情况相加，根据二项式定理的推论：$\sum_{k=0}^{n} C_n^k = 2^n$。
- 结果式子： $\sum_{k=0}^{n} C_n^k \times 1 = 2^n$
(2) 在 $3n+1$ 个球中，有 $n$ 个相同。求从这 $3n+1$ 个球中选取 $n$ 个的方案数。
- 分析过程： 同理，有 $n$ 个相同球，剩下 $(3n+1) - n = 2n+1$ 个互不相同的球。 我们要选 $n$ 个球。假设从不同的球中选了 $k$ 个（$0 \le k \le n$），选法有 $C_{2n+1}^k$ 种。 剩下的 $n-k$ 个由相同的球补齐，选法始终为 1 种。 因此总方案数为 $\sum_{k=0}^{n} C_{2n+1}^k$。 根据二项式系数对称性 $C_{2n+1}^k = C_{2n+1}^{(2n+1)-k}$，可以知道前一半的和与后一半的和相等： $\sum_{k=0}^{n} C_{2n+1}^k = \frac{1}{2} \sum_{k=0}^{2n+1} C_{2n+1}^k = \frac{1}{2} \times 2^{2n+1} = 2^{2n}$。
- 结果式子： $\sum_{k=0}^{n} C_{2n+1}^k = \frac{1}{2} 2^{2n+1} = 2^{2n}$
题 1.50
(1) 在由 5 个 0，4 个 1 组成的字符串中，出现 01 或 10 的总次数为 4 的字符串，有多少个？
- 分析过程： “出现 01 或 10”代表字符发生了一次反转交替。出现 4 次交替，意味着这 9 个字符被分成了 $4 + 1 = 5$ 个相同字符组成的“段（block）”。 既然有 5 个段，且必须是 0 和 1 交替出现，那么段的排列只有两种模式：
- 模式A：0段 - 1段 - 0段 - 1段 - 0段。此模式下，有 3 个“0段”和 2 个“1段”。 我们将 5个0 分成 3个非空的段，使用“隔板法”：5个0中间有4个空，插入2块板，方法数为 $C_{5-1}^{3-1} = C_4^2$。 我们将 4个1 分成 2个非空的段，插入1块板，方法数为 $C_{4-1}^{2-1} = C_3^1$。 模式A的总数：$C_4^2 \times C_3^1 = 6 \times 3 = 18$。
- 模式B：1段 - 0段 - 1段 - 0段 - 1段。此模式下，有 2 个“0段”和 3 个“1段”。 5个0分2段：$C_{5-1}^{2-1} = C_4^1$。 4个1分3段：$C_{4-1}^{3-1} = C_3^2$。 模式B的总数：$C_4^1 \times C_3^2 = 4 \times 3 = 12$。 总数是两种模式相加。
- 结果式子： $C_4^2 \times C_3^1 + C_4^1 \times C_3^2 = 18 + 12 = 30$
(2) 在由 $m$ 个 0，$n$ 个 1 组成的字符串中，出现 01 或 10 的总次数为 $k$ 的字符串，有多少个？
- 分析过程： 推广(1)的思路，出现 $k$ 次交替，意味着字符串被划分为 $k+1$ 个段。我们要根据 $k$ 的奇偶性分类讨论： 情况一：$k$ 是偶数。 设 $k = 2r$。此时共有 $2r+1$ 个段。 模式A：开头的段为0。那么有 $r+1$ 个“0段”，$r$ 个“1段”。 分段方法数：$C_{m-1}^{r} \times C_{n-1}^{r-1}$。 模式B：开头的段为1。那么有 $r$ 个“0段”，$r+1$ 个“1段”。 分段方法数：$C_{m-1}^{r-1} \times C_{n-1}^{r}$。 总数 = $C_{m-1}^{k/2} C_{n-1}^{k/2 - 1} + C_{m-1}^{k/2 - 1} C_{n-1}^{k/2}$ 情况二：$k$ 是奇数。 设 $k = 2r - 1$。此时共有 $2r$ 个段。 因为段数是偶数，无论以 0 还是 1 开头，最终都会有 $r$ 个“0段”和 $r$ 个“1段”。 将 $m$ 个 0 分为 $r$ 段的方法数为 $C_{m-1}^{r-1}$。将 $n$ 个 1 分为 $r$ 段的方法数为 $C_{n-1}^{r-1}$。 由于可以是 0 段开头或 1 段开头，共有 2 种模式。 总数 = $2 \times C_{m-1}^{r-1} \times C_{n-1}^{r-1} = 2 C_{m-1}^{(k-1)/2} C_{n-1}^{(k-1)/2}$。
- 结果式子： 当 $k$ 为偶数时： $C_{m-1}^{k/2} \cdot C_{n-1}^{k/2 - 1} + C_{m-1}^{k/2 - 1} \cdot C_{n-1}^{k/2}$ 当 $k$ 为奇数时： $2 \cdot C_{m-1}^{(k-1)/2} \cdot C_{n-1}^{(k-1)/2}$
题 1.55
题目：偶数位的对称数，即从左向右的读法与从右向左的读法相同，如 3223。试证这样的数可被 11 整除。
- 分析（证明）过程：
- 一个数能被 11 整除的判定特征是：其奇数位上数字之和与偶数位上数字之和的差，必须能被 11 整除（或等价地说，各位数字的交替和能被 11 整除）。
- 设这个对称数为 $2n$ 位，其数字从左到右记为 $a_1, a_2, \dots, a_n, a_{n+1}, \dots, a_{2n}$。
- 因为是对称数，所以它满足镜像对称关系，即第一位等于最后一位，第二位等于倒数第二位…… 也就是 $a_1 = a_{2n}, a_2 = a_{2n-1}, \dots, a_k = a_{2n+1-k}$（对于 $1 \le k \le n$）。
- 我们来计算这个数的各位数字交替和 $S$： $S = a_1 - a_2 + a_3 - a_4 + \dots + (-1)^{2n-2}a_{2n-1} + (-1)^{2n-1}a_{2n}$
- 将对称位置的项两两分组： 考察第 $k$ 项 $a_k$ 和与其对称的第 $2n+1-k$ 项 $a_{2n+1-k}$。 在交替和中，$a_k$ 的符号由 $(-1)^{k-1}$ 决定； 而 $a_{2n+1-k}$ 的符号由 $(-1)^{(2n+1-k)-1} = (-1)^{2n-k} = (-1)^{-k} = -(-1)^{k-1}$ 决定。
- 由于 $a_k = a_{2n+1-k}$，且它们在交替和式子中带的符号正好是一正一负（完全相反）。 所以每一对对称位置的数字在交替求和时都会相互抵消为 0，即 $(-1)^{k-1}a_k + (-1)^{2n-k}a_{2n+1-k} = 0$。
- 因此，整个 $2n$ 位对称数的交替和 $S = 0$。因为 0 能被 11 整除，所以该偶数位的对称数必能被 11 整除。证明完毕。
题 1.57
题目：$n$ 个人分别沿着两张圆桌坐下，一张 $r$ 个人，另一张 $n-r$ 个人，试问有多少种不同的方案？
- 分析过程： 根据题目“分别沿着两张圆桌”可以判断，两张桌子是可以区分的（因为各坐 $r$ 和 $n-r$ 人，即使在 $r = n/2$ 时通常语境下两张实体桌子也是独立存在的）。 第一步：分组。从 $n$ 个人中选出 $r$ 个人去坐第一张桌子，剩下的 $n-r$ 个人去坐第二张桌子。选人的方法数为 $C_n^r$。 第二步：排座位。这被选出的 $r$ 个人围着第一张圆桌坐，圆排列的方法数为 $(r-1)!$。 第三步：剩下的 $n-r$ 个人围着第二张圆桌坐，圆排列的方法数为 $(n-r-1)!$。 根据乘法原理，将上述三个步骤相乘即得总方案数。
- 结果式子： $C_n^r \times (r-1)! \times (n-r-1)!$ （化简后可写为 $\frac{n!}{r(n-r)}$）
本文由作者按照 CC BY 4.0 进行授权