有限組合せ

ウィキペディア

有限組合せ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/01/05 07:50 UTC 版)

有限組合せ（ゆうげんくみあわせ）とは、組合せ論や数え上げ数学などで扱う「組合せの数」を考察するのではなく、「組合せの実体」を閉じた数式（漸化式を含む）で算出する方法を探索する数学のことである。

「組合せの実体」とは、組合せそのものである。例えば、組合せの要素を $1,\,2,\,3$とするとき、 この3つから、繰り返しを許さず２つを取り出した組合せは、 $\langle \,1,\,2\,\rangle$, $\langle \,1,\,3\,\rangle$, $\langle \,2,\,3\,\rangle$である。 この $\langle \,1,\,2\,\rangle$, $\langle \,1,\,3\,\rangle$, $\langle \,2,\,3\,\rangle$が「組合せの実体」ということになる。

組合せの算出

組合せの全てを算出する数式

繰り返しを許さない組合せの総数 $C(n,\,r)$は、

$\,\,\,\,\,$ $C(n,\,r)={\frac {n!}{r!\,(n-r)!}}$

で与えられる。 この"繰り返しを許さない組合せ"に関して、 $n$と $r$を与えて、総数 $C(n,\,r)$個の組合せ全てを代数計算で算出する数式が"researchmap"に報告されている。 論文タイトルは「繰り返しを許さない組合せの各組を全て算出できる数式」で、2018年12月12日付けで「researchmap」へ下記の数式（漸化式）が提出されている。

• $\,\,$ $\langle \,b_{1},b_{2},\ldots ,b_{k},\ldots ,b_{r}\,\rangle ,$ $\,\,$（組合せの表示）
• $\,\,$ $b_{k}=b_{k-1}+t_{k-1},$
• $\,\,$ $t_{k-1}=1,2,\ldots ,n-r+k-b_{k-1},$
• $\,\,$ $k=1,2,\ldots ,r.$
• $\,\,$ $b_{0}=0,$ $\,\,$（定義）
• $\,\,$ $r\leq n.$

ここに、 $n,\,r,\,k,\,b_{k}$は、すべて正の整数とする。

算出された要素の表示方法

数式 $b_{k}=b_{k-1}+t_{k-1}$ を用いて算出した組合せ要素の表示方法を示す．

長島の組合せ網羅漸化式

を用いて組合せ要素の算出を行い、表示する場合に大切な事は「算出に用いた $b_{k-1}$のすぐ右隣に、ひとつずつ、算出された複数のすべての $b_{k}$を書き並べる」という操作である。式で表すと、

$\,\,$ $\langle \,\ldots ,b_{k-1},\,\,b_{k-1}+1,\,\ldots \,\rangle ,$

$\,\,$ $\langle \,\ldots ,b_{k-1},\,\,b_{k-1}+2,\,\ldots \,\rangle ,$

$\,\,$ $\langle \,\ldots ,b_{k-1},\,\,b_{k-1}+3,\,\ldots \,\rangle ,$

$\,\,$ $\,\ldots \,\ldots \,\ldots \,\ldots \,,$

$\,\,$ $\langle \,\ldots ,b_{k-1},\,\,b_{k-1}+t_{k-1},\,\ldots \,\rangle ,$

$\,\,$ $\,\ldots \,\ldots \,\ldots \,\ldots \,,$

$\,\,$ $\langle \,\ldots ,b_{k-1},\,\,n-r+k-1,\,\ldots \,\rangle ,$

$\,\,$ $\langle \,\ldots ,b_{k-1},\,\,n-r+k,\,\ldots \,\rangle$

となる。

関連項目

組合せ論

初等組合せ論

有限組合せ論

数え上げ組合せ論

組合せ数学