10.1 加法法则与乘法法则

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【加法法则:按互不重叠的类别计数】若结果集合分成两类 ,,两类分别有 个结果,则“属于A或属于B”共有 个结果。推广为两两不交的 ,有 。分类须无重无漏;若同一结果被分入两类,就不能直接相加,后续须用包含排斥消除重复。

【乘法法则:按步骤完成一次选择】若第一步有 种选择,每种第一步选择后第二步都恰有 种,依此类推第 步总有 种,则完整过程数为 。完全独立地从各集合取元素是这种规则的特例,更一般的分步选择可以有依赖,只要每个已有前缀的后续选择数相同即可。例如不放回的有序选取,各步可选数会逐步减少,仍适用乘法法则。

这里的“独立选择”是计数模型的说明,不是概率论中只检查两两事件独立就能推出联合独立。若不同前缀留下的选法数不同,应分别计数后相加,不能任取一个数相乘。

【例10.1.1:n元集上的关系和函数】设 ,求自反关系、对称关系、反对称关系、函数及双射的个数。

【解】(1)关系矩阵有 个0、1位置。自反性把对角线 个位置固定为1,其他 位自由,故共有 个自反关系。

(2)对称性要求 。每个对角位可独立取0、1,每个无序不同点对只须选择一次,共 个二选一,故对称关系数为 。不能把对称位置的两个矩阵元素当成两次独立选择。

(3)反对称性并不要求矩阵与转置不同,而是不同点之间不能同时有两个相反方向。每对 的 只可为 ;对角位不受这个限制,故数目为 。反对称不等于反自反,不能强迫对角线为0。

(4)函数 为每个输入选唯一输出,各有 种,共 个。双射须输出互不重复,各步为 种,共 个。空集到空集恰有一个函数且为双射;在计数语境中把相应 约定为1,且 。

同理,n元集上的一元运算数为 ,二元运算数为 ;若二元运算要求交换,只需为 个无序输入对选输出。若还要求幂等,则对角输入 固定,仅有 个自由输入对。使用这些式子前必须先说清运算的定义域、值域与附加条件。

【例10.1.2:分类IPv4地址的计数模型】教材采用历史分类地址示意:A类固定前缀0,另有7位网络标识、24位主机标识;B类固定10,另有14位网络、16位主机;C类固定110,另有21位网络、8位主机。按题目给定的简化限制,仅排除A类全1网络标识,并在各类中排除全0、全1主机标识,求此模型允许的地址数。

A0B10C11008162432
图10.1.1:三种32位格式;固定前缀、网络位、主机位分别标明长度

【解】三类前缀互斥,先按类相加;每类内部把网络选择与主机选择相乘:

因此题设模型总数为 。这三个数的用途是展示“分类相加、分步相乘”,不是当前Internet实际可供计算机使用的地址总数。

实际IPv4还包括私有、回环、链路本地及其他专用地址等限制,现行地址分配与路由采用CIDR前缀而非只按A、B、C三类计算;例如原题没有排除的全0网络部分也涉及专用地址。IPv4是32位、IPv6是128位,格式位数不能直接等同于可分配主机数。关于分类模型与无类前缀的区别,可参照RFC4632第2、3节:https://www.rfc-editor.org/rfc/rfc4632.html;专用地址见IANA登记:https://www.iana.org/assignments/iana-ipv4-special-registry/ 。