組合せ（数学）とは？公式・例・性質をわかりやすく解説

記法と基本公式

n 個の要素から k 個を選ぶ方法の数（0 ≤ k ≤ n）は、通常「n 個から k 個を選ぶ」と表し、C(n,k)、nCk、あるいは二項係数の記法で (n k) と書きます。閉じた形では n! / (k!(n − k)!) で計算できます。ここで n!（階乗）は 1·2·3·…·n を意味します。この式は、順序付きの選び方（k 個の異なる要素の順列）の総数を、1 つの選ばれた部分集合につき何通りの並べ方があるかで割ることで、異なる k 要素部分集合の個数を数えています。式中で用いる階乗については階乗を参照してください。

例と、順序と選択の違い

簡単な例として、6 人の委員会から 3 人を選ぶと、C(6,3) = 20 通りの組合せがあります。もし順序が重要なら、3 人の各組合せは 3! = 6 通りに並べ替えられるので、順序付きリストは合計 120 通りになります。したがって、順列は一般に組合せより数が多く、順列は区別する並べ方を、組合せは同じ集合として扱う点が異なります。順序が重要な配置については順列も参照してください。

変種と便利な性質

• 境界の場合: C(n,0) = C(n,n) = 1。通常の「重複なし」の解釈では、k > n のとき C(n,k) = 0 です。
• 対称性: C(n,k) = C(n,n−k)。これは階乗の公式から直接従い、k 個を選んで含めることは、n−k 個を選んで除外することに等しい、という事実を表しています。
• パスカルの恒等式: C(n,k) = C(n−1,k−1) + C(n−1,k)。これはパスカルの三角形や多くの帰納的議論の基礎になります。
• 重複を許す場合（多重集合）には、n 種類から k 個を選ぶ数は C(n+k−1,k) です。これは、分割や stars-and-bars の議論で用いられる標準的な変種です。

応用と計算上の注意

組合せは、確率論、統計学、数え上げ組合せ論、アルゴリズム設計などの幅広い分野に現れます。二項係数は二項定理の係数であり、有限集合における所定の大きさの部分集合の数を数えるため、事象の確率計算や組合せ的証明に役立ちます。計算機で大きな n choose k を求めるときは、非常に大きな階乗を直接計算するのを避け、丸め誤差やオーバーフローを抑えるために、乗法的な公式や動的計画法（パスカルの三角形）がよく使われます。

定義が सरल明快で応用範囲も広いため、組合せと二項係数は、有限の選択、順序を考えない標本抽出、多くの初等的な数え上げ問題を考えるうえで、今なお基本的な道具となっています。