第六十七讲 几个重要的计数模型 讲义-2026年高中数学竞赛

第六十七讲 几个重要的计数模型

利用加法原理、乘法原理、排列与组合可以推导出许多重要的计数模型, 这些模型经常运用在各种问题之中, 已经成为计数中的“常识”。

1. 基本计数模型

以下列举的一些计数问题都是基本的计数模型, 应熟练掌握。

(1)  可重复排列: 设 是一个 元集合，一个 元有序组 ，其中 (可以相同),称为 的一个 元可重复排列。由乘法原理,一个 元集合的 元可重复排列的个数是 。

从一个 元集合 到一个 元集合 的映射 ,可等同于 的一个 元可重复排列: 将 的元素记为 ,则 等同于 , ,因此从 到 的映射个数为 。

(2)  正整数解:对固定的 ，计算方程

的正整数解 的个数,这里 是有序数组。

下面的方法称为 “隔板法”。取一列 个点,相邻两点之间称为一个空隙,从 个空隙中选取 个空隙,每个空隙中放入一块隔板,将 个点分成了 段,每段中至少有一个点。记从左至右各段中的点数为 ,这就产生了一组正整数解 。易知正整数解与选取隔板的方案一一对应,因此正整数解 , 的个数为 。

(3)  可重复组合: 设 是一个 元集合,从 中选取 个元素,允许重复但不考虑顺序,这 个元素称为 的一个 元可重复组合。设 ,确定一个 元可重复组合只需确定每个 被选取几次。设 被

选取了 次, ,则

的 元可重复组合一一对应于上式的非负整数解 。令 ,则 一一对应于

的正整数解 。由(2)中结论可知， 元集合 的 元可重复组合的个数为 。

(4)  递增序列:从集合 中选取 个数，构成严格递增的序列 ,这等同于选取 的一个 元组合,共有 种方法。从 中选取 个数,构成单调不减的序列 ,有多少种选法? 可作变量替换 ,则 成为 中的严格递增序列,且易知 与 一一对应。因此单调不减序列 的个数等于 。

注意:一个单调不减序列 也等同于 的一个 元组合(不考虑顺序的 元可重复组合可按单调不减顺序排列)，这也给出了(3)中可重复组合数计算的另一种方法。

(5)  圆排列:将物体排列在圆周上，假设经过圆周旋转可以变为相同的排列认为是同一类排列,在这样的等同关系下,同一类排列称为一个圆排列。将 个不同的物体排列在圆周上,若不考虑圆周的旋转,则相当于全排列,共有 ! 种。将旋转后能等同的排列分为一组,每组恰有 个排列,这 个排列被视作是同一个圆排列,故不同的圆排列个数为 。

例 1 有 10 个红球和 9 个蓝球, 同色的球无区别, 将它们封装入三个不同的盒子中, 要求每个盒子至少有一个红球和一个蓝球。求不同的分配方法数。

解 设三个盒子分别为 。对 ,设盒子 含有 个红球 个蓝球。从而 。每一种分配方法由正整数 , 所确定。利用隔板法可知 有 种, 有 种,再由乘法原理得分配方法数为 。

例 2 从 中选取一个 10 元子集,不包含连续两个正整数,共有几种选取方法?

解 一个 10 元子集等同于一个严格递增的序列 ,不含相邻整数则要求 ,对 成立。令 。则 是选自 中的严格递增的序列,并且 与 , 一一对应。因而满足要求的 10 元子集的个数为 。

例 3 有 8 对夫妇围坐在一张圆桌旁聚餐，要求夫妇两人相邻而坐。若经过圆周的旋转后入座方式相同则认为是同一种入座方式，求不同的入座方法数。

解 由于每一对夫妇必须相邻而坐, 安排座位时先看作一个人。这样先安排 8 个人的圆周排列(有 7 ! 种排列)，再将每个人替换为其所对应的一对夫妇(有两种方法)， 由乘法原理，共有 种不同的入座方法。

例 4 将 3 个红球、3 个黄球和3 个蓝球排列在圆周上，若经过圆周旋转后可以变为相同的排列认为是同一种排列。求不同的排列个数。

解 将圆周上的 9 个等分点按顺时针依次记为 。将 9 个球放在这 9 个点上,先不考虑圆周的旋转,则等同于多重元素的排列,排列个数为 1680。设 为将 旋转至 的旋转。对一个排列 ,记 为将 经过旋转 后所产生的排列。

对于每个排列 ,考虑 这 9 个排列。当且仅当红、黄、蓝三种颜色的球均构成正三角形时, 这 9 个排列中只有三种不同排列, 否则这 9 个排列互不相同。而红、黄、蓝均构成正三角形的排列有 3! =6 个(只需考虑 上红、黄、蓝的排列)。故在考虑圆周的旋转下,不同的排列个数为