4年に一度のスポーツの祭典 全競技速報中

nCm コンビネーションについてですが、n,mが偶数か奇数かによって偶数奇数判定ってできないでしょうか?
分数が入ってると偶数か奇数かわからないような気がするのですが、

階乗計算をしないでできるだけ簡単にコンビネーションの偶数奇数判定をしたいのですが、

どなたか、知恵を御貸し下さい。
お願い致します。

gooドクター

A 回答 (4件)

    • good
    • 0

n, m が偶数か奇数か, だけでは決まりませんが, log n 時間くれれば可能だと思う. ちょっと計算したところによると, 「nCm を 2 で割った余り」を P(n, m) とおくと


・P(0, 0) = 1
・n が偶数かつ m が奇数なら P(n, m) = 0
・その他のときは P(n, m) = P(floor(n/2), floor(m/2))
でいけるような感じ.
あ, だから「偶数C奇数」は必ず偶数です>#2.
あとで見ると絶対謎にしか見えないので導出過程を書いておくと:
P(0, 0) = 1 は (0C0 = 1 だから) 自明.
n が偶数のときには, 「Z/2Z 上で多項式 f(x) に対し [f(x)]^2 = f(x^2)」が使えて, m が偶数なら P(n, m) = P(n/2, m/2). m が奇数のときは自動的に P(n, m) = 0 となります.
最後に n が奇数のときは nCm の帰納的定義から nCm = (n-1)C(m-1) + (n-1)Cm なので, P(n, m) = P(n-1, m-1) + P(n-1, m) mod 2. ただしこのとき n-1 は偶数で m と m-1 のうち一方は偶数かつ他方は奇数なので, n が偶数のときを使うともっと簡単になるはずです. じっと見るとこの場合 P(n, m) = P(floor(n/2), floor(m/2)) と書けることがわかります.
ということで, 数学的には多分このくらい. プログラムで判定するなら言語によるけど, C なら (~n & m) != 0 でいけるかな?
    • good
    • 0

こんばんは。



判定できません。
判定できないことの証明としては、反例を挙げるだけでよいです。

偶数C偶数
8C2 = 8×7÷(2×1) = 28 偶数
6C2 = 6×5÷(2×1) = 15 奇数

奇数C偶数
9C2 = 9×8÷(2×1) = 36 偶数
7C2 = 7×6÷(2×1) = 21 奇数

偶数C奇数
6C3 = 6×5×4÷(3×2×1) = 20 偶数
14C6 = 14×13×12×11×10×9÷(6×5×4×3×2×1) = 3003 奇数

奇数C奇数
9C3 = 9×8×7÷(3×2×1) = 84 偶数
7C1 = 7÷1 = 7 奇数


ご参考に。
    • good
    • 0

帰納的な定義から表を作れば n^2 か nm か, くらいの時間だけど....


もっと速くできるかどうかは, すぐには分かんない.
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング