ブログ

特になし

多項係数の偶奇

多項係数 \frac{n!}{k_1!~k_2!~\ldots~k_m!} の偶奇を求めたくなることはよくあると思います。
Lucas の定理を使えば形式的に計算できますが、ここでは組合せ的な方法で多項係数の偶奇を求めてみます。

まず多項係数の値は、一列に並べた n 個のボールのうち k_i 個を色 i で塗る方法の数と解釈できます。なのでそのような塗り方の偶奇を考えます。
ここで色の塗り方が左右対称でない場合、左右反転することで異なる塗り方と対応付けることができます。

f:id:gzlcp:20200424095627p:plain
この塗り方を反転すると
f:id:gzlcp:20200424095620p:plain
こうなる、逆も同じ

つまり左右対称でない色の塗り方は偶数です。よって塗り方全体の偶奇は左右対称な塗り方の偶奇に等しいです。

n が偶数のとき、 k_1, k_2, \ldots, k_m の中に奇数があれば左右対称な塗り方は存在しません。この場合、塗り方の総数は偶数と分かります。 k_1, k_2, \ldots, k_m が全て偶数なら、左右対称な塗り方の数は \frac{n}{2} 個のボールのうち \frac{k_i}{2} 個を色 i で塗る方法の数と一致します。

n が奇数のとき、 k_1, k_2, \ldots, k_m の中の奇数がちょうど 1 つでなければ、左右対称な色の塗り方は存在しません。このときも塗り方の総数は偶数と結論できます。そうでないとき、一般性を失わずに k_1, k_2, \ldots, k_m の中で k_1 だけが奇数であるとします。この場合、左右対称な塗り方の数は、 \frac{n - 1}{2} 個のボールのうち \frac{k_1 - 1}{2} 個を色 1 で、 \frac{k_i}{2} 個を色 i (2 \leq i \leq m) で塗る方法の数に等しいです。

以上のどちらの場合でも、小さい問題への帰着は各 n, k_1, k_2, \ldots, k_m の右シフトに等しくなっています。これを踏まえると、 n, k_1, k_2, \ldots, k_m をそれぞれ 2 進数で表したとき、 n で 0 になっている桁については k_1, k_2, \ldots, k_m でも 0、 n で 1 になっている桁については k_1, k_2, \ldots, k_m の中でちょうど 1 つが 1 になっていることが多項係数の値が奇数になることの必要十分条件になります。

これは k_1~\text{or}~k_2~\text{or}~ \ldots ~\text{or}~k_m = n と 1 つの式で表すことができます ( \text{or} は整数の bitwise OR)。