組合せ (数学)のソースを表示

{{Redirect|組合せ}}
{{Expand English|Combination|date=2024-05}}
[[数学]]において、'''組合せ'''（くみあわせ、{{lang-en-short|combination, choose}}）とは、有限個の互いに区別可能な要素の集まりから有限個を選び出す方法である{{sfn|岩波数学辞典|loc=184. 順列・組合せ p.526}}。あるいは選び出した要素をその“並べる順番の違いを区別せずに”並べたもののことである{{sfn|伏見|1942|loc=第I章　数学的補助手段 1節 組合わせの理論|p=5}}。組合せは[[組合せ数学]]と呼ばれる数学の分野で研究される。身近な例でいえば、デッキ（山札）から決まった数のカード（手札）を引くことや、ロトくじなどがその例である。

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

== 定義 ==
[[位数 (群論)|位数]] {{mvar|n}} の[[有限集合]] {{mvar|E}} と非負整数 {{mvar|k}} に対し、集合 {{mvar|E}} に関する'''組合せ'''とはこの集合の（有限）[[部分集合]]のことを言い、特に {{mvar|E}} に関する {{mvar|k}}-組合せ（あるいはもっと具体的に、与えられた {{mvar|n}} 個の元から {{mvar|k}} 個選んで得られる組合せ）とは {{mvar|E}} の {{mvar|k}}-元部分集合を言う。

{{mvar|E}} の {{mvar|k}}-組合せ全体の成す集合を {{math|𝒫{{sub|''k''}}(''E'')}} と表す<ref>[[Louis Comtet]], ''Analyse combinatoire élémentaire'', [https://books.google.fr/books?id=Mx6Va5RiENEC&pg=PA2 {{p.|2}}].</ref><ref>Hervé Gianella, Romain Krust, Frank Taieb et Nicolas Tosel, ''Problèmes choisis de mathématiques supérieures'', [https://books.google.fr/books?id=TySkMs-B_JkC&pg=PA120 {{p.|120}}].</ref>とき、{{math|𝒫{{sub|''k''}}(''E'')}} の位数は有限であり、初等組合せ論においては {{lang|en|'''C'''ombination}} の頭文字を取って、{{mvar|{{sub|n}}C{{sub|k}} , C{{su|p=n|b=k}} , {{sup|n}}C{{sub|k}} , C{{sub|n,k}}}} または {{math|''C''(''n'', ''k'')}} のような記号で表す。{{仮リンク|ピエール・エリゴン|fr|Pierre Hérigone}}が1634年の『実用算術』で {{mvar|{{sub|n}}C{{sub|k}}}} の記号を定義した<ref>{{Cite|和書 |author=黒木哲徳 |title=なっとくする数学記号 |series=ブルーバックス |publisher=講談社 |year=2021 |pages=96,97 |isbn=9784065225509 |ref=harv}}</ref>。ただし、この数は数学のあらゆる分野に頻繁に現れ、大抵の場合 <math>\tbinom{n}{k}</math> と書かれる。特に[[二項定理]]
:<math>(1+x)^n = \textstyle\sum\limits_{k=0}^n \dbinom{n}{k} x^k</math>
に係数として現れることは顕著であり、これにより <math>\tbinom{n}{k}</math> はふつう'''[[二項係数]]'''と呼ばれる。二項展開の係数として数 <math>\tbinom{n}{k}</math> を定義するものと考えれば {{math2|1=''k'' = ''n''}} または {{math2|1=''k'' = 0}} のとき <math>\tbinom{n}{k}=1</math>, {{math2|''k'' > ''n''}} のとき <math>\tbinom{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>
で与えられることを利用するのが簡便である。この式の分子は {{mvar|k}}-[[順列]]（{{mvar|k}}個のものを“並べる順番の違いを区別して”並べたもの）を作る総数を表し、分母はそれら {{mvar|k}}個の並べ替えの総数が {{math|''k''!}} であることを表し、並びだけが異なるそれらは同じ組合せを与えるものであるから、割っているのはそれらの違いを無視することに対応している。

== 組合せの数え上げ ==
{{mvar|A}} は {{mvar|n}}-元集合で、{{mvar|a}} は {{mvar|A}} に属さない元、{{mvar|k}} は非負整数とする。このとき、{{math2|''A'' ∪ {''a''} }}の {{math2|''k'' + 1}} 個の元からなる部分集合は、{{mvar|A}} の {{math2|''k'' + 1}} 個の元からなる部分集合か、さもなくば[[単集合]] {{math|{''a''} }}に {{mvar|A}} の {{mvar|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>
と書ける。ただし、{{math2|''k'' > ''n''}} のとき {{math|1=𝒫{{sub|''k''}}(''A'') = &empty;}} である。（この等式の位数は、[[パスカルの三角形]]を構成するのに用いる[[漸化式]] <math>\tbinom{n+1}{k+1} = \tbinom{n}{k+1} + \tbinom{n}{k}</math> に対応する）。

== 組合せの数の計算 ==
{{mvar|n}}-元に対する {{mvar|k}}-組合せの総数を効率的に計算するために以下の等式が利用できる<ref>この式は例えば任意の精度の算術[[ライブラリ]]である [[GNU Multi-Precision Library|GMP]] が用いている。{{en}} [https://gmplib.org/manual/Binomial-Coefficients-Algorithm Binomial coefficients algorithm] を参照。</ref>。{{math2|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>
最初の式は {{math2|''k'' ≤ {{sfrac|''n''|2}}}} なる場合に帰着するのに利用できるし、後の2つは
:<math>\binom{n}{k} = \frac{n-k+1}{1}\cdot\frac{n-k+2}{2}\cdot \dotsb \cdot \frac{n}{k}</math>
となることを示せる。

== 注釈 ==
{{Reflist}}

== 参考文献 ==
* {{Cite book|和書 |author=西岡康夫 |title=数学チュートリアル やさしく語る 確率統計 |publisher=[[オーム社]] |year=2013 |isbn=9784274214073 |ref={{sfnref|西岡|2013}}}}
* {{Cite book|和書 |author=[[伏見康治]] |title=確率論及統計論 |url=https://www.jstage.jst.go.jp/article/jsmemag/46/313/46_KJ00003058243/_article/-char/ja/ |publisher=[[河出書房]] |year=1942 |isbn=9784874720127 |ref={{sfnref|伏見|1942}}}}
* {{Cite book|和書 |editor=[[日本数学会]] |title=数学辞典 |edition=第4版 |publisher=[[岩波書店]] |year=2007 |isbn=9784000803090 |ref={{sfnref|岩波数学辞典}}}}

== 関連項目 ==
* [[組合せ数学]]
* [[重複組合せ]]
* [[順列]]
* [[重複順列]]
* [[完全順列]]
* [[場合の数]]
* [[数え上げ]]
* [[数え上げ数学]]
* [[置換 (数学)]]
* [[重複置換]]
* [[写像12相]]
* [[樹形図]]

== 外部リンク ==
* {{MathWorld |title=Combination |urlname=Combination}}
* {{MathWorld |title=Choose |urlname=Choose}}
* {{MathWorld |title=k-Subset |urlname=k-Subset}}

{{DEFAULTSORT:くみあわせ}}
[[Category:組合せ論|*]]
[[Category:数学に関する記事]]