看不懂Wikipedia对${ap \choose bp} \equiv {a \choose b} \pmod{p^2}$的证明.

hbghlyj

此帖子是该论坛帖子12#的后续：

看不懂维基百科上的${ap \choose bp} \equiv {a \choose b} \pmod{p^2}$的证明.

hbghlyj 发表于 2024-11-5 11:37
阶为 $p$ 的循环群的 $a$ 次直和作用在集合 $A$ 上，并且扩展到作用在大小为 $bp$ 的子集的集合上。这个群作用的每个轨道都有 $p^k$ 个元素，其中 $k$ 是与轨道中的子集 $B$ 部分地相交的环的数量。大小为 1 的轨道有 $\textstyle {a \choose b}$ 个，并且没有大小为 $p$ 的轨道。

有人能解释一下这段话吗？我完全糊涂了
“与 $B$ 相交的不完整环的数量”是什么意思？“每个轨道都有$p^k$个元素”指的是什么？

hbghlyj

设 $A_i=\{(i-1)p+1, \cdots, ip\}$ ($1\leq i\leq a$)，$A=\bigcup\limits_{1\leq i\leq a} A_i$，对于每个 $i$，设 $\sigma_i$ 是 $A_i$ 上的循环置换。因此 $\sigma_i$ 的阶为 $p$，设 $P=\prod\limits_{i=1}^a\langle \sigma_i\rangle$，它作为 $A$ 的置换作用，从而作用于 $\mathcal{B}:=\{B|B\subseteq A, |B|=bp\}$。

现在可以将 $\mathcal{B}$ 划分为 $P$ 作用下的轨道，并注意到 $|\mathcal{B}|=\binom{ap}{bp}$。对于 $B\in\mathcal{B}$，设 $k(B)$ 表示 $\left|\{i\bigm\vert |A_i\cap B|\in [1,p-1]\}\right|$，随后，$P_B=p^{a-k(B)}$，即 $B$ 的 $P$ 轨道长度为 $p^{k(B)}$。注意到要么 $k(B)\geq 2$，要么 $k(B)=0$，而 $P$ 的作用固定 $k(B)$。因此，模 $p^3$，$\binom{ap}{bp}\equiv|\{B|k(B)=0\}|+|\{B|k(B)=2\}|=\binom{a}{b}+|\{B|k(B)=2\}|$。

此外，$|\{B|k(B)=2\}|=\binom{a}{2}(\binom{2p}{p}-2)\binom{a-2}{b-1}$，因此只需证明 $p^3|\binom{2p}{p}-2$。

其余部分与经典证明相同：$p^3|\binom{2p-1}{p-1}-1=\prod\limits_{i=1}^{p-1}(1+\frac{p}{i})-1$。或者你可以参考维基百科上的证明。

hbghlyj

hbghlyj 发表于 2024-11-5 21:51
随后，$P_B=p^{a-k(B)}$，即 $B$ 的 $P$ 轨道长度为 $p^{k(B)}$。

解释一下这句话，由于那些固定 $B$ 不变的 $\sigma_i$ 恰好就是那些不与 $B$ 相交的 $\sigma_i$，所以它们有 $a-k(B)$ 个，所以$B$的稳定子的阶为$p^{a-k(B)}$。用 $P$ 的阶 $p^a$ 除以$p^{a-k(B)}$，即得 $B$ 的 $P$ 轨道长度为 $p^{k(B)}$。

hbghlyj

hbghlyj 发表于 2024-11-5 21:51
注意到要么 $k(B)\geq 2$，要么 $k(B)=0$.

这句话说我们不能有一个 $B$ 使得 $k(B)=1$，这是因为 $B$ 中元素的数量是 $bp$，是 $p$ 的倍数
如果$B$只部分相交 1 个 $A_i$，并完全包含(或完全不相交)其余的 $A_i$，这意味着 $B$中元素的数量不能是$p$的倍数，矛盾。

hbghlyj

hbghlyj 发表于 2024-11-5 21:51
此外，$|\{B|k(B)=2\}|=\binom{a}{2}(\binom{2p}{p}-2)\binom{a-2}{b-1}$

让我们解释一下这个公式是如何产生的。
它想要计算滿足条件 $k(B)=2$ 的 $B$ 的数量。
$k(B)=2$ 表示 $B$ 仅与 2 个 $A_i$ 部分相交，这意味着 $B$ 与 这两个$A_i$ 相交的元素数量不多于$2p$也不为0且为$p$的倍數，因此只能为 $p$。记住 $B$ 有 $bp$ 个元素，因此它还完全包含 $A_i$ 中的 $(b-1)$ 个。

先选取与$B$部分相交的两个$A_i$，有$\binom{a}{2}$种方法。那么这两个 $A_i$ 都有 $2p$ 个元素，我们需要从中选择 $p$ 个放入 $B$ 中，而避免“完全选择一个 $A_i$ 而另一个留下 0 个元素”的情況需要減少2个选法，因此有$\binom{2p}{p}-2$种方法。最后需要在剩余的 $A_i$ 中选择 $b-2$ 个 $A_i$ 完全包含在 $B$ 中，所以选取方法数为 $a-2\choose b-1$

realnumber

每个字都认识,赶紧闪,~~~随机异位面传送