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

考虑统计有 $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)$。只需本文第一部分的论证即可。