Combination

組み合わせとは、n 個から順序を考慮せずに k 個を選ぶ選び方の数 C(n,k)=n!/(k!(n-k)!)、すなわち二項係数である。

目的

順序のない選択を数え上げる、組合せ数学と確率論の基礎である。

メカニズム

C(n,k) = n!/(k!(n-k)!) = C(n,n-k) が成り立つ。漸化式は C(n,k)=C(n-1,k-1)+C(n-1,k)（パスカルの三角形）である。多倍長の数には対数または漸化式を用いてオーバーフローを避ける。C(n,0)=1、C(n,n)=1 である。

ユースケース

二項分布などについての確率の計算
組合せの数え上げ
二項展開などにおける係数の計算
超幾何分布（ハイパージオメトリック）

例

入力
```
C(5,2)=5!/(2!3!)=10
```
Output
```
10
```
Choosing 2 of 5, unordered

よくあるエラー

Computing factorials directly overflows: Use the recurrence or logarithms

関連用語

順列はn個からk個を選ぶ順序付きの数え方であり、P(n,k)=n!/(n-k)! で計算する。全順列の個数はn!である。

階乗 n! = n×(n-1)×...×1 は順列と組合せの基礎である。極めて速く増大し、20! はすでに 64 ビット整数の範囲を超える。

関連ツール

高精度計算ツール

High-precision arithmetic calculator. No floating-point errors。無料、プライベート、100%クライアントサイド。

References