練習問題 3.11.2

② 本文中で与えた再帰的な定義で（n m）を求める関数comb

(* 組み合わせ *)
(*
m個のなかからn個選び出す組み合わせの数 mCn は、
mCn = mPn / n!
すなわち、
mPn = m! / (m - n)!  --> これを n! で割る。
たとえば、5C2 なら、
5P2 = 5! / (5-2)! = 5*4*3*2*1 / 3*2*1 = 20
5C2 = 5P2 / n! なので、20 / 2*1 = 10
答え、10通り
*)
(*
以下のように、再帰的に定義できる。
nC0 = nCn = 1
nCm = (n-1)Cm + (n-1)C(m-1)
ただし、0 <= m < n
*)
(* comb : (int, int) => int *)
let rec comb (n, m) =
  if m = 0 || n = m
  then 1
  else
    comb ((n - 1), m) + comb ((n - 1), (m - 1));;

(* TEST *)
let test11 = comb(5, 2) = 10;;
let test12 = comb(10, 2) = 45;;
let test13 = comb(10, 4) = 210;;

Tweet