組合せ (数学)

「組合せ」はこの項目へ(転送)されています。その他の用法については「組合せ (曖昧さ回避)」をご覧ください。

数学において、組合せ（くみあわせ、英: combination, choose）とは、相異なる（あるいは区別可能な）いくつかの要素の集まりからいくつかの要素を（重複無く）選び出す方法である^[1]。あるいは選び出した要素をその“並べる順番の違いを区別せずに”並べたもののことである^[2]。組合せは組合せ論と呼ばれる数学の分野で研究される。身近な例でいえば、デッキ（山札）から決まった数のカード（手札）を引くことや、ロトくじなどがその例である。

定義

位数 n の有限集合 E と非負整数 k に対し、集合 E に関する組合せとはこの集合の（有限）部分集合のことを言い、特に E に関する k-組合せ（あるいはもっと具体的に、与えられた n 個の元から k 個選んで得られる組合せ）とは E の k-元部分集合を言う。

E の k-組合せ全体の成す集合を 𝒫_k(E) と表す^[3][4]とき、𝒫_k(E) の位数は有限であり、初等組合せ論においては Combination の頭文字を取って、_nC_k , Cn
k , ⁿC_k , C_n,k または C(n, k) のような記号で表す。(ピエール・エリゴン)（フランス語版）が1634年の『実用算術』で_nC_kの記号を定義した^[5]。ただし、この数は数学のあらゆる分野に頻繁に現れ、大抵の場合 ${\displaystyle \textstyle {\binom {n}{k}}}$  と書かれる。特に二項定理

${\displaystyle (1+x)^{n}=\sum _{k=0}^{n}{n \choose k}x^{k}}$ 

に係数として現れることは顕著であり、これにより ${\displaystyle \textstyle {\binom {n}{k}}}$  はふつう二項係数と呼ばれる。二項展開の係数として数 ${\displaystyle \textstyle {\binom {n}{k}}}$  を定義するものと考えれば k = n または k = 0 のとき ${\displaystyle \textstyle {\binom {n}{k}}=1}$ , k > n のとき ${\displaystyle \textstyle {\binom {n}{k}}=0}$  と考えるのは自然である。

実用上は個々の係数が具体的に

${\displaystyle {\binom {n}{k}}={\frac {n\times (n-1)\times \dotsb \times (n-k+1)}{k\times (k-1)\times \dotsb \times 1}}\left(={\frac {P(n,k)}{k!}}\right)}$ 

で与えられることを利用するのが簡便である。この式の分子は k-順列（k-個のものを“並べる順番の違いを区別して”並べたもの）を作る総数を表し、分母はそれら k-個の並べ替えの総数が k! であることを表し、並びだけが異なるそれらは同じ組合せを与えるものであるから、割っているのはそれらの違いを無視することに対応している。

組合せの数え上げ

A は n-元集合で、a は A に属さない元、k は非負整数とする。このとき、A ∪ {a} の k + 1 個の元からなる部分集合は、A の k + 1 個の元からなる部分集合か、さもなくば単元集合 {a} に A の k-元部分集合を併せたものであるから、

${\displaystyle {\mathcal {P}}_{k+1}(A\cup \{a\})={\mathcal {P}}_{k+1}(A)\cup \left\{X\cup \{a\}\mid X\in {\mathcal {P}}_{k}(A)\right\}}$ 

と書ける。ただし、k > n のとき 𝒫_k(A) = ∅ である。（この等式の位数は、パスカルの三角形を構成するのに用いる漸化式 ${\displaystyle {\tbinom {n+1}{k+1}}={\tbinom {n}{k+1}}+{\tbinom {n}{k}}}$  に対応する）。

組合せの数の計算

n-元に対する k-組合せの総数を効率的に計算するために以下の等式が利用できる^[6]。0 ≤ k ≤ n として:

${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}},\quad {\binom {n+1}{k+1}}={\frac {n+1}{k+1}}{\binom {n}{k}},\,{\binom {n}{0}}=1.}$ 

最初の式は k ≤ n/2 なる場合に帰着するのに利用できるし、後の二つは

${\displaystyle {\binom {n}{k}}={\frac {(n-k+1)}{1}}\cdot {\frac {(n-k+2)}{2}}\cdot \dotsb \cdot {\frac {n}{k}}}$ 

となることを示せる。

注釈

1. ^ 岩波数学辞典, 184. 順列・組合せ p. 526.
2. ^ 伏見 1942, p. 5, 第I章　数学的補助手段 1節 組合わせの理論.
3. ^ (Louis Comtet), Analyse combinatoire élémentaire, p. 2.
4. ^ Hervé Gianella, Romain Krust, Frank Taieb et Nicolas Tosel, Problèmes choisis de mathématiques supérieures, p. 120.
5. ^ 黒木哲徳『なっとくする数学記号』講談社〈ブルーバックス〉、2021年、96,97頁。ISBN (9784065225509)。 
6. ^ この式は例えば任意の精度の算術ライブラリである GMP が用いている。 Binomial coefficients algorithm を参照。

参考文献

• 西岡康夫『数学チュートリアル やさしく語る 確率統計』オーム社、2013年。ISBN (9784274214073)。 
• 伏見康治『確率論及統計論』河出書房、1942年。ISBN (9784874720127)。http://ebsa.ism.ac.jp/ebooks/ebook/204。 
• 日本数学会 編『数学辞典』（第4版）岩波書店、2007年。ISBN (9784000803090)。 

関連項目

• 重複組合せ
• 順列
• 重複順列
• 置換 (数学)
• 重複置換
• 写像12相
• 組合せ数学（組合せ論）

外部リンク

• Weisstein, Eric W. "Combination". MathWorld (英語).
• Weisstein, Eric W. "Choose". MathWorld (英語).
• Weisstein, Eric W. "k-Subset". MathWorld (英語).