組合せ (数学)

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

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

日常では組合せとは要素が2個以上の物を示すが、数学においては要素が1個や0個の場合も組合せの内に含めて考える。

定義

位数 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 {\tbinom {n}{k}}}$ と書かれる。特に二項定理

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

に係数として現れることは顕著であり、これにより ${\displaystyle {\tbinom {n}{k}}}$ はふつう二項係数と呼ばれる。二項展開の係数として数 ${\displaystyle {\tbinom {n}{k}}}$ を定義するものと考えれば k = n または k = 0 のとき ${\displaystyle {\tbinom {n}{k}}=1}$, k > n のとき ${\displaystyle {\tbinom {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 なる場合に帰着するのに利用できるし、後の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。https://www.jstage.jst.go.jp/article/jsmemag/46/313/46_KJ00003058243/_article/-char/ja/。
• 日本数学会 編『数学辞典』（第4版）岩波書店、2007年。ISBN 9784000803090。

関連項目

• 組合せ数学
• 重複組合せ
• 順列
• 重複順列
• 完全順列
• 場合の数
• 数え上げ
• 数え上げ数学
• 置換 (数学)
• 重複置換
• 写像12相
• 樹形図

外部リンク

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