コンビネーションの偶数奇数判定ってできますかね

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

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

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

No.4 ベストアンサー 回答者： qqqqqhf 回答日時： 2009/02/25 01:19

http://oshiete1.goo.ne.jp/qa2385467.html

No.3 回答者： Tacosan 回答日時： 2009/02/23 21:12

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 でいけるかな?

No.2 回答者： sanori 回答日時： 2009/02/23 19:08

こんばんは。

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

偶数Ｃ偶数
8Ｃ2　＝　８×７÷（２×１）　＝　２８　偶数
6Ｃ2　＝　６×５÷（２×１）　＝　１５　奇数

奇数Ｃ偶数
9Ｃ2　＝　９×８÷（２×１）　＝　３６　偶数
7Ｃ2　＝　７×６÷（２×１）　＝　２１　奇数

偶数Ｃ奇数
6Ｃ3　＝　６×５×４÷（３×２×１）　＝　２０　偶数
14Ｃ6　＝　１４×１３×１２×１１×１０×９÷（６×５×４×３×２×１）　＝　３００３　奇数

奇数Ｃ奇数
9Ｃ3　＝　９×８×７÷（３×２×１）　＝　８４　偶数
7Ｃ1　＝　７÷１　＝　７　奇数


ご参考に。

No.1 回答者： Tacosan 回答日時： 2009/02/23 19:06

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

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