haskell-ja > Archives > 2012/11/19

長文すいません。
■練習問題1.2.3についての蒸し返し
(「関数プログラミング入門 Haskellで学ぶ原理と技法」)
「第1回 IFPH読書会」に参加させていただきました。
「練習問題1.2.3」の問題は、すべての簡約過程を全探索で書かせて
簡約過程の諸々を実感させる目的がある様に思えるので
Permitation等の数え上げの数学を使用して問いに答えるのは題意から外れると
自分でも思います。

ですが、問題をより一般化した場合、場合の数が100を超えるような問題と
出会った時に、自分は全探索で漏れなく答を列挙できる自信はありません。
(単なる計算ミスが、発生する確率が無視できない。)
また、検算を簡単に行う方法も知りたいのです。
(他に、コンピュータに解かせる方法もあると思います。)

今問題に対して、階乗を応用したPermitationの、Permitation(3, 2)では間違いでしたが、
２重階乗を使用したPermitationのような物、(ここではPermitation'と呼ばせてください。)
で解けると思います。
(問題は、１回簡約すると２つ簡約ポイントが消滅するので、１回に１つだけ選択肢が消える
Permitationでは、数えられないのが理由でした。)

Permitation'の雑な定義は下式
(1)n!! = n * (n-2) * (n-4) * ...... 
(2)Permitation' = n!!/(n-2r)!!

これを使うと、今回の回答は、次の様になると思います。
Permitation'(3,2) = 3 * 1

これは、少なくとも、検算用や別法には、成ると思います。
nobsun様、どの様に思われるでしょうか ?

(「２重階乗」自体も今回初めて見るもので、上記Permitation'の数学での
正式呼称は解りません。知っている方がいらっしゃったら、どうか教えてください。)