「組合せ (数学)」の版間の差分
Knotopologynn (会話 | 投稿記録) m 新しい数式として、全組合せを網羅できる計算式を投稿した。 |
rv. 意味のない数式: Knotopologynn (会話) による ID:73364535 の版を取り消し タグ: 取り消し |
||
25行目: | 25行目: | ||
: <math>\binom{n}{k} = \frac{(n-k+1)}{1}\cdot\frac{(n-k+2)}{2}\cdot \dotsb \cdot \frac{n}{k} |
: <math>\binom{n}{k} = \frac{(n-k+1)}{1}\cdot\frac{(n-k+2)}{2}\cdot \dotsb \cdot \frac{n}{k} |
||
</math> |
</math> |
||
となることを示せる。 |
となることを示せる。 |
||
<br /> |
|||
== 全組合せを網羅する計算 == |
|||
繰り返しを許さない組合せにおいて、総数が <math>\tbinom{n}{k}</math> 個の全ての組合せを算出できる数式として、 |
|||
下記の式が一般に公開されている<ref name="combin-reseamap-2018">長島 隆廣[繰り返しを許さない組合せの各組を全て算出できる数式]researchmap, 2018年12月. 論文PDF:https://researchmap.jp/T_Nagashima/</ref>。 |
|||
:::* <math>\; b_w = b_{w-1}+ t_{w-1},</math> |
|||
:::* <math>\; t_{w-1}=1,2,\ldots,n-k+w-b_{w-1},</math> |
|||
:::* <math>\; w=1,2,\ldots,k,</math> |
|||
:::* <math>b_0 =0. \;</math>'''(定義)'''。 |
|||
== 注釈 == |
== 注釈 == |
||
57行目: | 41行目: | ||
* [[置換 (数学)]] |
* [[置換 (数学)]] |
||
* [[重複置換]] |
* [[重複置換]] |
||
* {{仮リンク|12 |
* {{仮リンク|写像12相|en|Twelvefold way}} |
||
== 外部リンク == |
== 外部リンク == |
2019年7月6日 (土) 12:40時点における版
数学において、組合せ(くみあわせ、英: combination, choose)とは、相異なる(あるいは区別可能な)いくつかの要素の集まりからいくつかの要素を(重複無く)選び出す方法である[1]。あるいは選び出した要素をその“並べる順番の違いを区別せずに”並べたもののことである[2]。組合せは組合せ論と呼ばれる数学の分野で研究される。卑近な例でいえば、デッキ(山札)から決まった数のカード(手札)を引くことや、ロトくじなどがその例である。
定義
位数 n の有限集合 E と非負整数 k に対し、集合 E に関する組合せとはこの集合の(有限)部分集合のことを言い、特に E に関する k-組合せ(あるいはもっと具体的に、与えられた n 個の元から k 個選んで得られる組合せ)とは E の k-元部分集合を言う。
E の k-組合せ全体の成す集合を 𝒫k(E) と表す[3][4]とき、𝒫k(E) の位数は有限であり、初等組合せ論においては Combination の頭文字を取って、nCk, Cn
k, nCk, Cn,k または C(n, k) のような記号で表す。ただし、この数は数学のあらゆる分野に頻繁に現れ、大抵の場合 と書かれる。特に二項定理
に係数として現れることは顕著であり、これにより はふつう二項係数と呼ばれる。二項展開の係数として数 を定義するものと考えれば k = n または k = 0 のとき , k > n のとき と考えるのは自然である。
実用上は個々の係数が具体的に
で与えられることを利用するのが簡便である。この式の分子は k-順列(k-個のものを“並べる順番の違いを区別して”並べたもの)を作る総数を表し、分母はそれら k-個の並べ替えの総数が k! であることを表し、並びだけが異なるそれらは同じ組合せを与えるものであるから、割っているのはそれらの違いを無視することに対応している。
組合せの数え上げ
A は n-元集合で、a は A に属さない元、k は非負整数とする。このとき、A ∪ {a} の k + 1 個の元からなる部分集合は、A の k + 1 個の元からなる部分集合か、さもなくば単元集合 {a} に A の k-元部分集合を併せたものであるから、
と書ける。ただし、k > n のとき 𝒫k(A) = ∅ である。(この等式の位数は、パスカルの三角形を構成するのに用いる漸化式 に対応する)。
組合せの数の計算
n-元に対する k-組合せの総数を効率的に計算するために以下の等式が利用できる[5]。0 ≤ k ≤ n として:
最初の式は k ≤ n/2 なる場合に帰着するのに利用できるし、後の二つは
となることを示せる。
注釈
- ^ 岩波数学辞典, 184. 順列・組合せ p. 526.
- ^ 伏見 1942, p. 5, 第I章 数学的補助手段 1節 組合わせの理論.
- ^ Louis Comtet, Analyse combinatoire élémentaire, p. 2.
- ^ Hervé Gianella, Romain Krust, Frank Taieb et Nicolas Tosel, Problèmes choisis de mathématiques supérieures, p. 120.
- ^ この式は例えば任意の精度の算術ライブラリである GMP が用いている。 Binomial coefficients algorithm を参照。
参考文献
- 西岡康夫『数学チュートリアル やさしく語る 確率統計』オーム社、2013年。ISBN 9784274214073。
- 伏見康治『確率論及統計論』河出書房、1942年。ISBN 9784874720127 。
- 日本数学会編 編『数学辞典』(第4版)岩波書店、2007年。ISBN 9784000803090。
関連項目
外部リンク
- Weisstein, Eric W. "Combination". mathworld.wolfram.com (英語).
- Weisstein, Eric W. "Choose". mathworld.wolfram.com (英語).
- Weisstein, Eric W. "k-Subset". mathworld.wolfram.com (英語).