最后更新: 2025-01-22 09:01 查看: 236 次反馈能力测评会员8.2元/月赞助

多重集的排列和组合

6.4 多重集的排列和组合

在第 1 章介绍集合的概念时曾经指出：所谓多重集是一些对象（可重复出现）的全体，多重集中对象 $a_i$ 的出现的次数 $n_i$ 称为元素 $a_i$ 的重数。若多重集中不同元素个数为 $k$ 时，称该多重集为 $k$ 元多重集。如果多重集的元素个数是有限的，则称为有限多重集。若有限多重集 $S$ 有 $a_1, a_2, \cdots, a_k$ 共 $k$ 个不同元素，且 $a_i$ 的重数为 $n_i$ ，则可记为

$$
\left\{n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k\right\}
$$

例6．8 有限 3 元多重集 $\{a, a, a, a, b, b, c\}$ 可简记为 $\{4 \cdot a, 2 \cdot b, 1 \cdot c\}$ 。
如果 $k$ 元多重集的不同元素重复出现任意多数次时，可记为

$$
\left\{\infty \cdot a_1, \quad \infty \cdot a_2, \quad \cdots \infty \cdot a_k\right\}
$$

本节讨论多重集的排列和组合。
多重集的排列
定义6．4 设有限多重集 $S=\left\{n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k\right\}$ ，且 $n=n_1+n_2+n_k$ ，从 $S$ 中有序选取 $r$ 个元素称为 $S$ 的一个 $r$－排列 $(r \leqslant|S|=n)$ 。当 $r=n$ 时，称为 $S$ 的一个全排列。从 $k$ 元多重集 $S=\left\{\infty \cdot a_1, \infty \cdot a_2, \cdots, \infty \cdot a_k\right\}$ 中有序选取 $r$ 个元素我们也称为 $S$ 的一个 $r$－排列。

定理6．9 设 $k$ 元多重集 $S=\left\{\infty \cdot a_1, \infty \cdot a_2, \cdots, \infty \cdot a_k\right\}$ ，则 $S$ 的 $r$－排列数是 $k^r$ 。
证明：在构造 $S$ 的一个 $r$－排列时，每一位都有 $k$ 种选法。由于 $S$ 中的每种元素可任意次重复，因此每位的选择是相互独立的，由乘法原理得不同的排列数为 $k^r$ 。

例 6.9 求 4 位二进制字符串的个数。
解：此问题相当于求多重集 $\{\infty \cdot 0, \infty \cdot 1\}$ 的 4 －排列数，故为 $2^4=16$ 。

定理 6.10 设有限多重集 $S=\left\{n_1 \cdot a_1, n_2 \cdot a_2, \cdots, n_k \cdot a_k\right\}$ ，且 $n=n_1+n_2+n_k=|S|$ ，则 $S$的全排列数为

$$
\frac{n!}{n_1 \unrhd n_2 \rrbracket \cdots n_{k}!}
$$

证明：$S$ 的一个排列就是它的 $n$ 个元素的一个全排列，但 $S$ 中有 $n_1$ 个 $a_1$ ，在排列时要占据 $n_1$个位置，故对 $n_1$ 个 $a_1$ 的排列就是从 $n$ 个位置中无序选取 $n_1$ 个位

免费注册看余下 70%

非VIP会员每天5篇文章，开通VIP 无限制查看

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

高等数学测评 函数与极限一元函数微分学一元函数积分学微分方程空间向量与代数多元微分学多元积分学无穷级数

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

线性代数测评 行列式矩阵向量空间

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

概率统计测评 事件与概率一维随机变量与事件多维随机变量与事件随机变量的数字特征大数定律与中心极限定理统计量与抽样分布参数估计假设检验

上一篇：牛顿二项式定理

下一篇：容斥原理

本文对您是否有用？有用 (0) 无用 (0)