离散数学-2
设 a1 < a2 < … < an 是 n 个实数，A = {a1, …, an}，φ 是 A 到 A 的可逆映射。如果 a1 + φ(a1) < a2 + φ(a2) < … < φ(an) + an，试证：φ = IA。
证 设 φ(a1) ≠ a1，则由 φ 是可逆的，故为一一对应，从而必有 j, j > 1，使 φ(aj) = a1。
于是，对任何正整数 i < j，有 ai + φ(ai) < aj + φ(aj)。但由于 ai ≥ a1，φ(aj) = a1，所以
a1 + φ(a1) ≤ ai + φ(ai) < φ(aj) + aj = aj + a1,
故 φ(ai) < aj，从而 φ(ai) = ak, k < j。这表明当 φ(a1) = ap 时，p < j。于是，对任意的 i, i < j，φ(ai) ∈ {a1, a2, …, aj − 1}。
从而 φ 限制在 {a1, a2, …, aj − 1} 上时，φ 也是一个一一对应(若不是,则要么违反在整个定义域上的可逆性,要么违反上面的大小限制)，于是有 i，使 φ(ai) = a1，矛盾。故 φ(a1) = a1。
类似可证 φ(a2) = a2, …, φ(an) = an，即 φ = IA。[证毕]
注意：如 A 为无穷集，则命题不真，例如 A = ℕ 时，令 φ(n) = n + 1，则
1 + φ(1) = 3 < φ(2) + 2 = 5 < 3 + φ(3) = 7…, φ ≠ IA
设 u1, u2, ⋯, umn + 1 是一个两两不相交的整数构成的数列，则必有长至少为 n + 1 的递增子序列或有长至少为 m + 1 的递减子序列。
证 令 A = {u1, u2, ⋯, umn + 1}，则 |A| = mn + 1。
设以 ui 为首项的最长递增子序列的长度为 ℓi+，
设以 ui 为首项的最长递减子序列的长度为 ℓi−。
反证法：假设题中结论不成立，则 ℓi+ ≤ n, ℓi− ≤ m, i = 1, 2, 3, ⋯, mn + 1。
令 φ : A → {1, 2, ⋯, n} × {1, 2, ⋯, m}, ∀ui ∈ A, φ(ui) = (ℓi+, ℓi−)，则 φ 是单射。
实际上，∀ui, uj ∈ A 且 ui ≠ uj(i < j)，则
若 ui > uj，则 ℓi− > ℓj−，所以 (ℓi+, ℓi−) ≠ (ℓj+, ℓj−)；
即 φ(ui) ≠ φ(uj)。
若 ui < uj，则 ℓi+ > ℓj+，所以 (ℓi+, ℓi−) ≠ (ℓj+, ℓj−)；
即 φ(ui) ≠ φ(uj)。
故 φ 为单射，从而就有 mn + 1 ≤ mn 矛盾。
一些人组成的团体 S，试证可以把 S 分为两组，使得每个人在其所在的组中的朋友数至多是他在团体 S 中的朋友数的一半。
证 对 S 的任一二划分 {A, Ac}，令 f(A, Ac) = {(a, b) ∣ (a, b) ∈ A × Ac 且 a 与 b 互为朋友}
由于 |S| < ∞，所以 S 的 2-划分为有限个。所以，存在 S 的一个 2-划分 {B, Bc}，使 f(B, Bc) 最大。我们断言 B 与 Bc 即为所求。
实际上，∀a ∈ S，若 a ∈ B 且 a 在 B 中的朋友数 d > a 在 Bc 中的朋友数 d′，则把 a 调到 Bc 中得分组 B \ {a} 与 Bc ∪ {a}，分别记为 B′, B′c。于是
f(B′, B′c) = f(B, Bc) + (d − d′) > f(B, Bc)
这与 f(B, Bc) 为最大值的假设相矛盾。
已知 m 个整数 a1, a2, ⋯, am，试证：存在两个整数 k, ℓ，0 ≤ k < ℓ ≤ m，使得 ak + 1 + ak + 2 + ⋯ + aℓ 能被 m 整除。
【证】 考察下式：
a1
a1 + a2
a1 + a2 + a3
⋮
a1 + a2 + ⋯ + am
若第 i 式能被 m 整除，则显然成立，此时 k = 0, ℓ = i；
若任一式都不能被 m 整除，则考察各式被 m 整除后的余数，如下式：
a1 = q1m + r1
a1 + a2 = q2m + r2
a1 + a2 + a3 = q3m + r3
⋮
a1 + a2 + ⋯ + am = qmm + rm
由于每一个都不能被 m 整除，故共有 m 个余数—相当于 m 个物体。而任意整数被 m 除后的余数有 m − 1 种可能（即 1, 2, …, m − 1）—相当于 m − 1 个抽屉。
由抽屉原理，必有两个余数相等，设为 ri = rj，其中 i < j。
于是 (a1 + ⋯ + aj) − (a1 + ⋯ + ai) = ai + 1 + ⋯ + aj 能被 m 整除。
此时 k = i, ℓ = j，结论成立。
在一个半径为 16 的圆内任意放入 650 个点。给你一个形似垫圈的圆环，此圆环的外半径为 3, 内半径为 2。现在要求你用这个垫圈盖住这 650 个点中的至少 10 点，这可能吗？证明你的结论。
每个点可接触区面积: S = π(32 − 22) = 5π 可接触区的实际面积: S′ = π(16 + 3)2 = 361π 可能接触的总面积: nS = 650 * 5π = 3250π 平均一个位置接触的可接触区个数: $$ \frac{3250\pi}{361\pi}\approx9.002 \gt 9 $$ 故至少存在一个点接触10个可接触区(反证:若不然,则上面不可能大于9)
设 a1a2⋯an 为 1, 2, ⋯, n 的任一排列。如果 n 是奇数且
(a1 − 1)(a1 − 2)⋯(an − n) ≠ 0, 则乘积为偶数
反证法：若 (a1 − 1)(a2 − 2)⋯(an − n) 为奇数，则 (ai − i) 中的 ai 与 i 必是一个为奇数，一个为偶数。而 n 为奇数，故奇数个数为 $\left\lfloor \frac{n}{2} \right\rfloor + 1$ 比偶数 $\left\lfloor \frac{n}{2} \right\rfloor$ 多一个，这是不可能的。
证法 2：当 n 为奇数时，1, 2, …, n 中有 $\frac{n-1}{2}$ 个偶数，$\frac{n+1}{2}$ 个奇数，奇数的个数比偶数的个数多一个。于是，a1, a2, …, an，1, 2, …, n 中恰有 n + 1 个奇数。然而只有 n 个因子（n 个盒子），先把 a1, a2, …, an 依次放入 n 个盒中，然后把 1, 2, …, n 依次放入 n 个盒中，这样就把 n + 1 个奇数放入了 n 个盒中。因此，有一个盒子 i 中的两个数均为奇数，对应的因子 ai − i 就是偶数。
珍珠 4 颗，有真有假。真珍珠重量相同且为 p，假珍珠重量相同且为 q，p > q。用秤（而不是天平）仅称量 3 次查出真假，应该怎么做？
【解】 先用 < 1>、 < 2>、 < 3>、 < 4> 为 4 个珍珠编号且代表其重量。 < 1 > + < 2> 表示这两个珍珠放在一起称且代表其重量。其他类推。
称 < 1 > + < 2>， < 1 > + < 3>， < 2 > + < 3 > + < 4>，得如下的方程组：
$$ \begin{align*} <1> + <2> &= a_1 \\ <1> + <3> &= b_1 \\ <2> + <3> + <4> &= c_1 \end{align*} $$
其中 a1, b1, c1 是在称量后得到的常数。显然，a1 为 2p 或 2q 或 p + q。令
$$ x = \frac{<1> - q}{p - q}, \quad y = \frac{<2> - q}{p - q}, \quad z = \frac{<3> - q}{p - q}, \quad \omega = \frac{<4> - q}{p - q}, $$
$$ a = \frac{a_1 - 2q}{p - q}, \quad b = \frac{b_1 - 2q}{p - q}, \quad c = \frac{c_1 - 2q}{p - q}, $$
则我们有 $$ \begin{align*} x + y &= a \\ x + z &= b \\ y + z + \omega &= c \end{align*} $$ 其中 x, y, z, ω ∈ {0, 1}，a, b, c 为已知的常数。
由于 2(x + y + z) + ω = a + b + c 所以如果 a + b + c 为偶数，则 ω = 0；如果 a + b + c 为奇数，则 ω = 1。于是，根据 a + b + c 的奇偶性决定方程组的解。再由算得的结果 x, y, z, ω 中是 1 的代表相应的珍珠为真，为 0 的代表相同的珍珠为假珍珠。
设 f : X → Y。证明：f 是满的当且仅当 ∀E ∈ 2Y 有 f(f−1(E)) = E
⇐ if ∀E ∈ 2Y 有 f(f−1(E)) = E，往证 f 是满的。假设 f 不是满射，则 ∃y0 ∈ Y 使 ∀x ∈ X, f(x) ≠ y0。令 E = {y0}，则 f−1(E) = ϕ，∴ ϕ = f(f−1(E)) = E = {y0}，矛盾。所以，f 是满的
⇒ 显然，f(f−1(E)) ⊆ E。设 y ∈ E，则由于 f 是满的，所以 ∀y ∈ E, ∃x ∈ X 使 f(x) = y，故 x ∈ f−1(E) 且 y ∈ f(f−1(E))。因此，E ⊆ f(f−1(E))，故 f(f−1(E)) = E。
设 f : X → Y。证明：f 是单射当且仅当 ∀F ∈ 2X 有 f−1(f(F)) = F
⇐ 若不然, ∃x1, x2 ∈ X, x1 ≠ x2 使 f(x1) = f(x2)。令 F = {x1} 则 f(F) = f({x1}) = {f(x1)}, f−1(f(F)) = {x1, x2} ≠ {x1} = F，矛盾。
⇒ 由单射的性质,显然。
设 f : X → Y, A ⊆ X，则 (f(A))c ⊆ f(Ac) 成立吗？
提示:既不是满射,也不是单射
[解]
尝试举反例即可.
反例：设 X = {1, 2, 3}, Y = {a, b, c}。
f : X → Y, f(1) = a, f(2) = a, f(3) = b。
令 A = {1, 2}，则 Ac = {3}。
f(A) = {a}，(f((A))c = {b, c}，但 f(Ac) = b。
设 X 是一个无穷集合，f : X → Y。证明：存在 X 的一个真子集 E 使得 f(E) ⊆ E
证 取 x0 ∈ X，
令 x1 = f(x0), x2 = f(x1), ⋯, xn = f(xn − 1), ⋯。若到某一位与前面有重复项，设为第 k 项，即 f(xk) = xi(i < k)。令 E = {x0, x1, x2, ⋯, xk} ⊂ X，则 f(E) ⊆ E 且 E ⊂ X。
若 xi 互不相同，令 E1 = X \ {x0} ⊂ X，则 f(E1) ⊆ E1。
[不去掉 x0 有 E1 = X]
设 M 是一个非空集合，φ : M → M，N ⊆ M。令 𝒜 = {P|P ⊆ M 且 N ⊆ P, φ(P) ⊆ P}，G = ⋂P ∈ 𝒜P。
试证：
G ∈ 𝒜
N ∪ φ(G) = G
证 (1) ∀P ∈ 𝒜，G = ⋂P ∈ 𝒜P ⊆ P ⊆ M；∀P ∈ 𝒜，N ⊆ P，所以 N ⊆ G；φ(G) = φ(⋂P ∈ 𝒜P) ⊆ ⋂P ∈ 𝒜φ(P) ⊆ ⋂P ∈ 𝒜P = G。因此 G ∈ 𝒜。
- 显然有 N ∪ φ(G) ⊆ G。N ∪ φ(G) ⊆ M，N ⊆ N ∪ φ(G)，只要证明 φ(N ∪ φ(G)) ⊆ N ∪ φ(G) 即可知 N ∪ φ(G) ∈ 𝒜
从而有 G ⊆ N ∪ φ(G)
∀y ∈ φ(N ∪ φ(G))，∃x ∈ N ∪ φ(G)，使得 y = φ(x)
因为 x 是 N ∪ φ(G) 中元素，则可分以下二种情况讨论
- x 的像在 N 中，则 φ(x) ∈ N ∪ φ(G)；
- x 的像不在 N 中，又分三种情况：
- ① φ(x) = x
- ② φ(x) = y 时必有 φ(y) = x
- ③ φ(x) = y 且 φ(y) = z 时必有 φ(x) = z（否则与 φ(P) ⊆ P 矛盾）。
- 这三种情况下均有 φ(x) ∈ N ∪ φ(G)
设 X, Y, Z 是三个非空集合，|Z| ≥ 2。证明：f : X → Y 是满射当且仅当不存在从 Y 到 Z 的映射 g1 和 g2，使得 g1 ≠ g2，但g1 ∘ f = g2 ∘ f。
⇒ 因 f : X → Y 且 f 为满射，故 ∀y ∈ Y, ∃x ∈ X ，使得 f(x) = y。
假设存在 g1, g2, g1 ≠ g2，但 g1 ∘ f = g2 ∘ f。因为 g1 ≠ g2，所以 ∃y0 ∈ Y，使得 g1(y0) ≠ g2(y0)。对于上面的 y0，∃x0 ∈ X（f 是满射），使得 g1(f(x0)) ≠ g2(f(x0))
[g1(y0) ≠ g2(y0)]，即 g1f(x0) ≠ g2f(x0)。故 g1 ∘ f ≠ g2 ∘ f 与 g1 ∘ f = g2 ∘ f，矛盾。所以假设不成立。
证法 2:
f 满射 ⇔ f 右可逆 ⇔ ∃h : Y → X，使得 f ∘ h = IY⇔ 假设 g1 ∘ f = g2 ∘ f 得到 g1 = g2，命题得证。
⇐ f : X → Y，假设 f 不是满射，则 ∃y0 ∈ Y，使得 ∀x ∈ X, f(x) ≠ y0。构造两个映射 g1, g2 : Y → Z，
当 y = y0 时，g1(y0) ≠ g2(y0)；
当 y ≠ y0 时，g1(y) = g2(y)。
因为 |Z| ≥ 2，故此时 g1 ≠ g2，但
∀x ∈ X, g1 ∘ f(x) = g1(y ≠ y0) = g2(y ≠ y0) = g2 ∘ f(x)
即 g1 ∘ f = g2 ∘ f，与假设不存在 g1 ≠ g2，但 g1 ∘ f = g2 ∘ f 矛盾，故 f 一定是满射。
设 X, Y, Z 是三个非空的集合，|X| ≥ 2，证明：f : X → Y 是单射当且仅当不存在从 Z 到 X 的映射 g1, g2，使得 g1 ≠ g2，但 f ∘ g1 = f ∘ g2
⇒ f 是单射，则 ∀x1, x2, x1 ≠ x2，有 f(x1) ≠ f(x2)。假设存在 g1 和 g2 : Z → X, g1 ≠ g2，因为 |X| ≥ 2，于是 ∃z0 ∈ Z，使得 g1(z0) ≠ g2(z0)。
而由于 f 为单射，故 f(g1(z0)) ≠ f(g2(z0))，即 f ∘ g1(z0) ≠ f ∘ g2(z0)，故 f ∘ g1 ≠ f ∘ g2 矛盾。
证法 2: f 单射 ⇔ f 左可逆的 ⇔ ∃h 使得 hf = IX⇒ 由 f ∘ g1 = f ∘ g2 ⇒ g1 = g2 得证。
逆否命题：g1 ≠ g2 ⇔ fg1 ≠ fg2。
⇐ 假设 f 不是单射，则 ∃x1, x2 ∈ X, x1 ≠ x2，但 f(x1) = f(x2)。构造两个映射 g1 和 g2 : Z → X, ∀z ∈ Z，令 g1(z) = x1, g2(z) = x2，由于 |X| ≥ 2，故若 x1 ≠ x2，则有 g1 ≠ g2。但 ∀z ∈ Z, f ∘ g1(z) = f(x1) = f(x2) = f ∘ g2(z)，于是有 f ∘ g1 = f ∘ g2 矛盾。
设 f : X → Y, g : Y → Z，则 g ∘ f 是 X 到 Z 的映射。我们知道由 f 和 g 分别诱导出从 2X 到 2Y 与 2Y 到 2Z 的映射也记为 f 和 g。问诱导映射 f 与 g 的合成 g ∘ f 是否是映射 g ∘ f 的诱导映射呢？
[解]
不是.
举反例:
考虑X = {1, 2, 3}, Y = {a, b, c}, Z = {α, β, γ}
现在令 $$ f(1)=a,f(2)=a,f(3)=b\\ g(a)=\alpha,g(b)=\alpha,g(c)=\beta $$ 记:A = {a, b} ⊂ Y, B = {α, β} ⊂ Z
有诱导映射:f : 2X → 2Y, f(X) = A, g : 2Y → 2Z, g(Y) = B,
诱导映射$g \circ f(X)=\empty$,然而$g f(1)=,g f(2)=,g f(3)=, 即g f(X)=$才是其真正的诱导映射.
设 f : X → Y, g : Y → Z, A ⊆ Z，证明：(g ∘ f)−1(A) = f−1(g−1(A))
∀x ∈ (g ∘ f)−1(A), g ∘ f(x) ∈ A, f(x) ∈ g−1(A), x ∈ f−1(g−1(A))
即: (g ∘ f)−1(A) ⊆ f−1(g−1(A))
类似地:
∀x ∈ f−1(g−1(A)), f(x) ∈ g−1(A), g ∘ f(x) ∈ A, x ∈ (g ∘ f)−1(A)
即: (g ∘ f)−1(A) ⊇ f−1(g−1(A))
为了简便,上面过程可以用⇔
令 f 与 g 都是从集合 A 到 A 的映射。试证： |f ∘ g(A)| ≤ min {|f(A)|,|g(A)|}
采用反证法.
假设|f ∘ g(A)| = min {|f(A)|,|g(A)|} + 1,|f(A)| = x, |g(A)| = y
分情况讨论:
x > y
|f ∘ g(A)| = min {|f(A)|,|g(A)|} + 1 = y + 1,这是不可能的,违反了映射的定义
x = y
|f ∘ g(A)| = min {|f(A)|,|g(A)|} + 1 = x + 1,这是不可能的,违反了映射的定义
x < y
|f ∘ g(A)| = min {|f(A)|,|g(A)|} + 1 = x + 1,这是不可能的,违反了映射的定义
设 f 和 g 都是从集合 A 到 A 的映射。试证：一般地 f ∘ g(A) ⊈ f(A) ∩ g(A) 注意本题在书上的表述有误,可以很容易举出一个反例.
本题笔者未完全理解. 若此处f, g全为恒等映射不能断定此命题错误吗?笔者猜测是某些文字中隐藏的条件未被使用.
下面贴出老师参考答案:
如果 g 是单射，则 g 是双射，此时， fg(A) = f(g(A)) = f(A) = f(A) ∩ g(A) 如果 g 不是单射，则 g 也不是满射，∃x ∈ A 使得 ∀y ∈ A 均有 g(y) ≠ x，此时 fg(A) = f(g(A)) ⊆ f(A) \ f(x)
f(A) ∩ g(A) ⊆ f(A) \ {x} 一般情况下，f(x) ≠ x，因此 fg(A) ⊈ f(A) ∩ g(A)。
设 f = u ∘ g ∘ v，其中 f, g, u, v 都是从集合 A 到 A 的映射。证明： |f(A)| ≤ |g(A)|
f = u ∘ g ∘ v，则 f(A) = u(g(v(A)))，则 |f(A)| ≤ |g(v(A))| ≤ |g(A)|
设 N = {1, 2, 3, ⋯}，试构造两个映射 f 和 g : N → N，使得 - (1) fg = IN，但 gf ≠ IN； - (2) gf = IN，但 fg ≠ IN。
[解] (1) fg = IN 但 gf ≠ IN，故 f 是满射，但 f 不是单射。于是令： f : N → N, f(1) = 1, f(n) = n − 1, n ≥ 2,
g : N → N, ∀n ∈ N, g(n) = n + 1,
则 fg = IN 但 gf ≠ IN。事实上，当 n = 1 时，gf(1) = g(f(1)) = g(1) = 2，故 gf ≠ IN。
- 和(1)有什么区别?
设 f : X → Y 则 - (1) 若存在唯一的一个映射 g : Y → X，使得 gf = IX，则 f 是可逆的吗？ - (2) 若存在唯一的一个映射 g : Y → X，使得 fg = IY，则 f 是可逆的吗？
[解]
- f 不一定可逆。
- 当 |X| = 1 时，f 不一定可逆。
- 当 |X| ≥ 2 时，f 可逆。
- f 一定可逆。
证 由 fg = IY，得 f 是单射。假设 f 不是满射，则 g 不唯一，矛盾。
设 f : X → Y, |X| = m, |Y| = n，则 - (1) 若 f 是左可逆的，则 f 有多少个左逆映射？ - (2) 若 f 是右可逆的，则 f 有多少个右逆映射？
[解] 令 X = (x1, x2, ⋯, xm), Y = (y1, y2, ⋯, yn)，则
- 有 mn − m；
- 有 |f−1(y1)| × |f−1(y2)| × ⋯ × |f−1(yn)| = Πξ ∈ Y|f−1(ξ)|
自行绘图结合定义即可.
证明：每个 n 次置换 σ 都可分解成这样的一些置换的乘积：每个置换或为 (1 2) 或为 (2 3 ⋯ n)。
证 只须证明，∀i ∈ {2, 3, …, n} 有 (1 i) = αxβαy 其中 α = (2, 3, …, n)，β = (1 2)，这是因为: (i j) = (1 i)(1 j)(1 i) 此结论在教材中有证明
$$ (1 \ i) = \alpha^{x} \beta \alpha^{y}=\begin{pmatrix} i & i+1 & \cdots \\ 2 & 3 & \cdots \end{pmatrix}(1,2)\begin{pmatrix} 2 & 3 &\cdots \\ i & i+1 & \cdots \end{pmatrix} $$
凑出x, y即可
观察发现: $$ \alpha^{x+y} =\begin{pmatrix} 2 & 3 &\cdots \\ i & i+1 & \cdots \end{pmatrix}\begin{pmatrix} i & i+1 & \cdots \\ 2 & 3 & \cdots \end{pmatrix}=\alpha \\ \Rightarrow x+y=n-1 \\ $$ 凑出y = i − 2,进而有x = n + 1 − i
(1 i) = αn + 1 − iβαi − 2
任一偶置换均可被分解成 3− 循环置换 (123)，(124)…(12n) 中若干之乘积。
证 证法 1：∀i, j, s, t ∈ {1, 2, ⋯, n}, i ≠ j, s ≠ t (ij)(st) = (1i)(1j)(1i)(2s)(2t)(2s) = (1i)(1j)(2s)(1j)(2t)(2s)
= (1i)(2s)(1j)(2t)(1i)(2s)
= (1 2 s)(1 2 i)(1 2 t)(1 2 j)(1 2 s)(1 2 i)
因为 $(1 \quad 2 \quad s)(1 \quad 2 \quad i) = \begin{pmatrix} 1 & 2 & s \\ 2 & s & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 & i \\ 2 & i & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & s & i \\ i & s & 2 & 1 \end{pmatrix} = (1i)(2s)$ $$ (12t)(12j) = \begin{pmatrix} 1 & 2 & t \\ 2 & t & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 & j \\ 2 & j & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 & t & j \\ j & t & 2 & 1 \end{pmatrix} = (1j)(2t) $$ 因此本题得证。
证法 2：由 (1 i)(1 j) = (1 i j)，(1 i j) = (12j)(12i)(12j)2 即得证。
- 证明下列置换等式
(ac1⋯chbd1⋯dk)(ab) = (ac1⋯ch)(bd1⋯dk)
(ac1⋯ch)(bd1⋯dk)(ab) = (ac1⋯chbd1⋯dk)
- $$ (ac_1 \cdots c_h bd_1 \cdots d_k)(ab) = \begin{pmatrix} a & c_1 & c_2 & \cdots & c_h & b & d_1 & \cdots & d_k \\ c_1 & c_2 & c_3 & \cdots & b & d_1 & d_2 & \cdots & a \end{pmatrix}(ab) $$
$$ = \begin{pmatrix} a & c_1 & c_2 & \cdots & c_h & b & d_1 & \cdots & d_k \\ c_1 & c_2 & c_3 & \cdots & a & d_1 & d_2 & \cdots & b \end{pmatrix} $$
= (ac1⋯ch)(bd1⋯dk) (2) $$ (ac_1 \cdots c_h)(bd_1 \cdots d_k)(ab) = \begin{pmatrix} a & c_1 & \cdots & c_h & b & d_1 & \cdots & d_k \\ c_1 & c_2 & \cdots & a & d_1 & d_2 & \cdots & b \end{pmatrix}(ab)= \begin{pmatrix} a & c_1 & \cdots & c_h & b & d_1 & \cdots & d_k \\ c_1 & c_2 & \cdots & b & d_1 & d_2 & \cdots & a \end{pmatrix}= (ac_1 \cdots c_h bd_1 \cdots d_k) $$
设 σ 是任一置换，试证：σ−1(i1i2⋯ir)σ = (i1σ i2σ⋯irσ)。
证 令 α = σ−1(i1i2⋯ir)σ，β = (i1σ i2σ⋯irσ)，∀i ∈ S，分两种情况，
i ∉ {i1σ, i2σ, ⋯, irσ} 时，iα = iβ = i；
i ∈ {i1σ, i2σ, ⋯, irσ} 时，又分两种情况，
- ① i = ikσ, k < r，iα = ikσσ−1(i1i2⋯ir)σ = (ik(i1i2⋯ir))σ = (ik + 1)σ = iβ；
- ② i = irσ，iα = irσσ−1(i1i2⋯ir)σ = (ir(i1i2⋯ir))σ = (i1)σ = iβ。
在所有的 n 次置换中，有多少个 n− 循环置换？
提示:站在映射的角度看这个问题,绘图或许会给你一些帮助
[解] $$ (i_1, i_2, \cdots, i_n) = \begin{pmatrix} i_1 & i_2 & \cdots & i_n \\ i_2 & i_3 & \cdots & i_1 \end{pmatrix} $$
对 i1，有 n 种选择
对 i2，有 (n − 1) 种选择
……
对 in 有
1 种选择
因此共有 n! 种排列。
对每个 n− 循环置换，均有 n 种排列，因此 n− 循环置换的个数为 $\frac{n!}{n} = (n-1)!$ 个。
设 S(n, k) 表示 Sn 中的恰有 k 个循环（包括 1− 循环）的置换个数。证明： $$ \sum_{k=1}^{n} S(n, k) x^k = x(x + 1)(x + 2)\cdots(x + n - 1) $$ 提示:如无必要能力精力,不建议花费时间在此.
考察 S(n, k) 与 S(n − 1, k)的关系.
在 n − 1 个元素的基础上增加一个元素 n 后的情况需要分类讨论:
- 增加的 n 自成循环,总循环数+1,要求前 n − 1 个元素形成 $ k-1$ 个循环,此时前 n − 1 个元素中有S(n − 1, k − 1) 个置换
- 增加的 n 被加入前 n − 1 个元素形成的某个循环,要求前 n − 1 个元素形成 $ k$ 个循环,此时前 n − 1 个元素中有S(n − 1, k) 个置换, n 可以被加入在 n − 1 个元素任何一个的前面,故有 n − 1 种加入方法
根据上面的分析,结合乘法法则有: S(n, k) = S(n − 1, k − 1) + (n − 1)S(n − 1, k) 如果对这个结果感到困惑,请仔细阅读 S(n, k) 的定义
由定义可以给出: S(n, n) = 1, S(n, 0) = 0 观察题设形式,联想到数学归纳法,施归纳于n:
当n = 1,S(1, 1)x = x
假设对 n = i 时结论成立,此时有: $$ \sum_{k=1}^{i} S(i, k) x^k = x(x + 1)(x + 2)\cdots(x + i - 1)=\prod ^{i-1}_{j=0}(x+j) $$ 则当 n = i + 1时,使用(1)式: $$ \begin{align} \sum_{k=1}^{i+1} S(i+1, k) x^k =& S(i+1, i+1) x^{i+1}+\sum_{k=1}^{i} S(i+1, k) x^k=\\ =& x^{i+1}+\sum_{k=1}^{i}[S(i,k-1)+iS(i,k) ]x^k \\ =& x^{i+1}+x\sum_{k=1}^{i}S(i,k-1)x^{k-1}+i\sum_{k=1}^{i}S(i,k) x^k\\ =& x^{i+1}+x\sum_{k=2}^{i}S(i,k-1)x^{k-1}+i\prod ^{i-1}_{j=0}(x+j)\\ =& x^{i+1}+x\sum_{k=1}^{i-1}S(i,k)x^{k}+i\prod ^{i-1}_{j=0}(x+j)\\ =& x^{i+1}+x[\prod ^{i-1}_{j=0}(x+j)-x^{i}]+i\prod ^{i-1}_{j=0}(x+j)\\ =& (x+i)\prod ^{i-1}_{j=0}(x+j)\\ =& \prod ^{i}_{j=0}(x+j) \end{align} $$ 证毕
令 {ank}k = 1∞ 是 {an}n = 1∞ 的子序列，证明：∀k ∈ ℕ, nk ≥ k。
采用反证法
假设 $\exist i \in \mathbb{N},n_i \lt i$,则 ni ≤ i − 1
根据子序列定义2.7.2: ni − 1 < ni ≤ i − 1
施归纳于 i ,可得 n1 < 1,又因为 nk ∈ ℕ 这是不可能的.
设 {an}n = 1∞ 是一个序列。试证：{an}n = 1∞ 的子序列的子序还是 {an}n = 1∞ 的子序列。
取 X 上一个序列 {an}n = 1∞ ,取 s = {ni}i = 1∞ 作为自然数序列的一个子序列,取 r = {ms}s = 1∞ 作为 s 序列的一个子序列
此问题等价于证明: r ∘ s 是自然数序列的一个子序列
验证定义即可: ∀i, j ∈ ℕ, i < j, s(i) < s(j) ⇒ r(s(i)) < r(s(j)) 证毕
给出一个三元运算的例子。
提示:注意 n 元运算定义
[解] 求三个正整数的最大公因数