多重集排列数为奇数充要条件的证明

根据搜索结果和组合数学理论，提供一个更为简化的证明过程，说明多重集排列数 $P = \frac{n!}{n₁!n₂!...nₖ!}$ 为奇数的充要条件。

简化后的充要条件表述

对于一个多重集 $S = \{n₁·a₁, n₂·a₂, ..., nₖ·aₖ\}$，其排列数 $P$ 为奇数的充要条件是： 在二进制表示下，所有 $nᵢ$ 的 $1$ 位互不重叠，且它们的和 $n = n₁ + n₂ + ... + nₖ$ 在相加时不产生任何进位。

简要证明

核心思路

• 利用Lucas定理：Lucas定理指出，对于素数 $p$，组合数 $C(n,m)$ 模 $p$ 等于将 $n$ 和 $m$ 表示为 $p$ 进制数后各位组合数的乘积模 $p$。特别地，当 $p = 2$ 时，$C(n,m)$ 为奇数当且仅当 $m$ 的二进制表示不包含 $n$ 的二进制表示中没有的 $1$。
• 推广到多重集排列数：多重集排列数可以视为多重组合数的乘积，其奇偶性由各阶乘中 $2$ 的幂次决定。

关键步骤

• $2$ 的幂次分析： $P$ 为奇数 $\Leftrightarrow v₂(P) = 0 \Leftrightarrow v₂(n!) = \sum_{i}v₂(nᵢ!)$ 根据Legendre公式，$v₂(m!) = m - s₂(m)$，其中 $s₂(m)$ 是 $m$ 的二进制表示中 $1$ 的个数。
• 二进制无进位加法： 由 $v₂(n!) = \sum_{i}v₂(nᵢ!)$ 可得：$n - s₂(n) = \sum_{i}(nᵢ - s₂(nᵢ))$ 因为 $n = \sum_{i}nᵢ$，所以简化为：$s₂(n) = \sum_{i}s₂(nᵢ)$ 这意味着在二进制加法 $n = \sum_{i}nᵢ$ 过程中没有进位。
• 直接结论： 上述等式成立的充要条件是所有 $nᵢ$ 的二进制表示中 $1$ 的位置互不重叠，这样在相加时不会产生进位，保持了 $1$ 的总数不变。

直观解释

这个条件可以直观理解为：当将所有 $nᵢ$ 的二进制表示叠加时，没有任何两个 $nᵢ$ 在同一二进制位上有 $1$。这保证了：

• 在计算 $n = \sum_{i}nᵢ$ 时不会产生进位。
• 每个阶乘 $n!$ 和 $nᵢ!$ 中 $2$ 的幂次关系保持平衡。
• 最终排列数 $P$ 的分母和分子中 $2$ 的幂次完全抵消。

示例验证

• 示例1：考虑多重集 $\{1·a, 2·b\}$（即 $n₁ = 1 = 1₂, n₂ = 2 = 10₂$，$n = 3 = 11₂$） 二进制表示：$1 = 1₂, 2 = 10₂$ 相加：$1 + 10 = 11₂$（无进位） 排列数：$\frac{3!}{1!2!} = 3$（奇数） 验证：满足条件（$1$ 位不重叠）
• 示例2：考虑多重集 $\{1·a, 1·b, 1·c\}$（即 $n₁ = n₂ = n₃ = 1 = 1₂$，$n = 3 = 11₂$） 二进制表示：$1 = 1₂, 1 = 1₂, 1 = 1₂$ 相加：$1 + 1 + 1 = 11₂$（有进位） 排列数：$\frac{3!}{1!1!1!} = 6$（偶数） 验证：不满足条件（$1$ 位重叠）

这个简化证明利用了Lucas定理的核心思想和二进制表示的特性，避免了复杂的Legendre公式计算，直接抓住了问题的本质特征。