組合せを算出する数式の研究（組合せ数学）

この場では、組合せ数学に関して、一般に公開されている研究を紹介し、その研究について考察する。公開されている研究の内容は、論文：繰り返しを許さない組合せの各組を全て算出できる数式 ^[1] に記述されている組合せ数学に関する問題である。

一般に、組合せ数学では、組合せの数（総数）を計算する目的のもとで研究され、議論されることが多い。

組合せには、繰り返し（重複）を許す場合と、繰り返し（重複）を許さない場合の二通りがある。ここでは常に、繰り返しを許さない組合せの場合のみを扱う。繰り返しを許さない組合せの総数 C(n, r) が、

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

で与えられることは周知である。この総数 C(n, r) 種類の組合せについて、その全てを計算式で算出する方法を以下で示し考察する。

現在までの組合せに関する数学の理論には、組合せそのものの実体を網羅して書き出すために用いる計算式としての数式が存在しない。したがって、辞書 ^[2] ^[3] ^[4] ^[5] ^[6] ^[7] や解説書 ^[8] ^[9] ^[10] などの、どこにもその数式は記述されていない。コンピュータを用いて計算するためのプログラムは数多く存在するが、これらのプログラムは計算式として用いるための数式ではない。

以下では，組合せそのものの実体を網羅して書き出すために計算式として用いる数式を示す。

組合せの各組を全て算出できる漸化式

以下で示す組合せの算出方法は、前掲の論文に記述されている方法である。なお、n は選ぶ候補の数で、r は選択の回数である。n と r は、いずれも正の整数である。

まず、組合せの要素を、正の整数 1, 2, 3, . . . , n. または、 b₁, b₂, b₃, . . . , b_nで表示し、組合せを〈1, 2, 3, . . . , r〉または、〈b₁, b₂, b₃, . . . , b_r〉で表示する。ここに、 b₁, b₂, b₃, . . . , b_r, . . . , b_n は全て、正の整数とする。

公開されている研究論文では計算式として、以下の漸化式を用いて組合せを算出している。

$\;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.$

ここに、n, r, k, b_k は、すべて正の整数とする。なお、r と n は、r ≤ n を満たすものとする。

定義1.

k = 1 の場合、b_k−1 = b₁₋₁ = b₀ から得られる b₀ を、

b_{0}=0

と定義する。

組合せの表示方法

次に、組合せの要素が算出されたあと、 組合せの各組を表示するとき、必ず守る必要がある基本的な表示方法を以下で示す。

$\;\langle \,\ldots ,\;b_{k-1},\quad b_{k-1}+1,\;\ldots \,\rangle ,$
$\;\langle \,\ldots ,\;b_{k-1},\quad b_{k-1}+2,\;\ldots \,\rangle ,$
$\;\quad \ldots \ldots \ldots \ldots \ldots \ldots \ldots ,$
$\;\langle \;\ldots ,\;b_{k-1},\quad b_{k-1}+t_{k-1},\;\ldots \,\rangle ,$
$\;\quad \ldots \ldots \ldots \ldots \ldots \ldots \ldots ,$
$\;\langle \;\ldots ,\;b_{k-1},\quad n-r+k-1,\;\ldots \,\rangle ,$
$\;\langle \;\ldots ,\;b_{k-1},\quad n-r+k,\;\ldots \,\rangle .$

この上式が、組合せの各組を表示するとき、必ず守る必要がある基本的な表示方法を数式の一般項で示したものである。くだけた、分かり易い言い方をすると、 { 1, 2, . . . , n } を 1 から n までの正の整数の集合とし、 α, β, γ, δ, ε, ζ を、この集合の元、 α, β, γ, δ, ε, ζ ∈ { 1, 2, . . . , n } とする。この時、α（b_k−1に相当）を用いて算出された要素を、 β, γ, δ, ε, ζ（b_kに相当）とすると、組合せは以下のように表示しなければならない。

\;\langle \,\ldots ,\;\alpha ,\;\beta ,\;\ldots \,\rangle ,

\;\langle \,\ldots ,\;\alpha ,\;\gamma ,\;\ldots \,\rangle ,

\;\langle \,\ldots ,\;\alpha ,\;\delta ,\;\ldots \,\rangle ,

\;\langle \,\ldots ,\;\alpha ,\;\epsilon ,\;\ldots \,\rangle ,

\;\langle \,\ldots ,\;\alpha ,\;\zeta ,\;\ldots \,\rangle .

もし、α が b₁ ならば、算出された組合せは、

\;\langle \;\alpha ,\;\beta ,\;\ldots \,\rangle ,

\;\langle \;\alpha ,\;\gamma ,\;\ldots \,\rangle ,

\;\langle \;\alpha ,\;\delta ,\;\ldots \,\rangle ,

\;\langle \;\alpha ,\;\epsilon ,\;\ldots \,\rangle ,

\;\langle \;\alpha ,\;\zeta ,\;\ldots \,\rangle

と書く必要がある。

これが、組合せの各組を表示するとき、必ず守る必要がある基本的な表示方法と言うことになる。

数値を用いた組合せの計算例と表示の例

以下で数値を用いた例題を計算してみる。例として、n = 6、r = 2 を計算する。この場合、組合せの総数 C(6, 2) は、 C(6, 2) = 15 である。したがって、15通りの組合せが計算される。まず、前述の漸化式に、n = 6、r = 2 を適用すると、漸化式が下記のように書ける。

$\;$ $b_{k}=b_{k-1}+t_{k-1},$
$\;$ $t_{k-1}=1,2,\ldots ,6-2+k-b_{k-1},$
$\;$ $k=1,2,\ldots ,2.$

上記の式を整理して書き直すと下記の式を得る。

$\;$ $b_{k}=b_{k-1}+t_{k-1},$
$\;$ $t_{k-1}=1,2,\ldots ,4+k-b_{k-1},$
$\;$ $k=1,2.$

次に、上式について、k = 1 および k = 2 を適用して書き表すと、以下の式を得る。

$\,\,$ $k=1.\qquad b_{1}=b_{0}+t_{0},\qquad t_{0}=1,2,\ldots ,5-b_{0}.$
$\,\,$ $k=2.\qquad b_{2}=b_{1}+t_{1},\qquad t_{1}=1,2,\ldots ,6-b_{1}.$

ここで、上記の b₁ = b₀ + t₀ および、 t₀ = 1, 2, . . . , 5 − b₀ に対して、定義、 b₀ = 0 を適用すると、b₁ と t₀ が、

b_{1}=0+t_{0}=t_{0},

t_{0}=1,2,\ldots ,5-0=1,2,\ldots ,5

となるので、b₁ として、

b_{1}=1,2,\ldots ,5

が得られる。すなわち、b₁ として、 b₁ = 1, 2, 3, 4, 5 の5種類の要素が算出されたことになる。これにより、計算途中の組合せは、

\langle \,1,\;\star \,\rangle ,\quad \langle \,2,\;\star \,\rangle ,\quad \langle \,3,\;\star \,\rangle ,\quad \langle \,4,\;\star \,\rangle ,\quad \langle \,5,\;\star \,\rangle

と書ける。ここで、上式の星印（ $\star$ ）は、次に算出される b₂ を書き込む位置である。したがって、r = 2 の組合せとしては、 $\langle \,b_{1},\;b_{2}\rangle$ と書ける。次に、 b₂ を算出する計算を示す。前述の式、 b₂ = b₁ + t₁、 t₁ = 1, 2, . . . , 6 − b₁ を用いる。いま、b₁ = 1, 2, 3, 4, 5 であるから、t₁ は、 b₁ = 1、 b₁ = 2、 b₁ = 3、 b₁ = 4、 b₁ = 5 を t₁ に適用すると、

$\;t_{1}=1,\,2,\,3,\,4,\,5,\qquad (b_{1}=1),$
$\;t_{1}=1,\,2,\,3,\,4,\qquad (b_{1}=2),$
$\;t_{1}=1,\,2,\,3,\qquad (b_{1}=3),$
$\;t_{1}=1,\,2,\qquad (b_{1}=4),$
$\;t_{1}=1,\qquad (b_{1}=5)$

となる。これにより、 b₂ = b₁ + t₁ を用いて計算すると、 b₂ が下記のように得られる。

$\;b_{2}=2,\,3,\,4,\,5,\,6,\qquad (b_{1}=1),$
$\;b_{2}=3,\,4,\,5,\,6,\qquad (b_{1}=2),$
$\;b_{2}=4,\,5,\,6,\qquad (b_{1}=3),$
$\;b_{2}=5,\,6,\qquad (b_{1}=4),$
$\;b_{2}=6,\qquad (b_{1}=5).$

次に、これらの b₂ を、

\langle \,1,\;\star \,\rangle ,\quad \langle \,2,\;\star \,\rangle ,\quad \langle \,3,\;\star \,\rangle ,\quad \langle \,4,\;\star \,\rangle ,\quad \langle \,5,\;\star \,\rangle

の星印（ $\star$ ）の位置に配置する。この時、組合せの各組を表示するとき、必ず守る必要がある基本的な表示方法が適用される。

まず、上式の b₂ = 2, 3, 4, 5, 6, (b₁ = 1) を $\langle \,1,\;\star \,\rangle$ の $\;\star$ の位置へ配置する。これを表示すると、以下のようになる。

\langle \,1,\;2\,\rangle ,\quad \langle \,1,\;3\,\rangle ,\quad \langle \,1,\;4\,\rangle ,\quad \langle \,1,\;5\,\rangle ,\quad \langle \,1,\;6\,\rangle .

次に、b₁ = 2 のときは、b₂ = 3, 4, 5, 6 であるから、組合せは,以下のように書ける。

\langle \,2,\;3\,\rangle ,\quad \langle \,2,\;4\,\rangle ,\quad \langle \,2,\;5\,\rangle ,\quad \langle \,2,\;6\,\rangle .

次に、b₁ = 3 のときは、b₂ = 4, 5, 6 であるから、組合せは,以下のように書ける。

\langle \,3,\;4\,\rangle ,\quad \langle \,3,\;5\,\rangle ,\quad \langle \,3,\;6\,\rangle .

次に、b₁ = 4 のときは、b₂ = 5, 6 であるから、組合せは、以下のように書ける。

\langle \,4,\;5\,\rangle ,\quad \langle \,4,\;6\,\rangle .

最後に、b₁ = 5 のときは、b₂ = 6 であるから、組合せは、以下のように書ける。

\langle \,5,\;6\,\rangle .

以上の通り、n = 6、r = 2 の場合、漸化式により計算した算出の結果を以下に示す。

\langle \,1,\;2\,\rangle ,\quad \langle \,1,\;3\,\rangle ,\quad \langle \,1,\;4\,\rangle ,\quad \langle \,1,\;5\,\rangle ,\quad \langle \,1,\;6\,\rangle ,\quad \langle \,2,\;3\,\rangle ,\quad \langle \,2,\;4\,\rangle ,\quad \langle \,2,\;5\,\rangle ,\quad \langle \,2,\;6\,\rangle ,

\langle \,3,\;4\,\rangle ,\quad \langle \,3,\;5\,\rangle ,\quad \langle \,3,\;6\,\rangle ,\quad \langle \,4,\;5\,\rangle ,\quad \langle \,4,\;6\,\rangle ,\quad \langle \,5,\;6\,\rangle .

上に示した 15通りの組合せは、繰り返しを許さない組合せの総数 C(6, 2) が、

C(6,\,2)={\frac {6!}{2!\,(6-2)!}}=15

と計算されるので、漸化式による計算結果と総数が一致し、算出結果の正当性が確かめられる。

実際に、上述した15通りの組合せ〈1, 2〉から〈5, 6〉までは、 1，2，3，4，5，6 の 6 つから 2 つを取り出した組合せとして正しいことは明らかである。

漸化式による正しい算出結果の n と r の表

前述で示した漸化式を用いて算出計算し、正しい結果を得た、n と r の組みを表にして、以下に載せておく。

表1. 漸化式で算出し、正しい結果を得た n と r の表
$\quad \qquad$	r = 1	r = 2	r = 3	r = 4	r = 5	r = 7
n = 1	$\;$ n = 1, $\;\;$ r = 1	$\qquad$ — $\qquad$	$\qquad$ — $\qquad$	$\qquad$ — $\qquad$	$\qquad$ — $\qquad$	$\qquad \;$ — $\qquad$
n = 2	$\;$ n = 2, $\;\;$ r = 1	$\;$ n = 2, $\;\;$ r = 2	$\qquad$ — $\qquad$	$\qquad$ — $\qquad$	$\qquad$ — $\qquad$	$\qquad \;$ — $\qquad$
n = 3	$\;$ n = 3, $\;\;$ r = 1	$\;$ n = 3, $\;\;$ r = 2	$\;$ n = 3, $\;\;$ r = 3	$\qquad$ — $\qquad$	$\qquad$ — $\qquad$	$\qquad \;$ — $\qquad$
n = 4	$\;$ n = 4, $\;\;$ r = 1	$\;$ n = 4, $\;\;$ r = 2	$\;$ n = 4, $\;\;$ r = 3	$\;$ n = 4, $\;\;$ r = 4	$\qquad$ — $\qquad$	$\qquad \;$ — $\qquad$
n = 5	$\;$ n = 5, $\;\;$ r = 1	$\;$ n = 5, $\;\;$ r = 2	$\;$ n = 5, $\;\;$ r = 3	$\;$ n = 5, $\;\;$ r = 4	$\;$ n = 5, $\;\;$ r = 5	$\qquad \;$ — $\qquad$
n = 7	$\qquad \;$ — $\qquad$	$\qquad \;$ — $\qquad$	$\qquad \;$ — $\qquad$	$\qquad \;$ — $\qquad$	$\;$ n = 7, $\;\;$ r = 5	$\qquad \;$ — $\qquad$
n = 9	$\qquad \;$ — $\qquad \;$	$\qquad \;$ — $\qquad \;$	$\qquad \;$ — $\qquad \;$	$\qquad \;$ — $\qquad \;$	$\qquad \;$ — $\qquad \;$	$\;\;$ n = 9, $\;\;$ r = 7 $\;\;$

漸化式の反例

漸化式の反例を探し出す計算を行ってはいるが、今現在までのところ、反例の存在を確認してはいない。（2019/07/01）

命題(1). 漸化式、

{\begin{cases}\qquad \langle \,b_{1},\;b_{2},\ldots ,b_{k},\ldots ,b_{r}\rangle ,\quad ({\text{組 }}{\text{ 合 }}{\text{ せ }}\;)\\[2ex]\;\;b_{k}=b_{k-1}+t_{k-1},\quad ({\text{漸 }}{\text{ 化 }}{\text{ 式 }}\;)\\[1ex]\;\;t_{k-1}=1,2,\ldots ,n-r+k-b_{k-1},\quad ({\text{漸 }}{\text{ 化 }}{\text{ 式 }}\;)\\[1ex]\;\;k=1,2,\ldots ,r,\quad ({\text{漸 }}{\text{ 化 }}{\text{ 式 }}\;)\\[1ex]\;\;\qquad b_{0}=0\quad ({\text{定 }}{\text{ 義 }}\;)\end{cases}}

で算出した結果の組合せが偽である n と r の組みを示せ。【命題(1)おわり】

つまり、n と r を任意に与えて、上記の漸化式で算出した結果が、正しい組合せとはならない n と r を、同時に示せれば、それが反例となる。

漸化式の証明

漸化式を用いて算出する計算の結果が正しいことを証明しようと試みてはいるが、証明は未だ得られていない。（2019/07/01）

下に載せた画像は、算出に用いた漸化式と、正しく算出された n と r の表を示している。

TN-漸化式

これまで示してきた漸化式を用いて算出した組合せは、全ての n と r に関して、常に正しいことを証明せよ。

脚注

↑ 長島隆廣［繰り返しを許さない組合せの各組を全て算出できる数式］researchmap, 2018年12月. 論文PDF：https://researchmap.jp/T_Nagashima/
↑ 岩波數學辭典(岩波書店，1954) 日本數學會
↑ 岩波数学辞典第2版(岩波書店，1968) 日本数学会
↑ 岩波数学辞典第3版(岩波書店，1985) 日本数学会
↑ 岩波数学辞典第4版(CD-ROM付),(岩波書店，2007) 日本数学会
↑ 一松信，他：新数学事典(大阪書籍株式会社, 1979)
↑ 青本和彦，他：岩波数学入門辞典(岩波書店, 2005)
↑ G.ポリア, R.E.タージャン, D.R.ウッズ：組合せ論入門(近代科学社, 2015)
↑ ラスロウ・ロバース, 他：入門組合せ論(共立出版株式会社，1987)
↑ 樹下眞一：組合せ論入門(共立出版株式会社，1993)

[combi-resmap-2018-1] 長島隆廣［繰り返しを許さない組合せの各組を全て算出できる数式］researchmap, 2018年12月. 論文PDF：https://researchmap.jp/T_Nagashima/

[iwasugakujiten-1954-2] 岩波數學辭典(岩波書店，1954) 日本數學會

[iwasugakujiten-1968-3] 岩波数学辞典第2版(岩波書店，1968) 日本数学会

[iwasugakujiten-1985-4] 岩波数学辞典第3版(岩波書店，1985) 日本数学会

[iwasugakujiten-2007-5] 岩波数学辞典第4版(CD-ROM付),(岩波書店，2007) 日本数学会

[shinsugakujiten-1979-6] 一松信，他：新数学事典(大阪書籍株式会社, 1979)

[iwanyumonjiten-2005-7] 青本和彦，他：岩波数学入門辞典(岩波書店, 2005)

[gporia-2015-8] G.ポリア, R.E.タージャン, D.R.ウッズ：組合せ論入門(近代科学社, 2015)

[rasurou-1987-9] ラスロウ・ロバース, 他：入門組合せ論(共立出版株式会社，1987)

[kinoshita-1993-10] 樹下眞一：組合せ論入門(共立出版株式会社，1993)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

利用者:Knotopologynn/Research

目次