組合せ (数学)

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

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

定義

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

テンプレート:Mvar の テンプレート:Mvar-組合せ全体の成す集合を テンプレート:Math と表すとき、テンプレート:Math の位数は有限であり、初等組合せ論においては テンプレート:Lang の頭文字を取って、テンプレート:Mvar または テンプレート:Math のような記号で表す。テンプレート:仮リンクが1634年の『実用算術』で テンプレート:Mvar の記号を定義した。ただし、この数は数学のあらゆる分野に頻繁に現れ、大抵の場合 $(\genfrac{}{}{0ex}{}{n}{k})$ と書かれる。特に二項定理

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

に係数として現れることは顕著であり、これにより $(\genfrac{}{}{0ex}{}{n}{k})$ はふつう二項係数と呼ばれる。二項展開の係数として数 $(\genfrac{}{}{0ex}{}{n}{k})$ を定義するものと考えれば テンプレート:Math2 または テンプレート:Math2 のとき $(\genfrac{}{}{0ex}{}{n}{k})=1$, テンプレート:Math2 のとき $(\genfrac{}{}{0ex}{}{n}{k})=0$ と考えるのは自然である。

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

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n\times (n-1)\times \cdots \times (n-k+1)}{k\times (k-1)\times \cdots \times 1}(=\frac{P(n,k)}{k!})$

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

組合せの数え上げ

テンプレート:Mvar は テンプレート:Mvar-元集合で、テンプレート:Mvar は テンプレート:Mvar に属さない元、テンプレート:Mvar は非負整数とする。このとき、テンプレート:Math2の テンプレート:Math2 個の元からなる部分集合は、テンプレート:Mvar の テンプレート:Math2 個の元からなる部分集合か、さもなくば単集合 テンプレート:Mathに テンプレート:Mvar の テンプレート:Mvar-元部分集合を併せたものであるから、

${𝒫}_{k+1}(A\cup \{a\})={𝒫}_{k+1}(A)\cup \{X\cup \{a\}\mid X\in {𝒫}_k(A)\}$

と書ける。ただし、テンプレート:Math2 のとき テンプレート:Math である。（この等式の位数は、パスカルの三角形を構成するのに用いる漸化式 $(\genfrac{}{}{0ex}{}{n+1}{k+1})=(\genfrac{}{}{0ex}{}{n}{k+1})+(\genfrac{}{}{0ex}{}{n}{k})$ に対応する）。

組合せの数の計算

テンプレート:Mvar-元に対する テンプレート:Mvar-組合せの総数を効率的に計算するために以下の等式が利用できる。テンプレート:Math2 として:

$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n}{n-k}),(\genfrac{}{}{0ex}{}{n+1}{k+1})=\frac{n+1}{k+1}(\genfrac{}{}{0ex}{}{n}{k}),(\genfrac{}{}{0ex}{}{n}{0})=1.$

最初の式は テンプレート:Math2 なる場合に帰着するのに利用できるし、後の2つは

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n-k+1}{1}\cdot \frac{n-k+2}{2}\cdot \cdots \cdot \frac{n}{k}$

となることを示せる。

参考文献

• テンプレート:Cite book
• テンプレート:Cite book
• テンプレート:Cite book

関連項目

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

外部リンク

• テンプレート:MathWorld
• テンプレート:MathWorld
• テンプレート:MathWorld