組合せ (数学)
数学において、組合せ（くみあわせ、英: combination, choose）とは、相異なる（あるいは区別可能な）いくつかの要素の集まりからいくつかの要素を（重複無く）選び出す方法である[1]。あるいは選び出した要素をその“並べる順番の違いを区別せずに”並べたもののことである[2]。組合せは組合せ論と呼ばれる数学の分野で研究される。卑近な例でいえば、デッキ（山札）から決まった数のカード（手札）を引くことや、ロトくじなどがその例である。
Contents
定義
位数 n の有限集合 E と非負整数 k に対し、集合 E に関する組合せとはこの集合の（有限）部分集合のことを言い、特に E に関する k-組合せ（あるいはもっと具体的に、与えられた n 個の元から k 個選んで得られる組合せ）とは E の k-元部分集合を言う。
E の k-組合せ全体の成す集合を 𝒫テンプレート:Ind(E) と表す[3][4]とき、𝒫テンプレート:Ind(E) の位数は有限であり、初等組合せ論においては Combination の頭文字を取って、テンプレート:MsubCテンプレート:Msub, Cテンプレート:Su, テンプレート:MsupCテンプレート:Msub, Cテンプレート:Msub または C(n, k) のような記号で表す。ただし、この数は数学のあらゆる分野に頻繁に現れ、大抵の場合 [math]\textstyle\binom{n}{k}[/math] と書かれる。特に二項定理
- [math](1+x)^n=\sum_{k=0}^{n}{n \choose k}x^k[/math]
に係数として現れることは顕著であり、これにより [math]\textstyle\binom{n}{k}[/math] はふつう二項係数と呼ばれる。二項展開の係数として数 [math]\textstyle\binom{n}{k}[/math] を定義するものと考えれば k = n または k = 0 のとき [math]\textstyle\binom{n}{k}=1[/math], k > n のとき [math]\textstyle\binom{n}{k}=0[/math] と考えるのは自然である。
実用上は個々の係数が具体的に
- [math]\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)[/math]
で与えられることを利用するのが簡便である。この式の分子は k-順列（k-個のものを“並べる順番の違いを区別して”並べたもの）を作る総数を表し、分母はそれら k-個の並べ替えの総数が k! であることを表し。並びだけが異なるそれらは同じ組合せを与えるものであるから、割っているのはそれらの違いを無視することに対応している。
組合せの数え上げ
A は n-元集合で、a は A に属さない元、k は非負整数とする。このとき、A ∪ {a} の k + 1 個の元からなる部分集合は、A の k + 1 個の元からなる部分集合か、さもなくば単元集合 {a} に A の k-元部分集合を併せたものであるから、
- [math]\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\} [/math]
と書ける。ただし、k > n のとき 𝒫テンプレート:Ind(A) = ∅ である。（この等式の位数は、パスカルの三角形を構成するのに用いる漸化式 [math]\tbinom{n+1}{k+1}=\tbinom{n}{k+1}+\tbinom{n}{k}[/math] に対応する）。
組合せの数の計算
n-元に対する k-組合せの総数を効率的に計算するために以下の等式が利用できる[5]。0 ≤ k ≤ n として:
- [math]\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.[/math]
最初の式は k ≤ n/2 なる場合に帰着するのに利用できるし、後の二つは
- [math]\binom{n}{k} = \frac{(n-k+1)}{1}\cdot\frac{(n-k+2)}{2}\cdot \dotsb \cdot \frac{n}{k} [/math]
となることを示せる。
注釈
- ↑ 岩波数学辞典, 184. 順列・組合せ p. 526.
- ↑ 伏見 1942, 第I章 数学的補助手段 1節 組合わせの理論.
- ↑ Louis Comtet, Analyse combinatoire élémentaire, テンプレート:Abréviation 2.
- ↑ Hervé Gianella, Romain Krust, Frank Taieb et Nicolas Tosel, Problèmes choisis de mathématiques supérieures, テンプレート:Abréviation 120.
- ↑ この式は例えば任意の精度の算術ライブラリである GMP が用いている。 Binomial coefficients algorithm を参照。
参考文献
- 西岡康夫 『数学チュートリアル やさしく語る 確率統計』 オーム社、2013年。ISBN 9784274214073。
- 伏見康治 『確率論及統計論』 河出書房、1942年。ISBN 9784874720127。
- 『数学辞典』 日本数学会編、岩波書店、2007年、第4版。ISBN 9784000803090。
関連項目
外部リンク
- Weisstein, Eric W. “Combination”. MathWorld（英語）. Template:Cite webの呼び出しエラー：引数 accessdate は必須です。
- Weisstein, Eric W. “Choose”. MathWorld（英語）. Template:Cite webの呼び出しエラー：引数 accessdate は必須です。
- Weisstein, Eric W. “k-Subset”. MathWorld（英語）. Template:Cite webの呼び出しエラー：引数 accessdate は必須です。