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

不定方程式、不定不等式

重複組み合わせにはさまざまな応用範囲があります。ここでは、その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のような元となる関数をしっかりと作り込んでいけば、後から機能を追加することもできるし、その関数の処理をより効率的にできるとしたら、全ての機能において効率化が図れるので非常に有効といえます。