计数原理（习题）

计数原理（习题）

《组合数学（第五版）》第二章习题解答

示例： 对于性质 (a) 和 (b) 的四个子集的每一种，计数各数位取自数字 \(1,2,3,4,5\) 的四位数的个数：

  1. 各数位互不相同。

  2. 该数是偶数。

注意：这里有四个问题 (1) 无限制； (2) 性质 a 成立；(3) 性质 b 成立； (4) 性质 a,b 均成立。

解： (1) 根据乘法原理，每位均有五种选择，个数为 \(5^4=625\) 。

  1. 各位不同，为 \(5\) 的 \(4\) 排列，因此个位数为 \(P(5,4)=60\) 。

  2. 个位数是偶数，根据乘法原理，个数为 \(5^3\times2=250\) 。

  3. 各位数字不同且为偶数，先排个位数，有两种选择 (xxx2,xxx4) ，再依次确定其它位，共有 \(2\times4\times3\times2=48\) 种。

    ☐


示例： 如果所有同花色牌都放在一起，那么对于 \(52\) 张一副的牌有多少种排序方法？

解： 先排四个花色，再分别排每花色的十三张牌： \(4!\times(13!)^4\)

☐


示例： 确定作为下列各数的因子的 \(10\) 的最大幂（等价于末尾 \(0\) 的个数）。

  1. \(50!\) (2) \(1000!\)

解： 在阶乘结果中因子 \(2\) 的次数显然比 \(5\) 的次数多，所以计算 \(5\) 的因子次数就可以。

  1. \(1-50\) 中 \(5\) 的倍数有 \(10\) 个，\(25\) 的倍数有 \(2\) 个，所以 \(5\) 的因子次数为 \(10+2=12\) 。因此 \(50!\) 末尾有 \(12\) 个 \(0\) 。

  2. \(\dfrac{1000}{5}+\dfrac{1000}{25}+\dfrac{1000}{125}=248\)

    ☐


示例： 有多少个使下列性质同时成立且大于 \(5400\) 的整数？

  1. 各位数字互不相同。

  2. 数字 \(2\) 和 \(7\) 不出现

解： 使用数字 \(0,1,3,4,5,6,8,9\) 八个数字组成各位不同的数字

\(8\) 位数的个数为 \[7\times7\times6\times5\times4\times3\times2\times1\]

\(7\) 位数的个数为 \[7\times7\times6\times5\times4\times3\times2\]

\(6\) 位数的个数为 \[7\times7\times6\times5\times4\times3\]

\(5\) 位数的个数为 \[7\times7\times6\times5\times4\]

\(4\) 位数中，千位为 \(9,8,6\) 的个数为 \[3\times7\times6\times5\]

\(4\) 位数中，千位为 \(5\) 百位为 \(4,5,6,8,9\) 的个数为 \[5\times6\times5\]

共计：\(94860\) 个。

☐


示例： \(4\) 名男士和 \(8\) 名女士围着一张圆桌就座，如果每两名男士之间是两名女士，一共有多少种就座方法？

解： 认为经过旋转后一样的座次是同样的座次。让一名男士的位置固定，则另外三名男士的座次有 \(3!\) 种排布。

另外八名女士坐入男士间的空隙，有 \(8!\) 种排布。

因此共有 \(3!\times8!\) 种安排座次的方法。

☐


示例： \(6\) 名男士和 \(6\) 名女士围着一张圆桌就坐，如果男士和女士交替就坐，一共有多少种就座方法？

解： 先固定一位女士的座位，再排另外五位女士，有 \(5!\) 种方法。再排男士，有\(6!\) 种方法。因此共有 \(5!\times6!\) 种方法。

☐


示例： \(15\) 个人围着一张圆桌就座，如果 \(B\) 拒绝坐在 \(A\) 的旁边，一共有多少种就座方法？如果 \(B\) 只拒绝坐在 \(A\) 的右边，一共有多少种就座方法？

解： (1) 固定住 \(A\) 的位置。先排 \(A\) 左右两侧，有 \(13\times12\) 种方法。再排剩下 \(12\) 人，有 \(12!\) 种方法。共计 \(13\times12\times12!\) 种座次。

  1. 固定住 \(A\) 的位置。先排 \(A\) 的右侧，有 \(13\) 种排法。再排剩下 \(13\) 人。共计 \(13\times13!\) 种座次。

    ☐


示例： 从有 \(10\) 名男会员和 \(10\) 名女会员的一个俱乐部选出一个 \(5\) 人委员会。如果这个委员会至少要包含 \(2\) 位女士。有多少种方法形成这个委员会？此外，如果俱乐部里某位男士和某位女士拒绝进入该委员会一起工作，形成委员会的方式又有多少？

解： (1) 女士的人数选择为 \(2,3,4,5\) 人，对应男士的人数为 \(3,2,1,0\) 人。因此共有的方案数为： \[\binom{10}{2}\cdot\binom{10}{3}+\binom{10}{3}\cdot\binom{10}{2}+\binom{10}{4}\cdot\binom{10}{1}+\binom{10}{5}\cdot\binom{10}{0}\]

  1. 从上述方案数中减去该男士和该女士共同进入委员会的方案数即可。为了统计这类方案数，先把二人选进委员会，再从剩下的九男九女中选择三人，注意至少要选择一名女士以保证至少有两位女士进入委员会。因此方案数为：\[\binom{9}{1}\cdot\binom{9}{2}+\binom{9}{2}\cdot\binom{9}{1}+\binom{9}{3}\cdot\binom{9}{0}\]

相减得到： \[\binom{10}{2}\cdot\binom{10}{3}+\binom{10}{3}\cdot\binom{10}{2}+\binom{10}{4}\cdot\binom{10}{1}+\binom{10}{5}\cdot\binom{10}{0}-\binom{9}{1}\cdot\binom{9}{2}-\binom{9}{2}\cdot\binom{9}{1}-\binom{9}{3}\cdot\binom{9}{0}\]

示例： \(1\) 到 \(20\) 之间没有两个连续整数的 \(3\) 整数集合有多少个？

解： 从所有的 \(20\) 选 \(3\) 组合中去掉有连续整数的。

\(20\) 选 \(3\) 组合有 \(\dbinom{20}{3}\) 种。

连续三个整数的组合有 \(1,2,3\)，\(2,3,4\) ，… ，\(18,19,20\) 有 \(18\) 种。

仅有前两个整数连续的组合有 \(17+16+...+1=17\times9\) 种。（\(1,2\) 有 \(17\) 种，\(2,3\) 有 \(16\) 种，依此类推）

仅有后两个整数连续的组合也有 \(17\times9\) 种。

因此没有连续整数的 \(3\) 整数集合有 \(\dbinom{20}{3}-18-17\times18\) 种。

☐


示例： 从 \(15\) 个球员的集合种选出 \(11\) 个球员组成足球队，这 \(15\) 个人当中有 \(5\) 人只能踢后卫，有 \(8\) 人只能踢边卫，有二人既能踢后卫又能踢边卫。假设足球队有 \(7\) 个人踢边卫 \(4\) 个人踢后卫。确定足球队可能的组队方法数。

解： 令这两名全能型球员叫 \(A\) 和 \(B\) ，以二人的不同选位进行分类：

二人均不入选：\(\dbinom{5}{4}\cdot\dbinom{8}{7}=40\)

\(A\) 入选后卫 \(B\) 不入选：\(\dbinom{5}{3}\cdot\dbinom{8}{7}=80\)

\(B\) 入选后卫 \(A\) 不入选：同上

\(A\) 入选边卫 \(B\) 不入选：\(\dbinom{5}{4}\cdot\dbinom{8}{6}=140\)

\(B\) 入选边卫 \(A\) 不入选：同上

\(A\) 入选边卫 \(B\) 入选后卫：\(\dbinom{5}{3}\cdot\dbinom{8}{6}=280\)

\(A\) 入选后卫 \(B\) 入选边卫：同上

\(AB\) 均入选后卫：：\(\dbinom{5}{2}\cdot\dbinom{8}{7}=80\)

\(AB\) 均入选边卫：：\(\dbinom{5}{4}\cdot\dbinom{8}{5}=280\)

共计：\(40+80\times2+140\times2+280\times2+80+280=1400\) 。

☐


示例： 一所学校有 \(100\) 名学生和 \(3\) 个宿舍 \(A,B,C\) ，它们分别容纳 \(25\) ，\(35\) 和 \(40\) 人。

  1. 使得 \(3\) 个宿舍都住满学生有多少种方法？

  2. 假设 \(100\) 个学生中有 \(50\) 名男生和 \(50\) 名女生，而宿舍 \(A\) 全是男生宿舍，宿舍 \(B\) 全是女生宿舍，宿舍 \(C\) 男女兼收。有多少种方法可以为学生安排宿舍？

解： (a) 依次为三个宿舍挑出学生即可：\(\dbinom{100}{25}\cdot\dbinom{75}{35}\)

  1. 先挑男生宿舍和女生宿舍即可：\(C\) \(\dbinom{50}{25}\cdot\dbinom{50}{35}\)

    ☐


示例： 教室有两排座位且每排有 \(8\) 个座位。现有学生 \(14\) 人，其中 \(5\) 人总是坐在前排，\(4\) 人总是坐在后排。有多少种方法将学生分派到座位上？

解： 先把剩下的 \(5\) 个前后排不定的学生挑出前后排，再分别排列前后排

前排一个，后排四个：\(\dbinom{5}{1}\cdot6!\cdot8!\)

前排两个，后排三个：\(\dbinom{5}{2}\cdot7!\cdot7!\)

前排三个，后排两个：\(\dbinom{5}{2}\cdot8!\cdot6!\)

共计： \(\dbinom{5}{1}\cdot6!\cdot8!+\dbinom{5}{2}\cdot7!\cdot7!+\dbinom{5}{2}\cdot8!\cdot6!\)

☐


示例： \(6\) 个没有区别的车放在 \(6\times6\) 的棋盘上，使得没有两个车能够互相攻击的放置方法有多少？如果是\(2\) 个红车 \(4\) 个蓝车，那么放置方法又有多少？

解： (a) \(6!\)

  1. 先放置车，再挑两个涂蓝： \(\dbinom{6}{2}\cdot6!\)

    ☐


示例： \(2\) 个红车 \(4\) 个蓝车放在 \(8\times8\) 的棋盘上，使得没有两个车能够互相攻击的放置方法有多少？

解： 挑出两行不放车，在剩下的六行里逐行放置车：\(\dbinom{8}{2}\cdot P(8,6)\)

☐


示例： 确定 \(\{0,1,2,...,9\}\) 的循环排列的个数，其中 \(0\) 和 \(9\) 不在对面。

解： 确定 \(0\) 的位置，其对面的位置有 \(8\) 种选择，然后排列剩下\(8\) 个数字，共计 \(8\times8!\) 种排列方法。

☐


示例： 一群 \(mn\) 个人要被编入 \(m\) 个队，每队 \(m\) 个队员。

  1. 如果每队都有一个不同的名字，确定编队的方法数 \(A\)。

  2. 如果各队都没有名字，确定编队的方法数 \(B\)。

解： (a) 依次挑选 \(m\) 个队的队员，利用乘法原理得到 \[A={nm\choose m}\cdot {(n-1)m\choose m}\cdot {(n-2)m\choose m}\cdot ...\cdot{2m\choose m}\cdot{m\choose m}\]

  1. \(m\) 个队的任意置换都是相同的组队方式，所以方法数为 \[B=\dfrac{A}{n!}\]

    ☐


示例： \(5\) 个没有区别的车放在 \(8\times8\) 棋盘上，使得没有车能够攻击别的车而且第一行第一列都不空的放置方法有多少？

解法一 不考虑空行放置 \(5\) 个非攻击型车的方法 \(\dbinom{8}{5}^2\cdot5!\)

空第一行放置 \(5\) 个非攻击型车的方法 \(\dbinom{8}{5}\cdot\dbinom{7}{5}\cdot5!\)

空第一列放置 \(5\) 个非攻击型车的方法 \(\dbinom{7}{5}\cdot\dbinom{8}{5}\cdot5!\)

空第一行且空第一列放置 \(5\) 个非攻击型车的方法 \(\dbinom{7}{5}^2\cdot5!\)

根据容斥原理，总方法数为 \[\dbinom{8}{5}^2\cdot5!-\dbinom{8}{5}\cdot\dbinom{7}{5}\cdot5!\cdot2+\dbinom{7}{5}^2\cdot5!=147000\]

☐


解法二 将一个车放置在第一行和第一列的交叉点上，将剩下的四个车放入剩下 \(7\times7\) 的棋盘中，有 \(\dbinom{7}{4}^2\cdot4!\) 种方法。

将两个车分别放置在第一行和第一列上，控制住两行两列，有 \(7^2\) 种方法；再将剩下三个车放入剩下六行六列，有 \(\dbinom{6}{3}^2\cdot3!\) 种方法。

根据加法原理，总方法数为 \[\dbinom{7}{4}^2\cdot4!+\dbinom{6}{3}^2\cdot3!=147000\]

☐