Assignments: Mar 10th, 2026
Problem 1.
对于任意实数
\left| x - \frac{p}{q} \right| < \frac{1}{nq}.
\left| x - \frac{pk}{qk} \right| < \frac{1}{qk q{k+1}} = \frac{1}{qk(a{k+1}qk + q{k-1})} \leq \frac{1}{a{k+1}qk^2}.
对于给定的 n，选取适当的 k 使得 qk \leq n < q{k+1}。由连分数递推关系 q{k+1} = a{k+1}qk + q{k-1} \geq a{k+1}qk，我们有：
n < q{k+1} \leq (a{k+1} + 1)qk \quad \Rightarrow \quad a{k+1} > \frac{n}{q_k} - 1.
\left| x - \frac{pk}{qk} \right| < \frac{1}{a{k+1}qk^2} < \frac{1}{(\frac{n}{qk}-1)qk^2} = \frac{1}{nqk - qk^2}.
\left| x - \frac{pk}{qk} \right| < \frac{2}{nq_k}.
\Pr[f \text{ 是满射}] = \sum_{k=0}^{n-1} (-1)^k \binom{n}{k} \left(1 - \frac{k}{n}\right)^m.
Proof.
我们使用指数生成函数的方法。设 S(m,n) 为从 [m] 到 [n] 的满射数量。
首先，从 [m] 到 [n] 的所有函数数量为 n^m。对于满射，我们可以使用容斥原理，但这里展示另一种方法。
考虑指数生成函数：
F(x) = \sum_{m=0}^{\infty} n^m \frac{x^m}{m!} = e^{nx}.
这计算了所有函数（按像集大小加权）。为了提取满射，我们使用：
\sum_{m=0}^{\infty} S(m,n) \frac{x^m}{m!} = (e^x - 1)^n.
(e^x - 1)^n = \sum{j=0}^{n} \binom{n}{j} (-1)^{n-j} e^{jx} = \sum{j=0}^{n} \binom{n}{j} (-1)^{n-j} \sum_{m=0}^{\infty} j^m \frac{x^m}{m!}.
S(m,n) = \sum{j=0}^{n} \binom{n}{j} (-1)^{n-j} j^m = \sum{k=0}^{n} \binom{n}{k} (-1)^k (n-k)^m.
其中最后一步令 k = n-j。
因此，满射的概率为：
\Pr[f \text{ 是满射}] = \frac{S(m,n)}{n^m} = \sum{k=0}^{n} \binom{n}{k} (-1)^k \left(\frac{n-k}{n}\right)^m = \sum{k=0}^{n-1} (-1)^k \binom{n}{k} \left(1 - \frac{k}{n}\right)^m.
最后一步是因为 k=n 时项为0。
∎
Download the original write-up here.