6.1.

[!QUESTION]
若码长为 100 的 0, 1 符号串, 信道是二元对称, 差错的概率为 0.001, 求满足下列条件的概率:
(1) 无差错;
(2) 恰好一个错;
(3) 恰好两个错;
(4) 多于两个错.

每个比特的传输是独立的, 因此错误比特数 服从二项分布 , 其中 , , 成功概率 (无差错) 为 . 二项分布的概率质量函数为:

(1) 无差错:

(2) 恰好一个错:

(3) 恰好两个错:

6.1.

[!QUESTION]
利用图解求下列问题的解.
(1)

(2)

(3)

(4)

Images generated by: [Linear programming grapher (two variables)](https: <//www.zweigmedia.com/utilities/lpg/index.html>)

5.1

[!QUESTION]
试判断下面每对拉丁方是否正交?

(1) 所有有序对均为唯一, 共 种, 无重复. 因此, 这对 3 阶拉丁方是正交的.
(2) (1,1), (2,2), (3,3), (4,4) 在第四行重复出现. 因此, 这对 4 阶拉丁方不正交.
(3) 所有 个有序对均不重复. 因此, 这对 5 阶拉丁方是正交的.

5.2

[!QUESTION]
试判断下列拉丁方是否为正交族?

1. (4.14.)

[!QUESTION]
一个正六面体的 6 个面用 g, r, b, y 四种颜色涂染, 求其中两个面用色 g, 两个面用色 y, 其余一面用 b, 一面用 r 的方案数.

使用母函数形式的 Pólya 定理, 对立方体面染色问题进行分析. 设颜色变量为 , 需计算满足 项的系数. 立方体对称群 的循环指标为:

1. 恒等置换 ()

展开 , 提取 项系数:

2. 绕面中心轴 180° 旋转 ()

母函数项为 , 需组合出 :

1. (4.15.)

[!QUESTION]
对一个正六面体的 8 个顶点, 用 y 和 r 两种颜色染色, 使其中有 5 个顶点用色 y, 其余 3 个顶点用色, 求其方案数.

根据 Cauchy-Frobenius 引理, 我们需要计算立方体对称群中每个元素的不动点数目, 并求其平均值.

1. 恒等变换 (1 个)

所有染色方案均被保留, 方案数为组合数:

2. 绕面中心轴旋转 90° 或 270° (共 6 个)

循环结构为两个 4- 循环. 由于每个循环颜色必须相同, 但总颜色数要求 5y 和 3r (奇数), 无法满足, 故不动点数为:

1. (4.1.)

[!QUESTION]
若群 的元素 均可表示为某一个元素 的幂, 即 , 则称这个群为循环群. 若群的元素交换律成立. 即 满足, , 则这个群为阿贝尔 (Abel) 群, 试证明所有的循环群都是阿贝尔群.

设 是一个循环群, 其生成元为 . 根据循环群的定义, 中的任意元素均可表示为 的整数次幂, 即对任意的 , 存在整数 使得 且 .

考虑 和 的乘积:

同理, 交换顺序后的乘积为:

由于整数加法满足交换律 (), 因此:

1. (3.42.)

[!QUESTION]
一组人有 1900 人, 每个人至少有 1327 个朋友, 试证其中四位, 使得彼此都是好朋友.

我们通过鸽巢原理分步证明:

1. 任选一人 A, 其朋友集合 S 至少有 1327 人.
2. 分析 S 内部的朋友关系: 每个成员 在 整个图 中至少有 1327 个朋友.
   • B 的朋友包含 A 和 S 外的至多 572 人 (因外部共有 人).
   • 因此, B 在 S 内部 至少有 个朋友.
3. 聚焦于一个成员 B 及其朋友: 任取 , 设其在 S 内的朋友集合为 T, .
4. 分析 T 内的共同朋友: 任取 ，C 在 S 内部 至少有 754 个朋友.
   • C 的朋友在 T 内至少有 人 (因 最多有 人).
   • 因此, C 在 T 中至少有 181 个朋友.
5. 应用鸽巢原理:
   • B 的朋友集合 T 有 754 人, C 在 T 中至少有 181 个朋友.
   • 必存在 , 使得 D 是 B 和 C 的共同朋友 (因 B 与 C 的共同朋友数 ).
   • 此时，A、B、C、D 两两均为朋友, 构成 .

1. (3.76.)

[!QUESTION]
试证欧拉函数 , 其中求和是对 的所有除数, 包括 和 进行的.

欧拉函数 表示 到 中与 互质的数的个数. 设 的质因数为 , 根据容斥原理:

莫比乌斯函数 定义为:

• 若 有平方因子;
• 若 是 个不同质数的乘积.
  结合容斥原理，上述求和可统一表示为：

\phi(n) = n \sum_{d | n} \frac{\mu(d)}{d}

1. (3.2.)

[!QUESTION]
求从 1 到 500 的整数中被 3 和 5 整除但不被 7 整除的数的个数.

被 3 和 5 整除的数即 15 的倍数. 设 为 1 – 500 中 15 的倍数集合, 为被 7 整除的数集合. 所求为 .

2. (3.10.)

[!QUESTION]
A, B, C 三种材料用作产品 I, II, III 的原料, 但要求 I 禁止用 B, C 作原料, II 不能用 B 作原料, III 不允许用 A 作原料, 问有多少种安排方案? (假定每种材料只做一种产品的原料).

1. (2.63.)

[!QUESTION]
求 位二进制数, 相邻两位不出现 11 的数的个数.

设 表示符合条件的 位二进制数的个数.

初始条件:

• 当 时, 可以是 0 或 1, 故 .
• 当 时, 排除 11 后剩下 00, 01, 10, 故 .