关于线性基数量的一个有趣推导

· · 个人记录

考虑统计有 n 个元素的 n 维线性基，元素之间无序。

如果我们忽略元素之间无序的需求，我们可以发现第 i 个元素除了不能取到之前所能组成的的 2^{i-1} 个元素以外，其余的都可以取到，故结果为：

\prod_{i=0}^{n-1}(2^n-2^i)

考虑上元素无序这一点，显然合法方案的元素两两不同，故可以直接除去 n!，得到：

\frac{1}{n!}\prod_{i=0}^{n-1}(2^n-2^i)

对于上述结果为整数我们可以给出一个数论的证明： 考虑质因子 p，原命题等价于对于所有 p：

\nu_p(n!)\leq\nu_p(\prod_{i=0}^{n-1}(2^n-2^i))

若 p=2，则有：

\mathrm{LHS}\leq n-1\leq \frac{n(n-1)}{2}= \mathrm{RHS}

若 p\neq2，则有：

\mathrm{LHS}=\sum_{i=0}^{+\infty}\lfloor\frac{n}{p^i}\rfloor \leq \lfloor\frac{n}{p-1}\rfloor=\lfloor\frac{n}{\varphi(p)}\rfloor \mathrm{RHS}\geq \sum_{i=0}^{n-1}\nu_p(2^n-2^i)\geq \sum_{i=0}^{n-1}[2^n\equiv2^i\kern{-8pt}\pmod p] \sum_{i=0}^{n-1}[2^n\equiv2^i\kern{-8pt}\pmod p]=\lfloor\frac{n}{\delta_p(2)}\rfloor\geq\lfloor\frac{n}{\varphi(p)}\rfloor\geq \mathrm{LHS}

证毕。

与该结论相关的是 [小技巧 #49]：对于 n 阶矩阵 M 而言，\det M \bmod p 非零的 M 数量是 \prod_{i=0}^{n-1} (p^n-p^i)。只需本文第一部分的论证即可。