組合せ、重複組み合わせ（N:ラベルなし k:ラベルあり）　

重複順列、順列は区別がある学生を、区別がある部屋に割り振る例で考えました。これに対して組み合わせは、区別のないボールを、色の区別のある箱に入れるという例を使い考えます。写像にするとラベルがない集合Nにラベルがある集合Kを対応させるという想定です。

Nにラベルを付けない単射としての組み合わせ

組合せの考え方

ラベルが付いていないといってもイメージがつかないので、問題を考えながら理解していきます。

問題1

(1) 0から2まで番号が付いた3つのボールを、青、黄、赤、紫、緑の5つの箱に入れるときの順列の数を計算してください。なお、各箱にはボールは1つしか入らないものとします。

(2) 前問でボールに番号がなく区別がつかないとしたときの、組み合わせの数を計算してください。

図表1 で(1)と(2)の違いを写像により表しています。(1)は順列で、$\ _5 P_3 =60$通りになります。(2)もボールの区別がないことから、(1)では(0, 1, 2)が選ぶものとして(青、赤、緑)、(青、緑、赤)、(赤、青、緑)、(赤、緑、青)、(緑、赤、青)、(緑、青、赤)の6個の組み合わせを別のものとして数えるのに対し、(2)では1通りと計算します。

(2)の組み合わせの個数は、60個の順列を選ばれた３つの箱の順列3!=6で割った10通りになります。この組み合わせは$_k C_n$として表します。

数式2-1 組み合わせの個数の計算　k個からn個を選ぶ場合

$\displaystyle \ _k C_n =\frac{\ _k P_n}{n!}=\frac{k!}{n!(k-n)!} = \frac{\overbrace {k(k-1)(k-2)\cdots (k-n+1)}^{n個}}{\underbrace {n\times (n-1)\times \cdots 2 \times 1}_{n個}}$

組み合わせも順列と同じように、箱には球が1つしか入らないので単射となりますが、集合Nは区別なし（ラベルがついていないものunlabeled）と考えます。

組み合わせに関する関数

組み合わせの個数を計算するPythonの関数

組み合わせの個数を計算するために、Pythonの標準ライブラリには、mathモジュール、SciPyライブラリにcomb関数が用意されています。いずれの関数も集合Kの個数kと集合Nの個数nを引数として渡します。

mathモジュール、SciPyライブラリのcomb関数を使い組み合わせの個数を計算する

import math
from scipy.special import comb
k_list = ['青', '赤', '緑', '黄', '紫']
n = 3
print(f'mathモジュールのcomb関数：{math.comb(len(k_list), n)}')
print(f'SciPy.specialパッケージのcomb関数：{comb(5, 3)}')

mathモジュールのcomb関数：10
SciPyライブラリのcomb関数：10.0

1.　mathモジュールは通常、モジュール全体をimportすることが多いようです。

2.　com関数はSciPyライブラリのscipy.specialモジュールからインポートします。

3.　mathモジュールのcomb関数は整数で組み合わせの個数をも戻り値として返します。ただし、Pythonの v3.8以降でないと使うことはできません。

4.　scipy.specialパッケージのcomb関数は浮動小数点で返すところがmathモジュールと異なります。

順列、組み合わせを計算する関数を作成する

順列、組み合わせの個数を計算する関数を作成しますが、これらの計算では階乗の計算が必要になります。そこで、階乗を計算するfactorial関数を作成し、factorial関数を使って順列を計算するP関数、組み合わせを計算するC関数を作成します。これらの関数はよく使われるので、英字1文字にします。

①階乗：factorial 関数

引数を正の整数nとして、nから1までを掛け合わせます。ただし$ _ 5 P_3$のような計算をする場合には途中で止めても構いません。そこで、2つ目のrという引数を追加し、デフォルトをNoneとしておきます。階乗は0!=1となることが必要です。

②順列：P関数

引数として集合Kの個数kと集合Nの個数nを指定します。つまりk個から選んで並べる順列の個数を計算します。P関数はk

③：C関数

P関数の組み合わせ版です。C関数はk

階乗、順列、組合せを計算する関数

def factorial(n, r=None):
if r is None:
r = n
result = 1
for i in range(n, n-r, -1):
result *= i
return result
def P(k, n):
if k < n:
return 0
return factorial(k, n)
def C(k, n):
if k < n:
return 0
return factorial(k, n) // factorial(n)
print(f'0!={factorial(0)} 1!={factorial(1)} 5!={factorial(5)} 5X4X3={factorial(5,3)}')
print(f'5P5={P(5,5)} 5P3={P(5,3)} 5P1={P(5,1)} 5P0={P(5,0)} 5P6={P(5,6)}')
print(f'5C5={C(5,5)} 5C3={C(5,3)} 5C1={C(5,1)} 5C0={C(5,0)} 5C6={C(5,6)}')

0!=1  1!=1  5!=120  5X4X3=60
5P5=120  5P3=60  5P1=5  5P0=1  5P6=0
5C5=1  5C3=10  5C1=5  5C0=1  5C6=0

1.　2番目の仮引数r=Noneと指定することでrを指定しない場合は初期値でNone、指定した場合はその値がrに代入されます。

2.　1.を受けてrがNoneであれば3.でnをrに代入されます。このことにより、n!の計算ができるようになります。

5.　階乗の計算式は$n\times(n-1)\times(n-2)\times\cdots(n-r+1)です。この計算を実現するためfor i in range(n, n -r, -1)とします。3つ目の引数が-1の場合、降順にiを回しますが2番目の引数は1つ先まで指定するので、n-rとするとn-r+1で止まります。

9.　順列は基本的にはfactorial関数を適用しますがk < nの場合は0になるように明記します。

k,n,rが正の整数であれば、階乗、順列、組合せの計算が正しくできることがわかりました。

組み合わせを生成する関数

itertoolsモジュールのcombinations関数により、組み合わせの一覧を生成することができます。引数として集合Kのリストk_listと集合Nの個数nを渡します。

itertoolsモジュールを使い組み合わせの一覧を生成

import itertools
k_list = ['青', '赤', '緑', '黄', '紫']
n = 3
comb_injective_list = list(itertools.combinations(k_list, n))
print('injective=',len(comb_injective_list))
pprint.pprint(comb_injective_list)

injective= 10
[('青', '赤', '緑'),
 ('青', '赤', '黄'),
 ('青', '赤', '紫'),
 ('青', '緑', '黄'),
 ('青', '緑', '紫'),
 ('青', '黄', '紫'),
 ('赤', '緑', '黄'),
 ('赤', '緑', '紫'),
 ('赤', '黄', '紫'),
 ('緑', '黄', '紫')]

1.　itertoolsモジュールはPythonの標準ライブラリですが、ビルドイン関数ではないので、使用する都度、インポートする必要があります。

itertoolsはFunction Programming Moduleに分類されます。

3.　重複順列はitertoolsモジュールのcombinations関数を使い出力することができます。なお、combinations関数はイテレータという特殊な形式となるので、戻り値をリストとして扱うときにはlist関数を使い変換する必要があります。

4.　出力すると、リストの中に重複順列の各パターンがタプルにまとめられます。件数は10件になります。

6.　生成した重複順列は、pprint関数で出力したほうが見やすくなります。

組み合わせを生成する関数を作成する

Nに区別がある順列の生成

組み合わせと順列の関係を見るために、前に作成したperm_injective_funcを使い、リストperm_injective_listに順列を生成し、ここから組み合わせの配列に集約します。

順列を生成する関数

def perm_injective_func(k_list, n):
array = [()]
for cnt in range(n):
temp = array
array = []
for elm in temp:
for item in k_list:
if item not in elm:
array.append(elm + (item,))
return array
k_list = ['青', '赤', '緑', '黄', '紫']
n = 3
perm_injective_list = perm_injective_func(k_list, n)
print('reputation=',len(perm_injective_list))
pprint.pprint(perm_injective_list)

reputation= 60
[('青', '赤', '緑'),
 ('青', '赤', '黄'),
 ('青', '赤', '紫'),
 ('青', '緑', '赤'),
 ('青', '緑', '黄'),
 ('青', '緑', '紫'),
 ('青', '黄', '赤'),
 ('青', '黄', '緑'),
 ('青', '黄', '紫'),
 ('青', '紫', '赤'),

順列は60件になります。

次に、順列の中から1つ、代表を絞り込みます。

増加関数としての組み合わせと一覧の生成

組み合わせの一覧を生成するためには、青、赤、緑の3色の順列の6つの中からルールを決めて1つ代表を選ぶ必要があります。最もわかりやすいルールは、図表2のように全ての色に色番号を振り、ボールの順番を$x_0,x_1,x_2 \cdots x_n$というように振る方法です。ボールには区別が無いと言っておきながら違和感を覚えますが、出席番号のような区別ではなく、たまたま選んだ順番という意味として捉えるとわかりやすいと思います。

もし、1番初めに取り出したボール$X_0$が色番号0の青を選んだら、次の$X_1$のボールは0:青の次の1:黄色かそれより大きな色番号から選ぶようにします。もし2:赤を選んだら、$X_2$は3：紫かそれよりも大きな色番号から選びます。この結果、ボールの順番が後になるほど色番号が大きくなる（昇順）ように箱を選ぶこととします。

この考え方によると、#3のように0:青、2:赤、4:緑を選ぶとすると、2:赤、4:緑、0:青のような別の順番の順列は選ばれず、結果として組み合わせを生成することになります。このような考え方を、増加写像(increasing_map)といいます。少しまどろっこしい表現ですが、組み合わせのプログラムを作成するうえで非常に役立ちます。

この関係を数式にするとコンピュータの世界では添え字は0から始まるので図表のようになりますが、一般的には添え字は1から始まるので、それに倣うと次のように表現します。

$1 \leqq x_1\lt x_2\lt x_3 \leqq 5$

プログラムを作成する際には、カウンタや配列の添え字は0から始まるので、前者の方法が適しています。一方、組み合わせの式$_k C_n$との対応を考える場合は1から始まる方法のほうが適しています。そこで、今後は2つを併記する形でご紹介します。

そこで関係を一般化すると、つぎのようになります。

数式2-2増加写像を使った組み合わせの表現

プログラミングでの方法

$0\leqq x_0\lt x_1\lt\cdots\lt x_{n-1}\leqq k-1$

一般的な考え方

$1 \leqq x_1\lt x_2\lt \cdots \lt x_n \leqq k \Longleftrightarrow _k C_n$

増加関数の考え方を使い順列から組み合わせに変換する

増加写像の考え方を使い組み合わせの一覧を生成する関数を作成します。#4のperm_injective_func関数で作成した順列perm_injective_listから、増加写像の要件を満たす配列のみを抽出する関数を作成し、組み合わせを生成します。関数名は増加写像の意味を込めてincreasing_map_funcとし、引数は順列の配列とします。

順列の配列をelmとして順次読み込み、elmの中の要素よりもその1つ右側の要素の方が大きいことが分かった時点で、そのelmは増加写像の要件を満たさなくなるのでbreakし、次の要素を読み込みます。最後までbreakされなかったelmは、組み合わせとしてリストarrayに追加します。

順列のリストから組み合わせに絞り込む関数

def increasing_map_func(perm_list):
array=[]
for elm in perm_list:
for i in range(len(elm) - 1):
if elm[i] >= elm[i + 1]:
break
else:
array.append(elm)
return array
comb_injective_list = increasing_map_func(perm_injective_list)
print('injective=',len(comb_injective_list))
pprint.pprint(comb_injective_list)

injective= 10
[('赤', '青', '黄'),
 ('緑', '青', '黄'),
 ('緑', '赤', '青'),
 ('緑', '赤', '黄'),
 ('紫', '青', '黄'),
 ('紫', '赤', '青'),
 ('紫', '赤', '黄'),
 ('紫', '緑', '青'),
 ('紫', '緑', '赤'),
 ('紫', '緑', '黄')]

5.　elmのi番目がi+1番目より小さい場合には、増加写像にならないのでbreakします。このため3.ではiは0からelmの長さ-1までループさせます。

7.　4.のループで最後まで増加写像の要件を満たしている順列はelse節にarrayに追加します。

計算の結果10件に絞られました。

組み合わせを生成する関数

(3)では順列のリストから絞り込む方法で組み合わせを生成しましたが、順列の個数はnが大きくなると爆発的に増えてしまいマシンに負荷がかかります。このため、重複順列を生成するperm_unristricted_func関数に増加写像の処理を組み込むことで組み合わせを生成する関数を作成します。

組み合わせの単射なので関数名はcomb_injective_func関数とし、これまでと同じように、引数は箱の色のリストk_listとボールの個数nとします。重複順列では1つ目に2:赤を選んでも2つ目は0:青から順次選ぶ必要がありました。一方、組み合わせは増加関数であることから、2つ目は3:紫のから選べばよいことになります。そこで、この3:紫に当たる番号を変数startでコントロールします。

組合せを生成する関数

def comb_injective_func(k_list, n):
array = [()]
for _ in range(n):
temp = array
array = []
for elm in temp:
if elm == ():
start = 0
else:
start = k_list.index(elm[-1]) + 1
for item in range(start, len(k_list)):
array.append(elm+(k_list[item],))
return array
k_list = ['青', '赤', '緑', '黄', '紫']
n = 3
comb_injective_list = comb_injective_func(k_list, n )
print('injective=',len(comb_injective_list))
pprint.pprint(comb_injective_list)

injective= 10
[('青', '赤', '緑'),
 ('青', '赤', '黄'),
 ('青', '赤', '紫'),
 ('青', '緑', '黄'),
 ('青', '緑', '紫'),
 ('青', '黄', '紫'),
 ('赤', '緑', '黄'),
 ('赤', '緑', '紫'),
 ('赤', '黄', '紫'),
 ('緑', '黄', '紫')]

3.　選ぶ色の数nが埋まるまでループさせます。

8.　初めのボールは0:青からが候補になるのでstartを0に設定します。2つ目以降のボールを入れる箱を選ぶときは、前に選んだ色番号の次からが候補になりあます。

10. k_list.index(elm[-1])は最後に選んだ色番号が代入されているので、この番号+1をstartに代入します。

11. startからk_list最後の要素まで色番号を順次選び、タプルとして追加した新しい要素をarrayに追加します。

12. 全ての繰り返しが終わった後、最終的に生成された組み合わせを戻り値として返します。

インデックスの考え方が少し面倒ですが、重複順列のプログラムを少し修正するだけで組み合わせを生成する関数を作成することができました。

制約なしの重複組み合わせ

組み合わせは集合Kから1つしか選ぶことができませんが、重複組み合わせは、重複して選ぶことができます。このため、組み合わせに比べ複雑になりますが、写像と増加関数の考え方を使うと簡単に整理することができます。

重複組み合わせの考え方

まずは、単射の組み合わせとの違いを見るため、次の問題を考えます。

問題2

区別の無い5つのボールを、青、赤、緑の色がついた3つの箱に入れるとするときの場合の数を計算してください。なお、各箱には重複してボールを入れることができ、空の箱があってもよいものとします。

写像にすると、左の図のようになり、集合Kの要素は空白も複数の要素から対応付けられるので、組み合わせの単射に対し制約なし(unrestricted)のパターンになります。

重複組み合わせを生成する関数

Pythonで組み合わせの一覧を求めるためにはitertoolモジュールのcombinations_with_replacement関数を使います。引数は集合Kのリストと、集合Nの個数を渡し、重複組み合わせの一覧がジェネレータとして返ります。

itertoolsモジュールを使い重複組み合わせを生成する

k_list = ['青', '赤', '緑']
n = 5
comb_unrestrict_list = list(itertools.combinations_with_replacement(k_list, n))
print('unrestrict=',len(comb_unrestrict_list))
pprint.pprint(comb_unrestrict_list)

unrestrict= 21
[('青', '青', '青', '青', '青'),
 ('青', '青', '青', '青', '赤'),
　　　　・
　　　　・
('青', '青', '赤', '赤', '緑'),
 
 ('緑', '緑', '緑', '緑', '緑')]

1　重複組み合わせはitertoolsモジュールのcombinations_with_replacement関数で生成することができます。一部省略していますが、全部で21通りの組み合わせが考えられます。

写像による重複組み合わせ

「しきり」による重複組み合わせの計算

重複組み合わせを写像と、一般的に使われる分割の「しきり」とボールであらわす方法で考えます。この方法を使い、重複組み合わせのいくつかのパターンで整理します。

①典型的な重複組み合わせ

図の右側のように、5個の区別の無いボールを並べ、その間に青と赤を分ける「しきり」と赤と緑を分ける「しきり」を入れます。このケースは青2個、赤2個、緑1個とまっとうな組み合わせになります。

②端ではない色が選ばれない場合

制約なしの場合、青3つ緑2つが選ばれ、真ん中の赤が選ばれないようなケースも認められます。この場合、青と赤を分ける「しきり」と、赤と緑を分ける「しきり」が青と緑の間に並びます。

③端の色が選ばれない場合

右端の色は緑になりますが、この場合図表6のように一番右側に赤と青の「しきり」が入ります。

3つのケースを見ると、「しきり」2つとボール5つを7つのマスに並べる際の組み合わせを計算することで重複組み合わせの個数を求めることができます。

一般化すると、ボールの数nと「しきり」の数(k-1)を足したn+k-1個の中からボールn個を選ぶことになります。また「しきり」の方に注目すれば、仕切りk-1個を選ぶことと同じ意味になります。

このような区別なないn個のボールをk色の箱に重複を許して選ぶ重複組み合わせの個数を$\ _k H_n$で表し、計算式は次のようになります。

$\ _k H_n = \ _{n+k-1} C_n=\ _{n+k-1} C_{k-1}$

増加写像としての重複組み合わせ

増加写像の考え方

重複組み合わせを増加組み合わせの数式で表すと、組合せとは異なり前と同じ色を選んでもよいので、図の①のように$0\leqq x_0\leqq x_1 \leqq x_2\leqq x_3\leqq x_4\leqq 2$となります。ところで$x_i$は整数なので$x_i\leqq x_{i+1}\leftrightarrows x_i\lt x_{i+1}+1$となり、$\leftrightarrows 0\leqq x_0\lt x_1+1\lt x_2+2\lt x_3+3\lt x_4+4 \leqq2+4=6$と書き換えることができます。ここで、$y_i=x_i+i$を代入すると$\leftrightarrows 0\leqq y_0\lt y_1\lt y_2\lt y_3\lt y_4\leqq 6$となり図の下のようになります。

①の$x_4$の最大値は2なので、$y_4$の最大値は6となるところに注意してください。次に1始まりの方法を考えます。

$1 \leqq x_1\leqq x_2\leqq x_3\leqq x_4\leqq x_5\leqq 3$

$\leftrightarrows 1\leqq x_1\lt x_2+1\lt x_3+2\lt x_4+3\lt x_5+4\leqq 3+4=7$となります。$y_i=x_i+i-1$を代入すると$1\leqq y_1\lt y_2\lt y_3\lt y_4\lt y_5\leqq =7$となり、$\ _7 C_5$となります。

結果的に①の全ての組み合わせを集合1、②の全ての組み合わせを集合２とすると、集合１から集合２の各項に0,1,2,3,4を足した写像であり、逆に集合2は集合2から集合Ⅰへの対応は各項から0,1,2,3,4を引いた写像となり、2つの集合は逆写像がとなるので全単射となり個数が等しくなります。

ただし、コンピュータの世界では添え字は0から始まりますが、一般的には1から始まるので、それに倣うと次のように表現します。

$1\leqq y_1\lt y_2\lt y_3\lt y_4\lt y_5\leqq 3+4=7$

この関係を一般化すると、つぎのようになります。

数式2-3重複組み合わせの式

0はじまり

$0 \leqq x_0\leqq x_1\leqq \cdots \leqq x_{n-1} \leqq k-1$

$\leftrightarrows 0 \leqq x_0 \lt x_1+1 \lt x_2 +2 \cdots \lt x_{n-1}+n-1 \leqq n+k-2$

$\because x_i\leqq x_{i+1} \leftrightarrow x_i\lt x_{i+1}+1$

$\leftrightarrows 0\leqq y_0\lt y_1\lt y_2 \cdots y_{n-1}\leqq n+k-2$

１はじまり

$1 \leqq x_1\leqq x_2\leqq \cdots \leqq x_n \leqq k$

$\leftrightarrows 1 \leqq x_1 \lt x_2+1 \lt x_3 +2 \cdots \lt x_n+n-1 \leqq n+k-1$

$\because x_i\leqq x_{i+1} \leftrightarrow x_i\lt x_{i+1}+1$

$\leftrightarrows 1\leqq y_1\lt y_2\lt y_3 \cdots y_n\leqq n+k-1$

$\ _k H_n = \ _{n+k-1} C_n=\ _{n+k-1} C_{k-1}$

写像の考え方によると、重複組み合わせのような対応を広義の増加写像といい、組み合わせを狭義の増加写像といいます。組み合わせは単射の対応であったように、狭義の増加写像であることと単射は同じことをいいます。

重複組み合わせの一覧を生成

重複組み合わせをイメージするのには少し努力が必要ですが、その一覧を生成するプログラムは組み合わせの生成のプログラムを広義の単調増加関数にするため、1つだけ変更を加えるだけです。

制約なしの写像としての重複組み合わせを生成する

def comb_unristrict_func(k_list, n):
array = [()]
for cnt in range(n):
temp = array
array = []
for elm in temp:
if elm == ():
start = 0
else:
start = k_list.index(elm[-1]) # +
for item in range(start, len(k_list)):
array.append(elm + (k_list[item],))
return array
k_list = ['青', '赤', '緑']
n = 5
comb_unristrict_list = comb_unristrict_func(k_list, n )
print('injective=', len(comb_unristrict_list), 'H関数', H(len(k_list), n))
pprint.pprint(comb_unristrict_list )

injective= 21 H関数 21.0
[('青', '青', '青', '青', '青'),
 ('青', '青', '青', '青', '赤'),
 ('青', '青', '青', '青', '緑'),
 ('青', '青', '青', '赤', '赤'),
 ('青', '青', '青', '赤', '緑'),
 ('青', '青', '青', '緑', '緑'),
 ('青', '青', '赤', '赤', '赤'),
 ('青', '青', '赤', '赤', '緑'),
 ('青', '青', '赤', '緑', '緑'),
 ('青', '青', '緑', '緑', '緑'),
 ('青', '赤', '赤', '赤', '赤'),
 ('青', '赤', '赤', '赤', '緑'),
 ('青', '赤', '赤', '緑', '緑'),
 ('青', '赤', '緑', '緑', '緑'),
 ('青', '緑', '緑', '緑', '緑'),
 ('赤', '赤', '赤', '赤', '赤'),
 ('赤', '赤', '赤', '赤', '緑'),
 ('赤', '赤', '赤', '緑', '緑'),
 ('赤', '赤', '緑', '緑', '緑'),
 ('赤', '緑', '緑', '緑', '緑'),
 ('緑', '緑', '緑', '緑', '緑')]

10.　1つの箱が選択されたのち、次の箱を選ぶときには前と同じものを選ぶことも許されます。このため、startを選ぶときにstart = k_list.index(elm[-1])として組み合わせの時の#+1を削除するだけの変更になります。

増加写像の考え方は、プログラムを作成するうえではすごい威力を発揮することがわかります。

全射の重複組み合わせ

全射（空きがない）の重複組み合わせ

重複組み合わせは、制約なしという条件で、空になる箱を許していましたが、今度は空になる箱を許さない全射について考えます。

制約なしと全射の重複組み合わせを比較するため、次の問題を考えます。

問題3

区別の無い5つのボールを、青、赤、緑の色がついた3つの箱に入れるとするときの場合の数を計算してください。なお、各箱には重複してボールを入れることができ、空の箱が出ることは許されないものとします。

重複組み合わせにはitertoolsモジュールのcombinations_with_replacement関数が用意されているのに対し、全射の重複組み合わせを生成する関数は見当たらないので、独自に作成します。

全射の重複組み合わせの考え方

前項のなかで制約なしの重複組み合わせを3つのパターンで整理しました。このうち全射となると①「典型的な重複組み合わせ」（図表4）のみが対象となり、②「一部の色が選ばれない」（図表5）　のように「しきり」が隣り合ったり、③「端の色が選ばれない場合」（図表6）のように「しきり」が両端に来たりするものは許されません。

そこで、ボールと「しきり」混ぜた中からボールまたは「しきり」を選ぶのではなく、図表8のように、n=7、k=3の場合、6か所のうち2か所に「しきり」を入れる組み合わせを計算することにより、全射の重複組み合わせの個数を求めることができます。もちろん、6か所のうち「しきり」が入らない４か所を選ぶ組み合わせと考えることもできます。

図の通り$\ _6 C_2=\ _6 C_4=15$通りになります。一般化するとn-1個のすき間からk-1個を選んでしきりを入れるので$\ _{n-1} C_{k-1}$となります。その結果、全射の重複組み合わせの個数は$\ _{n-1} C_{k-1}=\ _{n-1} C_{n-k}$の式で計算することができます。

それでは次節で、計算式が正しいことを確認します。

全射の重複組み合わせの生成

comb_unristrict_func関数を使い、重複組み合わせを生成したのち、全射の条件を満たす組み合わせのみを選び出し個数を数えます。

制約なしの重複組み合わせから全射の組み合わせを絞り込む

k_list = ['青', '赤', '緑']
n = 7
comb_unrestrict_list =　comb_unristrict_func(k_list, n)
print('unrestrict=',len(comb_unrestrict_list))
comb_surjective_list=[]
for elm in comb_unrestrict_list:
if set(k_list).issubset(set(elm)) :
comb_surjective_list.append(elm)
len(comb_surjective_list), comb(n-1,len(k_list) - 1)

unrestrict= 36
(15, 15.0)

3.　生成した重複組み合わせを、配列comb_unrestrict_listに格納します。

6.　comb_unrestrict_listの1つ1つの組み合わせをelmで取り出し、集合にしてから要素数を計算し、k_listの個数と等しければ全射であると判断することができます。

8.　全射のものをcomb_surjective_listに格納します。7.　組み合わせが全射であるかはset(k_list).issubset(set(elm)) により判断します。k_listとelmをset関数により集合に変換し、issubsekメソッドでk_listが部分集合であるかを判断します。

n=7、k=3の場合、制約なしの重複組み合わせは36通りに対し、全射にすると15通りに絞られることになり、$\ _6 C_2=\ _6 C_4=15$通りと一致することを確認することができました。

全射の組み合わせを生成する際のテクニック

あらかじめ各色を確保する方法

全射の重複組み合わせを計算、図表のように生成する場合、図表9のようにはじめにk個の色にボールを1つずつ選んで全射である状態を確保した上で、残りボールを制約なしで重複組み合わせを計算するテクニックがあります。

制約なしなのである色が選ばれなくてもよかったのですが、全射の場合は少なくとも1つは選ぶ必要があります。そこで、とりあえずk個の色の箱にボール1つずつ計k個を入れることにより全射の条件を満たし、あとは残ったn-k個のボールは制約なしのときと同じようにボールを箱に割り振ればよいことになります。

3個のボールに対して青、赤、緑の色をそれぞれ対応させ、全射の状態であることを確保します。

残り4個のボールについて、制約なしで重複組み合わせを生成します。図表では赤が選ばれていませんが、①ですでに1つ確保されているので問題ありません。

②の個数は$\ _4 H_3 =\ _6 C_4=15$となり、全射の重複組み合わせの個数と一致します。

全射の重複組み合わせを生成する場合は、②の組み合わせに①で確保した青、赤、緑を1つ追加します。

一般化すると、全射の重複組み合わせの個数は$\ _k H_{n-k} =\ _{n-1} C_{n-k}$となり、前項の結果と一致します。

さっそく、全射の重複組み合わせを生成するプログラムを作成します。はじめにk個の全射を確保するためn-k個で制約なしの重複組み合わせを生成し、最後に各色を1個ずつ追加します。

k_listを確保して後から追加する方法で全射の重複組み合わせを生成

def comb_surjective_by_unristrict_func(k_list, n):
array = []
for elm in comb_unristrict_func(k_list, n - len(k_list)):
new_elm = [k_list[0]]
i = 0
for item in elm:
if item != new_elm[-1]:
new_elm.append(k_list[i := i + 1])
new_elm.append(item)
new_elm.extend(k_list[i+1:])
array.append(new_elm)
return array
k_list = ['青', '赤', '緑']
n = 7
comb_surjective_list = comb_surjective_by_unristrict_func(k_list,n)
print('surjective=', len(comb_surjective_list), 'H関数', H(len(k_list), n - len(k_list)))
pprint.pprint(comb_surjective_list )

計算結果は同様

3.　制約なしの重複組み合わせを生成する関数で生成した組み合わせを1つずつelmとして取り出します。

4.　new_elmに全射の重複組み合わせを作成します。全射であることから、1番目の要素は青(k_list[0])になるので、強制的に初期化します。

6.　読み込んだ要素をnew_elmに追加していきますが、前の色と変わったときは、初めに確保しておいた色を追加します。

11. elmに２番目以降の色が含まれていないと、その色が欠けてしまうので、追加します。

増加関数の考え方を使う方法

全射の重複組み合わせを増加関数の数式であらわすのは簡単ではありませんが、

$a \lesssim b$ を「$b$ は $a$ に等しいか、$a$ より1だけ大きい」$a \leqq b \leqq a+1$というような記号を独自に定義すれば何とか表現することができます。

$0 = x_0\lesssim x_1\lesssim \cdots \lesssim x_{n-1} = k-1$

ここでは次の３点がポイントになります。

$x_0$は必ず0番目の要素になるので0になります。

$x_1$以降は前の要素と同じが1つ大きいという\lesssim b$で表します。

最後の要素はk_listの最後の要素（k-1番目）と等しくなります。

増加関数を使ったプログラムを実現するために、次の工夫をします。

作成する組み合わせのはじめの要素に$k_0$の色（青）をはじめから入れておきます。

$\lesssim$記号（等しいか1つ大きい）を実現するため、1つ前の要素を読み込み、次の要素は前と同じ色からその次の色までを選ぶようにします。

最後の要素$x_{n-1}$はk_listの最後の色とするため、現在作成している要素の場所をn_index、現在選択した色が何番目かlk_indexを把握し、残りいくつかn-n_indexと残りの色が何色あるかk_k_indexを比べることにより、ここからどう頑張っても全射にならない組み合わせのものは候補から外すようにします。

増加関数の考え方を使い全射の重複組み合わせを生成する

def comb_surjective_func(n, k_list):
array = [(k_list[0],)]
for n_index in range(n - 1):
temp = array
array = []
for elm in temp:
if elm == ():
start = 0
else:
start = k_list.index(elm[-1])
for k_index in range(start, min(start + 2, len(k_list))):
if n-n_index > len(k_list) - k_index:
array.append(elm + (k_list[k_index],))
return array
k_list = ['青', '赤', '緑']
n = 7
comb_list = comb_surjective_func(n, k_list )
print('surjective=', len(comb_list), 'H関数', H(len(k_list), n-len(k_list)))
pprint.pprint(comb_list )

前のプログラムと同じ

11.　選ぶ色はstartからstart+1（プログラム上は+2）までとします。最後の（n-1）番目の要素を選ぶときはstart+1にするとリストの数を超えてエラーになるのでmin関数でk_listの大きさで止めるようにします。

12. 　上記③の条件を満たすため場合のみarrayに候補として追加します。

正しく計算することができました。制約なしの候補を作ってから全射の条件で絞り込むより、作成段階で条件に合わないものを切り捨てていく方が効率が良くなることが期待されます。

数式2-4全射の重複組み合わせを表す増加写像

$1 \leqq x_1 \leqq x_2 \leqq \cdots \leqq x_{n-k} \leqq k$

$ x_i\geqq 0\quad(i=1,2,\cdots,n)$

$\Leftrightarrow 1 \leqq x_1 < x_2+1 < x_3+2 < \cdots < x_{n-k}+n-k-1 \leqq k+n-k-1$

$\Leftrightarrow 1 \leqq y_1 < y_2< y_3 < \cdots < y_{n-k} \leqq n-1$

$\ _k H_{n-k} =\ _{n-1} C_{n-k}=\ _{n-1} C_{k-1}$

やはりこの場合も$\ _k H_{n-k} =\ _{n-1} C_{n-k}=\ _{n-1} C_{k-1}$と同じ式で表すことができます。

組み合わせの関数をまとめる

個数を計算する関数

意外なことに重複組み合わせの個数を計算する関数はPythonの標準ライブラリには見当たりません。あまりに単純なのが原因かもしれませんが、作っておくと便利です。関数名もシンプルにHとし、引数はkとnの個数とし、重複組み合わせを求める場合は、オプションで制約なしの場合は”u”、全射の場合は”s”を指定します。

重複組み合わせの個数を計算する関数

def H(k, n ,option='u'):
"""
n個の要素から重複を許してk個を取り出す重複組み合わせの個数を計算する関数。
Parameters:
-----------
k : int
kの要素数
n : int
nの要素数。
option : str, optional, default='i'
組み合わせの生成方法を指定するオプション。
'u' (unrestricted): kのうち1つも選ばれない要素があることを許す制約なしの重複組み合わせ
's' (surjective): kのうち1つは選ばれる必要がある全射の重複組み合わせ
Returns:
--------
int
重複組み合わせの個数
"""
if option == 'u':
return int(comb(n + k - 1, k - 1))
if option == 's':
return int(comb(n - 1, k - 1))
print(H(3, 5,'u'))
print(H(3, 5,'s'))

21
6

1.　 3番目の引数をoption='i'とすることで、組み合わせ（単射）をデフォルトとします。

2～20　複数行にわたるコメントを入れるときは’’’ ‘’’で囲います。行単位のコメントである

#とは異なり、通常のプログラムのコードを書くときと同じように、インデントを合わせる必要があります。ここでのコメントはdocstringといい、”? combinations_func”と入力すると表示されます。

組み合わせおよび重複組み合わせを生成する関数をまとめる

これまで単射、制約なし、全射の組み合わせを生成する関数を作成してきました。基本的な流れはほぼ同じで、それぞれ少しずつ修正を加えることで機能を実現することができました。そこで、これらの3つの関数をまとめたcombinations_func関数を作成します。

このため、3つ目の引数はoptionとし、次に通り設定します。

'i' (injective): 組み合わせ　default

'u' (unrestricted): 重複組み合わせ

's' (surjective):全射の重複組み合わせ

名にも指定しない場合（default）

なお、このように決めごとをしても、関数を使う人にはわからないし、この関数の中では誤ったoptionを指定した場合のエラー処理も含まれていないので、docstringを追加します。

組み合わせを生成する関数

def combinations_func( k_list, n, option='i'):
"""
与えられたリストk_listから、n個の要素の組み合わせを生成する関数。
Parameters:
-----------
k_list : list
組み合わせを生成するための要素のリスト。
n : int
生成する組み合わせの要素数。
option : str, optional, default='i'
組み合わせの生成方法を指定するオプション。
'i' (injective): 要素が増加する順序で組み合わせを生成する。
'u' (unrestricted): 要素の順序を考慮せずに組み合わせを生成する。
's' (surjective): 重複を許さず、要素数がn個の組み合わせのみを生成する。
Returns:
--------
list of tuples
生成された組み合わせのリスト。各組み合わせはタプルとして表現される。
"""
array = [()]
for cnt in range(n):
temp = array
array = []
for elm in temp:
if elm == ():
start = 0
else:
start = k_list.index(elm[-1]) + (1 if option == 'i' else 0)
for item in range(start, len(k_list) if option !='s' else min(start + 2, len(k_list))):
new_elm = elm + (k_list[item],)
if option != 's' or \
not(cnt == n - 1 and not set(k_list).issubset(set(new_elm))):
array.append(new_elm)
return array
k_list = ['青', '赤', '緑', '黄', '紫']
n=3
print(len(combinations_func( k_list, n, option='i')))
k_list = ['青', '赤', '緑']
n = 5
print(len(combinations_func( k_list, n, option='u')))
k_list = ['青', '赤', '緑']
n = 7
print(len(combinations_func( k_list, n, option='s')))

10
21
15

31. 増加写像を使って組み合わせを生成するので、１つの項目を選んだあと次の項目をk_listの何番目から追加するのかをstartに代入します。単射である純粋増加写像の場合は前のインデックス+1、それ以外は前のインデックスにするため0になります。1 if option == 'i' else 0は三項演算子といい、条件文を1行で書くことができます。

33.　組み合わせを1つ1つ作成するために、elmに選んだ色を追加しますが、全射の場合のみ一番最後(cnt==n-1)のときだけ、全射にならない組み合わせを(len(set(new_elm)) != len(k_list)))で判断してarrayに追加しないようにします。

combinations_func関数を使い、これまで例として扱ってきたケースについて組み合わせを計算すると、結果が正しいことがわかります。

３つの組み合わせのまとめ

combinations_func関数に集約したように、単射の組み合わせ、制約なしの重複組み合わせ、及び全射の重複組み合わせについてまとめると次のようになります。

数式2-5重複組み合わせの個数の計算

i:単射いわゆる組み合わせ

$\ _k C_n$

u:制限なしの重複組み合わせ

n個の区別のないボールをk種類の箱に重複を許して入れる場合の組み合わせ数

（0個の箱があってもOK）

$\ _k H_n = \ _{n+k-1} C_n=\ _{n+k-1} C_{k-1}$

s:全射の重複組み合わせ

n個の区別のないボールをk種類の箱に重複を許して入れる場合の組み合わせ数

（空の箱は許さない）

$\ _k H_{n-k} =\ _{n-1} C_{n-k}=\ _{n-1} C_{k-1}$

不定方程式、不定不等式

重複組み合わせにはさまざまな応用範囲があります。ここでは、その1つである不定方程式のいろいろなケースについてみていきます。

制約なしの場合

不定方程式を写像であらわす

重複組み合わせの考え方を使うと、次のような整数の問題も簡単に解決することができます。

問題4

次の条件を満たす$x_1,x_2,x_3$の組み合わせの数を計算してください。

$x_1+x_2+x_3=10\quad(x_i\geqq0)$

変数が3つあり、式が1つだから答えは1つに決まりません。このように複数の解があるような式を不定方程式(indefinite equation)といいます。重複組み合わせと不定方程式は一見すると関係がないように思えますが、写像にしてみると同じ形をしています。

ここでは、$x_i$の組の一覧を作成し個数を解の数を計算します。$x_i\geqq0$という条件なので、全射でも単射でもない制約なし(unristricted)のタイプになります。この関係も写像であらわします。

写像を見ると、この問題は区別のない10個ボールを3つの箱に空箱も許して分ける重複組み合わせと同じ枠組みであることがわかります。また、$x_i\geqq0$なので$ x_2=0$となる右側のものも許されます。

不定方程式のもととなる重複組組み合わせを作成する

そこで、まず$K={X_1, X_2, X_3}$、n=10として重複組み合わせを生成し、その個数を計算します。

不定方程式を重複組み合わせで解く

k_list = ['x1', 'x2', 'x3']
n = 10
k=len(k_list)
comb_unristrict_list = comb_unristrict_func(k_list, n )
print('unristricted=', len(comb_unristrict_list))
print('H関数', H(k,n),': comb関数',comb(n + k - 1, n))
pprint.pprint(comb_unristrict_list)

 unristricted= 66
H関数 66.0 : comb関数 66.0
[('x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1'),
 ('x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x2'),
 ('x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x3'),
 ('x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x2', 'x2'),
 ('x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x2', 'x3'),
 ('x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x3', 'x3'),
 ('x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x2', 'x2', 'x2'),
 ('x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x2', 'x2', 'x3'),
 ('x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x2', 'x3', 'x3'),
 ('x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x3', 'x3', 'x3'),
 ('x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x2', 'x2', 'x2', 'x2'),
 ('x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x2', 'x2', 'x2', 'x3'),
 ('x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x2', 'x2', 'x3', 'x3'),
 ('x1', 'x1', 'x1', 'x1', 'x1', 'x1', 'x2', 'x3', 'x3', 'x3'),
・
・
('x3', 'x3', 'x3', 'x3', 'x3', 'x3', 'x3', 'x3', 'x3', 'x3')]

3.　comb_unristrict_func関数を使い、その返り値を配列comb_unristrict_listに代入します。

5.　comb_unristrict_listの個数を計算します。

7.　k=3,n=10の重複組み合わせの数をH関数で計算するとともに、comb関数で$\ _{n+k-1} C_{k-1}$を計算します。両者が一致することが確認できます。

X1からX3までの組み合わせを生成することができました。件数を求めることができたので、次にその一覧を生成します。

重複組み合わせで不定方程式を解く

一覧表は、indefinite_listに作成します。#11で作成したcomb_unristrict_listの組み合わせを、1つずつelmに読み込んで集計します。

重複組み合わせから不定方程式を解く

indefinite_list = []
for elm in comb_unristrict_list:
cnt = [0] * len(k_list)
for item in elm:
cnt[k_list.index(item)] += 1
indefinite_list.append(cnt)
indefinite_list

[[10, 0, 0],
 [9, 1, 0],
 [9, 0, 1],
 [8, 2, 0],
 [8, 1, 1],
 [8, 0, 2],
 [7, 3, 0],
 [7, 2, 1],
 [7, 1, 2],
 ・
・
 
[0, 3, 7],
 [0, 2, 8],
 [0, 1, 9],
 [0, 0, 10]]

2.　#13で作成した重複組み合わせを1件ずつ読み込みます。

3.　$x_0$から$x_{k-1}$までのk_listの要素ごとの個数を計算するための配列cntを定義します。

5.　配列cntを使い$x_0,x_1,x_2$数の数をカウントします。

6.　1つの組み合わせについてカウントが終了したら配列を1つの解としてindefinite_listに追加します。

不定方程式を解く関数を作成する

これまでのように一つ一つの重複組み合わせを集計するのではなく、直接解を求める関数を作成します。関数名は制約なしの不定方程式という意味でequation_unristricted_funcとします。引数として変数の個数をk、式の合計をnとして方程式の解を生成します。

重複組み合わせから制約なしの不定方程式を解く

def equation_unristricted_func(k, n):
array = [()]
for kth in range(k):
temp = array
array = []
for elm in temp:
if kth < k-1:
for nth in range(n + 1):
if sum(new_elm := elm + (nth,)) <= n:
array.append(new_elm)
else:
break
else:
array.append(elm + (n-sum(elm),))
return array
n = 10
k = 3
equation_unristricted_list = equation_unristricted_func(k, n)
print('unristricted=', len(equation_unristricted_list))
print('H関数', H(k,n),': comb関数',comb(n + k - 1, n))
pprint.pprint(equation_unristricted_list)

unristricted= 66
H関数 66.0 : comb関数 66.0
[(0, 0, 10),
 (0, 1, 9),
 (0, 2, 8),
 (0, 3, 7),
 (0, 4, 6),
 (0, 5, 5),
 (0, 6, 4),
 ・
・
 
 (8, 2, 0),
 (9, 0, 1),
 (9, 1, 0),
 (10, 0, 0)]

7～8 重複順列と同じように変数$x_1,x_2$の順に0から9までの整数を順次タプルに追加し、作成途中の組み合わせを作成します。

9～10 作成途中の組み合わせで合計がn=10を超えて解になりえないものは除いて、最終的に解となる可能性のあるもののみarrayに追加します。

15～17$x_3$（最後の要素）は、作成途中の組み合わせの合計とn=10の差を追加して解を完成します。

組み合わせは66通りになり、$\ _ 3H_{10}=\ _{12} C_{10}=66$から計算した結果と一致します。まとめると次の式で計算することができます。

数式2-6制約なしの不定方程式の解の個数

$\sum\limits_{i=1}^k x_i=x_1+x_2+\cdots+x_k=n\quad0\leqq x_i\leqq n\;(i=1,2,\cdots,k)$

$\ _k H_n = \ _{n+k-1} C_n=\ _{n+k-1} C_{k-1}$

全射の場合

前項では解に０が含まれてもより制約なしの条件で計算しましたが、今度は$x_i>=1$なので全射の条件で計算します。上記のプログラムとの変更点は次の2点だけです。

①$x_i$の候補として制約なしの場合は0からとしたものを、全射としたので最小値を1に変更します。また、最大値はn-k+1となります。

②途中に候補としてarrayに追加する前のチェックとして、これまでの要素の合計がnと等しくなった時点で最後の要素が０になってしまうので全射の条件を満たすことができません。このため≦を＜に変更します。なお、②の変更は必ずしも必要はありません。

問題5

次の条件を満たす$x_1,x_2,x_3$の組み合わせの数を計算してください。

$x_1+x_2+x_3=10\quad(x_i\geqq1)$

条件が増えて難しそうですが、少しのプログラムの変更で機能を実現することができます。プログラム名は全射の意味を込めてequation_surjective_funcとします。

重複組み合わせから全射の不定方程式を解く

def equation_surjective_func(k, n):
array = [()]
for kth in range(k):
temp = array
array = []
for elm in temp:
if kth < k - 1:
for nth in range(1, n - k + 2): # range(n+1)
if sum(new_elm:=elm + (nth,)) < n: #<=
array.append(new_elm)
else:
break
else:
array.append(elm + (n - sum(elm),))
return array
n = 10
k = 3
equation_surjective_list = equation_surjective_func(k, n)
print('surjective=', len(equation_surjective_list))
print('H関数', H(k, n - k),': comb関数', comb(n - 1, n - k),comb(n - 1, k - 1))
pprint.pprint(equation_surjective_list)

surjective= 36
H関数 36.0 : comb関数 36.0 36.0
[(1, 1, 8),
 (1, 2, 7),
 (1, 3, 6),
 (1, 4, 5),
 (1, 5, 4),
 (1, 6, 3),
 (1, 7, 2),
 ・
・
 (4, 4, 2),
 (4, 5, 1),
 (5, 1, 4),
 (5, 2, 3),
 (5, 3, 2),
 (5, 4, 1),
 (6, 1, 3),
 (6, 2, 2),
 (6, 3, 1),
 (7, 1, 2),
 (7, 2, 1),
 (8, 1, 1)]

8.　上記①のためrange(n+1)をrange(1, n-k+2)に変更します。

10. 制約なしの場合0が許されるので、途中経過が10以下であれば解になる可能性はありましたが、全射の場合には1以上なのでn以下となります。

$\ _ 3H_{7}=\ _{9} C_{2}=36$となります。

制約なしと全射の不定方程式の関係

全射の組み合わせを生成する際に、はじめにk個の$x_i$全てに1ずつを代入し、残りのn-k個のなかで制約なしの不定方程式を解けばよいことになります。このため、制約なしで合計がn-kの不定方程式の解を作成しておき、各$x_i$に1ずつを足すことで全射の組み合わせを生成することができます。

制約なしと全射の不定方程式を比較する

equation_unristricted_list = []
for elm in equation_unristricted_func(k, n - k):
equation_unristricted_list.append(tuple([item + 1 for item in elm]) )
equation_surjective_list == equation_unristricted_list

True

2.　引数(k, n-k)で制約なしのindefinite_unristricted_funcを呼び出します。

3.　2.の結果の各項目に1を足し込みます。

4.　#15で作成した全射のプログラムの結果と比較します。

結果はTrueということで、両者は一致していることがわかりした。

数式2-7全射の不定方程式の解の個数

$\sum\limits_{i=1}^k x_i=x_1+x_2+\cdots+x_k=n\quad 1\leqq x_i\leqq n-k+1\;(i=1,2,\cdots,k)$

$\ _k H_{n-k} =\ _{n-1} C_{n-k}=\ _{n-1} C_{k-1}$

合計がnよりも小さくてもよい場合の不定不等式

k個の変数の合計がn以下であるような不等式（制約なし）

次からは応用編です。今度はぴったり10という方程式ではなく、10以下という不等式とします。不定不等式という方はあまりされていないので、とりあえずinequalityとしておきます。

問題6

次の条件を満たす$x_1,x_2,x_3$の組み合わせの数を計算してください。

$x_1+x_2+x_3 \leqq10\quad(x_i\geqq0)$

合計が10だけでなく0から9までも含めて考える必要があるので難しいような気もしますが、不定方程式では$x_0$から$x_{k-2}$までと$x_{k-1}$とで処理を変える必要がありましたが、不等式ではすべてn以下であれば配列に追加する処理でよいので却って単純です。プログラムにおいては不定方程式次のように不等式を等式に書き換えると簡単に計算することができます。ここでは、$k_3$を追加するところで、10ぴったりでなく10以下にすればよいわけです。

関数名は制約なしの不等式という意味でinequality_unristricted_funcとします。

重複組み合わせから制約なしの不定方程式を解く

def inequality_unristricted_func(k, n):
array = [()]
for kth in range(k):
temp = array
array = []
for elm in temp:
for nth in range(n + 1):
if sum(new_elm := elm + (nth,)) <= n:
array.append(new_elm)
else:
break
return array
k=3
n=10
inequality_unristricted_list = inequality_unristricted_func(k, n)
print('unristricted=', len(inequality_unristricted_list))
print('H関数', H(k + 1, n),': comb関数',comb(n + k, n),comb(n + k, k))
pprint.pprint(inequality_unristricted_list)

unristricted= 286
H関数 286.0 : comb関数 286.0 286.0
[(0, 0, 0),
 (0, 0, 1),
 (0, 0, 2),
 (0, 0, 3),
 (0, 0, 4),
 (0, 0, 5),
 (0, 0, 6),
 (0, 0, 7),
 (0, 0, 8),
 (0, 0, 9),

(10, 0, 0)]

9.　とにかく合計がn以下であればリストに追加できます。これは、最後の$x_k$の場合も同じです。

結果的には不定方程式のプログラムより単純になりますが、似たようなものをたくさん作ると混乱してきます。そこで、不定不等式を不定方程式から導く方法を考えます。

$x_1+x_2+\cdots + x_k \leqq n \ x_i\geqq 0\quad(i=1,2,\cdots,k)$

この不等式は、最後に正の整数wを付け加えることにより方程式とみなすことができます。このように不等式を方程式に置き換えるためのwをスラック変数といいます。スラック変数にnと$k_i$の合計との差を表します。

$x_1+x_2+\cdots + x_k +w= n \ x_i\geqq 0\quad(i=1,2,\cdots,k)$

この結果、個数の計算においてはk+1個の正の整数の合計がnになるような組み合わせを見つければよいことになります。そこで、制約なしの不定方程式の解を生成し、配列の右端の要素を切り捨てることにより不等式の解を生成してみます。

スラック変数を使い不等式を方程式に変換して解を生成する

equation_unristricted_list = []
for elm in equation_unristricted_func(k + 1, n):
new_elm = []
for item in elm:
new_elm.append(item )
equation_unristricted_list.append(tuple(new_elm[:k]))
inequality_unristricted_list == equation_unristricted_list

True

2.　引数(k+1, n)で制約なしのequation_unristricted_funcを呼び出します。+1はスラック変数wを指します。

3.　2.の結果の各項目、wを右端に含んだ配列が返されるので、k番目までをスライスすることによりに右端を切り捨てます。

4.　#17で作成した全射のプログラムの結果と比較します。

kを1つ増やして最後の値を切り捨てるだけで方程式が不等式に変化します。このことから次のことがわかります。

数式2-8制約なしの不定不等式の個数

$\sum\limits_{i=1}^k x_i=x_1+x_2+\cdots+x_k\leqq n\quad 0\leqq x_i\leqq n\;(i=1,2,\cdots,k)$

$\sum\limits_{i=1}^k x_i+w=x_1+x_2+\cdots+x_k+w= n\quad 0\leqq w\leqq n$

$\ _{k+1}\mathrm{H}\ _{n} = _{n+k}\mathrm{C}\ _{n}= _{n+k}\mathrm{C}\ _{k}$

k個の変数の合計がn以下であるような不等式（全射）

最後に、不等式で全射の場合の組み合わせを生成します。$x_i\geqq1)$

問題7

次の条件を満たす$x_1,x_2,x_3$の組み合わせの数を計算してください。

$x_1+x_2+x_3 \leqq10\quad(x_i\geqq1)$

#17を変更して解を生成するプログラムを作成します。全射の不等式という意味でinequality_surjective_funcとします。

全射の不等式の解を生成する

def inequality_surjective_func(k, n):
array = [()]
for kth in range(k):
temp = array
array = []
for elm in temp:
for nth in range(1, n - k + 2):
if sum(new_elm:=elm + (nth,)) <= n:
array.append(new_elm)
else:
break
return array
k = 3
n = 10
inequality_surjective_list = inequality_surjective_func(k, n)
print('surjective=', len(inequality_surjective_list))
print('H関数', H(k + 1, n - k),': comb関数', comb(n, n - k),comb(n, k) )
pprint.pprint(inequality_surjective_list)

H関数 120.0 : comb関数 120.0 120.0
[(1, 1, 1),
 (1, 1, 2),
 (1, 1, 3),
 (1, 1, 4),
 ・
・
 
 (7, 1, 2),
 (7, 2, 1),
 (8, 1, 1)]

7.　#17との違いは$x_i$を0からではなく1からはじめます。n+1としてn番目まで探しても結果は変わりませんが、なのでn-k+2とします。

最後に制約なしの方程式から全射の不等式を生成します。

制約なしの方程式で生成した組み合わせから、全射の不等式を生成します。このため、制約なしを全射に変更するためn-kの不定方程式の解を作成しておき、各$x_i$に1ずつを足すとともに、kを1つ増やしてスラック変数を切り捨てる処理を組み合わせます。2つを同時にすることでうまくいくか確認します。

制約なしの方程式で生成した組み合わせから、全射の不等式の解を生成

equation_unristricted_list = []
for elm in equation_unristricted_func(k + 1, n - k):
new_elm = []
for item in elm:
new_elm.append(item + 1)
equation_unristricted_list.append(tuple(new_elm[:k]))
inequality_surjective_list == equation_unristricted_list

True

2.　equation_unristricted_funcを呼び出すときに、スラック変数のk+1と全射のn-kを組み合わせます。

3.　全射にするため各$x_i$に1を加えるとともに、右端のスラック変数を切り捨てます。

2つの処理を加えても、お互いに邪魔することなく正しく配列を生成することができました。

数式2-9全射の不定不等式の個数

$\sum\limits_{i=1}^k x_i=x_1+x_2+\cdots+x_k\leqq n \quad1\leqq x_i\leqq n-k+1\;(i=1,2,\cdots,k)$

$\sum\limits_{i=1}^k x_i+w=x_1+x_2+\cdots+x_k+w=n\quad 0\leqq w\leqq n-k$

$\ _{k+1} H_{n-k}= \ _nC_{n-k} = \ _nC_{k}$

全射の不等式の個数

K個からn個を選ぶ組み合わせは$\ _kC_{n}$個であるのに対し、不等式はkとnが尺転して$\ _nC_{k}$個になります。不思議に思われるので、n=10,k=3を例に図に表します。

k=3なので不定方程式であれば、「しきり」は2つで済みますが、不等式なので$x_k$とスラック変数を区切る「しきり」が1つ必要になるので結果的にk個になります。一方、ボールとボールの間隔は、全射の場合は両端を含まないので9個で済みますが、不等式の場合には右端に1つ追加します。変数の合計が10に等しくなる等号の場合には最後の「しきり」が右端に来ます。これに対して、合計が9になる不等号では、右から2番目において、それ以降はスラック変数1となります。このため、結果的にはn(10)個からk(3)個を選べばよいことになります。

不定方程式、不等式のまとめ

不定方程式をまとめ、シンプルなindefinite_funcという関数名します。4つのパターンの要素を入れ込むと複雑になるので中でindefinite_unristricted_func関数を呼び出しパターンに応じ必要な変換をします。変数leqは不等式の場合にはTrueとします。通常は方程式なのでデフォルトはFalseとします。

組み合わせの関数のまとめ

def equation_func(k, n, option='u',leq=False):
if option == 's':
n-=k
if leq == True:
k+=1
l = equation_unristricted_func(k, n)
if leq == True:
l=[elm[:-1] for elm in l]
if option == 's':
return [tuple([item+1 for item in elm]) for elm in l]
else:
return [tuple([item for item in elm]) for elm in l]
print(len(equation_func(3,10,option = 'u')))
print(len(equation_func(3,10,option = 's')))
print(len(equation_func(3,10,option = 'u', leq=True)))
print(len(equation_func(3,10,option = 's', leq=True)))

2～3.　あらかじめ各変数kに1を割り振ることにより全射を実現するため、n-k個の中で重複組み合わせを計算します。

4～5.　leq=True、つまり変数の合計がn未満も許す場合はkとは別にスラック変数wを想定すればよいのでkを1つ追加します。

6.　2から6で設定したn,kをもとにindefinite_unristricted_funcを呼び出します。

7～8.　不等号の場合は、最後のスラック関数は不要なので取り除く処理をします。

リストをタプルに変換して返り値とします。このとき全射にするため2～3.で各変数のためにとっておいた１を足し込んでいきます。

関数を中に関数をつくると、シンプルにすることができます。また、indefinite_unristricted_funcのような元となる関数をしっかりと作り込んでいけば、後から機能を追加することもできるし、その関数の処理をより効率的にできるとしたら、全ての機能において効率化が図れるので非常に有効といえます。

多項定理と重複要素を含む順列の生成

多項定理を組み合わせの考え方からとらえる

多項定理と重複要素を含む順列の生成はは前章で取り上げましたが、組み合わせの考え方を使うと、効率的に計算することができるので再度取り上げます。

問題8

青いボールが3個、赤いボールが2個、緑色のボールが2個あります。これらの7個上ボールを一列に並べると、その組み合わせは何通りになりますか。ただし、青、赤、緑のボールはそれぞれ区別しないものとします。

順列の問題ですが、7個のボールを置く場所に0から6まで番号を、それぞれの色が何番目に場所を選ぶかを考えることにより組み合わせの問題に変換します。

図のように0から6の7か所に対して、青いボールを置く場所は3か所になるので$ _7C_{3}=35$通りになります。つぎに、35通りに対し、赤いボールを置く場所は残りの4か所のうち2か所になるので$ _4C_{2}=6$通りになります。最後に、残りの白いボール2個は2か所に置くことになるというより、選択の余地が無いので$ _4C_{2}=1$通りになります。つまり、$35\times 6\times1=210$通りになります。

一般化すると、p個、q個、r個の計n個のボールを一列に並べる際の組み合わせは、次のように計算します。

$n=p+q+r$

$ _n C_p\times _{n-p} C _q\times _{n-p-q} C _r$

$\displaystyle= \frac{n!}{p!(n-p)!}\times\frac{(n-p)!}{q!(n-p-q)!}\times\frac{(n-p-q)!}{r!(n-p-q-r)!}$

$\displaystyle= \frac{n!}{p!q!r!(n-p-q-r)!}=\frac{n!}{p!q!r!}$

$\because(n-p-q-r)!=0!=1$

この計算は、色の数が3よりも大きくなっても、同じように約分できるので次のように計算することができます。最終的には、前章での順列による方法から導いた数式と一致します。

数式2-10 多項定理の個数の計算

m種類のボールがそれぞれ$p_k$個、合計n個あるときの多項定理の数

$\displaystyle\frac{n!}{{p_{1}!\cdot p_{2}!\cdot p_{3}!\cdots p_{m}!}}=\frac{n!}{\prod\limits_{k=1}^m p_k!}$

$\sum\limits_{k=1}^m p_k=n$

組み合わせを使い重複要素を含む順列を生成する

選ばれる要素と選ばれない要素を分離する

組み合わせを使い重複要素を含む順列の生成するためには、ある色が決められた個数の場所を選んだら、次の色が残った色からさらに場所を選ぶ必要があります。そこで、組合せを生成する関数を改良し、配列から選ばれる要素と選ばれない要素を分割する必要があります。例えば、[(0,1,2,3,4,5)]から(0,1)が選ばれた場合、[(0,1)(2,3,4,5)]のように分割します。そこで、関数名を組み合わせの残りという意味でcomb_resudial_func とし、分割する配列を(0,1,2,3,4,5)、選ばれる要素数（ここでは2）をnを引数とします。またプログラムをすっきりさせるために、comb_injective_funcを使うのであらかじめ実行しておく必要があります。引数として、選ぶ前のリストoriginalと選ぶ数selected_nを渡し、戻り値として選ばれた組み合わせと選ばれなかった組み合わせを1つの要素の配列を返します。

組み合わせの配列で選ばれなかった要素も入れ込む

def comb_remaining_func(original, selected_n):
array = []
for comb_elm in comb_injective_func(original, selected_n):
remaining = []
for item in original:
if item not in comb_elm:
remaining.append(item)
array.append([comb_elm, tuple(remaining)])
return array
original = range(7)
selected_n = 2
comb_remaining_func(original, selected_n)

[[(0, 1), (2, 3, 4)],
 [(0, 2), (1, 3, 4)],
 [(0, 3), (1, 2, 4)],
 [(0, 4), (1, 2, 3)],
 [(1, 2), (0, 3, 4)],
 [(1, 3), (0, 2, 4)],
 [(1, 4), (0, 2, 3)],
 [(2, 3), (0, 1, 4)],
 [(2, 4), (0, 1, 3)],
 [(3, 4), (0, 1, 2)]]

3.　comb_injective_func関数で生成した組み合わせの組み合わせを1つずつcomb_elmとして取り出します。

5.　選ばれるまでのoriginalに対して、3.で取り出した組み合わせの中で、comb_elmにない要素が選ばれなかったものになるので、remainingに追加します。

8　選ばれたcomb_elmと選ばれなかったremainingをまとめてarrayに追加します。このときremainingはcomb_listに合わせてタプルに変換します。

重複要素を含む順列の並び順を決める

赤3個、青2個、白1個であれば、辞書dictとして[青:3, 赤:2, 緑:2]というリストを引数として渡します。重複要素を含む順列にするために、青いボールが何番目と何番目に置き、次に赤いボールを何番目と何番目に置き、残った場所に白ボールを置くというような並び順の配列を生成します。つまり、リストの左側から青、赤、緑がおかれる場所を[(0, 1, 2), (3, 4), (5, 6)]のようなリストを作成し、このリストから[青,青,青,赤,赤,緑,緑]となるように変換します。にここではcomb_ remaining func関数を早速使用し、その中でcomb_injective_funcを使うのであらかじめ実行しておく必要があります。

重複要素を含む順列を生成する

def multinominal_func(dict):
k_list=list(dict.keys())
n_list=list(dict.values())
n=sum(n_list)
seq_array = [[tuple(range(n))]]
for i in range(len(n_list) - 1):
temp =seq_array
seq_array = []
for elm in temp:
for item in comb_remaining_func( (elm[-1], n_list[i]):
seq_array.append(elm[:-1] + item)
array=[]
for elm in seq_array:
new_elm = [''] * n
for i,item in enumerate(elm):
for num in item:
new_elm[num] = k_list[i]
array.append(tuple(new_elm))
return array
dict = {'青':2, '赤':3, '緑':2}
multinominal_func(dict),len(multinominal_func(dict))

[('青', '青', '青', '赤', '赤', '緑', '緑'),
 ('青', '青', '青', '赤', '緑', '赤', '緑'),
 ('青', '青', '青', '赤', '緑', '緑', '赤'),
 ('青', '青', '青', '緑', '赤', '赤', '緑'),
 ('青', '青', '青', '緑', '赤', '緑', '赤'),
 ('青', '青', '青', '緑', '緑', '赤', '赤'),
 ('青', '青', '赤', '青', '赤', '緑', '緑'),
 ('青', '青', '赤', '青', '緑', '赤', '緑'),

2.　dictとして[青:3, 赤:2, 緑:2]に対して、keys（色:青、赤、緑）をk_list代入します。

3.　同様にdictからvalues(個数,3,2,2)をn_listに代入し4.でその個数をnに代入します。

5.　seq_arrayに①の配列を生成するため、要素数が7の場合、[[(0, 1, 2, 3, 4, 5, 6)]]のように2重のリストに0～6の数字を並べたタプルが入るような配列を作成します。

7.　seq_arrayの中身をいったんtempに代入したのち初期化し、seq_arrayに元の組み合わせ対してcomb_remaining_func関数を使い選ばれた色と選ばれなかった色に分けます。

次にseq_arrayに対し②の組み合わせをarrayに生成します。順列の要素数7の場所を確保し初期化します。

seq_arrayの要素を読み込んだら、初めに0番目の要素青の場所が[0,1,2]に青を代入します。同様に赤、緑の場所に代入していきます。

4.　関数perm_injective_func関数のように、1つのタプルから複数のタプルが生成されるのでarrayの中をtempに置き換えてから配列を生成します。

重複要素を含む順列のプログラムの効率を比較する

前章では順列から重複要素を含む順列を絞りこんで作成しましたが、効率が良くないことを指摘しました。一方、ここでは組み合わせで順番を決める方法で作成しました。そこで両者を同じ条件で実行し、時間を計測します。時間計測はtimeitモジュールのtimeit関数を使用します。

Timeit関数で時間計測をする

import timeit
loop = 500
result = timeit.timeit('multinominal_func2(dict)', globals=globals(), number=loop)
print(result / loop)

0.000678211000000374

　3.　timeitモジュールは変数や関数を独自に名前空間を作りますが、globals=globals()を指定するとまた、numberパラメータで実行回数を指定します。

4.　resultに関数の結果として計算した500回の実行時間が代入されるので、これを実行回数500で割って、1回あたりの実行時間を計算します。