重複順列、順列（N:ラベルあり K:ラベルあり）

重複順列、順列について、写像とPythonを使って整理します。制約なしの重複順列、単射の順列は最も基本的な位置づけとなりますが、全射となると複雑な計算が必要になります。この考え方は包除原理といい、とても奥深いものがあります。

全射でも単射でもない制約なしの重複順列

重複順列（product sequence with repetition）について理解するため、次の問題を考えます。

問題1

5人の学生が合宿で2つの部屋に分かれて泊まることとします。各学生は、どちらの部屋でも自由に選ぶことができます。5人の学生は出席番号で表し、N={0, 1, 2, 3, 4}とします。また、部屋名はK={A, B}としたとき、部屋割りとして考えられる重複順列の一覧を生成し、その個数を計算してください。

やっていることは単純ですが、写像について理解するため少しまどろっこしい説明が必要になります。

重複順列の考え方

写像からみた重複順列

重複順列などの場合の数では、慣習的に定義域を集合N、終域を集合Kとして、集合Nから集合Kへの写像と捉えます。図表1の１は、$A =\{0, 1\}$、$B=\{2, 4\}$となり、２は全員がAに泊まり$A=\{0, 1, 2, 3, 4\}$、Bには誰も泊まらず、$B=\emptyset$であることを示しています。

ここで次のものは写像になりせん。

集合Nの要素に対応する集合Kの要素がない、つまり野宿はできないということです。
集合Nの要素に対して集合Kの中に対応する要素が複数あることは許されません。つまり部屋Aで騒いで部屋Bで寝るということはできません。

一方、写像について全射や単射の制約なしの場合、次のものは問題ありません。

1つの集合Kの要素に対して複数の集合Nが対応すること、つまり相部屋OKということです。ここでは集合KのAは集合Nの0,1,3に対応しており、単射ではなくても許されます。
集合Kの要素の中に対応する要素がないこと、つまり空き部屋OKということです。このことから、全射でないものも許されます。

上記のことから、重複順列は制約なし（unrestricted）の写像ということができます。

重複順列の生成と個数の計算

重複順列の生成手順を図にすると次のようになります。

0がA,Bの2通りの部屋を選ぶことができ、その各々に対して1が2通り、さらにその各々について2が$2\times2=2^2=4$通り、・・・というように4までの5人に対して繰り返すので、$2^5=32 $通りとなります。最終的には、図の右側のように５人がどの部屋に泊まるかを32個のタプルとして生成し、1つのリストとしてまとめます。このように、重複順列の個数は$k^n$により計算することができるので、Pythonの標準モジュールには関数は用意されていません。この計算式は"k to the n-th power"と読み$\prod$はproductの略号です。

重複順列の個数

$_k\prod{_n}=k^n$

Pythonによる重複順列の生成と個数の計算

itertoolsモジュールのproduct関数による重複順列の生成

itertoolsモジュールのproduct関数を使うと重複順列を生成することができます。itertoolsモジュールはPythonのFunction Programming Moduleに分類されており、イテレータといわれるデータを1つずつ順番に取り出す機能が盛り込まれています。標準ライブラリの1つなので、Pythonがインストールされていれば使うことができます。ただし、ビルドイン関数ではないので、使用する都度、インポートする必要があります。

product関数で重複順列を生成するときは、集合の要素とnの個数をrepeat=nの形式で引数を渡します。

戻り値として0,1,・・4が選んだ部屋がAかBかを表すイテレータが生成されます。また、リストはpprint関数を使うと見やすく表示することができるので、あらかじめpprintをインポートしておきます。

itertoolsモジュールによる重複順列のリストの生成

import itertools
import pprint
k_list = ['A', 'B']
itertools_product_list = list(itertools.product(k_list, repeat = 5))
print('itertools product(2, 5) =',len(itertools_product_list))
pprint.pprint(itertools_product_list)

itertools product(2, 5) = 32
[('A', 'A', 'A', 'A', 'A'),
 ('A', 'A', 'A', 'A', 'B'),
（中略）
 ('A', 'B', 'B', 'A', 'A'),
 ('A', 'B’, 'B', 'A', 'B'),
（中略）
('B', 'B', 'B', 'B', 'A'),
('B', 'B', 'B', 'B', 'B')]

4.　イテレータをリストとして扱うときには、list関数を使いリスト型に変換する必要があります。

6.　生成した重複順列は、pprint関数で出力すると行ごとに表示され見易くなります。

product関数は、直積（デカルト積cartesian product）を生成する関数で、2つ以上の集合の要素間で総当たりの組み合わせを生成します。ここではk_list別々の5つの集合として捉え、直積を取るのでrepeat=5としています。その意味ではproduct関数の特殊な使い方といえます。

重複順列を生成する関数

重複順列を生成する関数の流れ

図表2のような重複順列を配列arrayに作成する場合、次の2つの考え方があります。

① n回forループを回し、arrayに各人がどの部屋を選ぶかを順次追加

少し専門的になりますが、幅優先探索（BFS = Breadth-First Search）という方法です。

初期の定義時: array = [(, )]

1回目のループ: array = [(A, ), (B, )]

2回目のループ: array = [(A, A), (A, B), (B, A), (B, B)]

3回目のループ: array = [(A, A, A), (A, A, B), (A, B, A), (A, B, B) , (B, A, A), (B, A, B), (B, B,A), (B, B,B)]

・・

のように追加します。

② はじめに1つ配列を作成し、そこから要素を入れ替え

深さ優先探索（DFS = Depth-First Search）という方法です。

1つ目　(A, A, A, A, A)

2つ目　(A, A, A, A, B)

3つ目　(A, A, A, B, A)

・・のように追加します。

ここでは、図表3のように、流れがシンプルな①の幅優先探索でプログラムを作成します。

arrayの中の作成途中の重複順列をelmとして順次読み込み、itemは各人がどの部屋に入るかを表します。1つのelmに対しAを追加したものとBを追加したものというように複数個のタプルをarrayに追加します。この流れでは配列arrayを読み込みながら、そのarrayに重複順列を追加する処理が必要になり、永久ループに陥る恐れがあります。そこで図表3のように、arrayの内容を1度リストtempにコピーし、arrayをクリアしたのちtempから順次読み込み、Aを付け加えた重複順列と、Bを付け加えたタプルをarrayに追加していきます。

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

前節の考え方に沿って、重複順列を生成する関数を作成します。関数名は制約なし(unrestricted)の順列(permutation)という意味でperm_unrestricted_funcとし、itertoolsと同様にk_listとnの2つの引数として渡します。なお、重複順列の各重複順列は、タプルにします。タプルはリストとは異なり、1度作ると変更することができません。このような性質をイミュータブル（変更不可）といい、ミュータブル（変更可能）であるリストよりも構造が単純であるため、マシンへの負荷が少なくなります。また、イミュータブルであることは不便な気もしますが、作成した配列を使っていろいろな処理をする場合、途中で勝手に変えられないので、予測不能なエラーが発生するリスクが少なくなるというメリットもあります。

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

引　数

k_list

集合Kの要素をタプルで指定

集合Nの要素の個数を指定

返り値

perm_unrestricted_list

重複順列を2重リスト形式で返す。

引　数

k_list

集合Kの要素をタプルで指定

引　数

集合Nの要素の個数を指定

返り値

perm_unrestricted_list

重複順列を2重リスト形式で返します。

def perm_unrestricted_func(k_list, n):
array = [()]
for _ in range(n):
temp = array
array = []
for elm in temp:
for item in k_list:
array.append(elm + (item,))
return array
n = 5
k_list= ['A', 'B']
perm_unrestricted_list = perm_unrestricted_func(k_list, n)
print('perm_unrestricted_func(2, 5) =',len(perm_unrestricted_list))
if perm_unrestricted_list == itertools_product_list:
print('perm_unrestricted_list == itertools_product_list')

perm_unrestricted_func(2, 5) = 32
perm_unrestricted_list == itertools_product_list

2.　arrayを初期化する際に、空のタプルを要素として持つリストとして定義します。次の4.でtempにコピーし、6.で制作途中の重複順列を読み込む際に何かしらのタプルがないとエラーになるためです。

3.　4.～8.により次のように、重複順列の作成途中のタプルを追加する処理をn回繰り返します。

1回目のループ: temp = [()], array = [(A ,), (B, )]

2回目のループ: temp = [(A,), (B,)], array = [(A, A), (A, B), (B, A), (B, B)]

3回目のループ: temp =[(A, A), (A, B), (B, A), (B, B)], array = [(A, A, A), (A, A, B), (A, B, A),・・のように推移します。

8.　リストtempからこれまで作成した1つ1つの作成途中のタプルをelmとして取り出し、k_listから取り出したitemを右側に結合しarrayに追加します。要素が1つだけのタプルは(item,)のようにかっこの中で変数にカンマを付けます。

このことにより、arrayが長さnの重複順列のリストとして返します。最終的にproduct関数と同じ結果になります。

単射としての順列

場合の数の中で最もよく使われる順列（permutation）について理解するため、次の問題を考えます。

問題2

3人の学生が合宿でそれぞれ個室に泊まることとします。宿舎にはK={A, B, C, D, E}の5部屋が用意されており、学生は出席番号で表し、N={0, 1, 2}としたときの部屋割りとして考えられる順列を一覧にし、その場合の数を計算してください。

写像からみた順列と個数の計算

順列について写像の視点から理解し、関数を使い個数を求め生成します。

写像から見た順列の考え方

こんな時代なのでみんな個室がよい、ということで誰もが同じ部屋に泊まらないような部屋割りも考えられます。写像から見ると、図表4のように、終域に属する要素は全てその定義域の要素にただ1つだけ対応させる単射(injective)となります。

SciPyライブラリ、mathモジュールのperm関数による順列の場合の数の計算

SciPyライブラリのspecial サブモジュールにあるperm関数により順列の場合の数を計算することができます。このほかPythonバージョン3.8以降ではmathモジュールにもperm関数が追加されました。ここでは順列に関する関数をご紹介しますが、ついでに組み合わせに関わる関数についてもご紹介しておきます。

math関数、SciPyライブラリを使い順列の個数を計算する

from scipy.special import perm, comb
import math
print(f'scipy.special.perm(2, 5) = {perm(n, len(k_list), exact = True)}')
print(f'scipy.special.comb(2, 5) = {comb(n, len(k_list), exact = True)}')
print(f'math.perm(2, 5) = {math.perm(n, len(k_list))}')
print(f'math.comb(2, 5) = {math.comb(n, len(k_list))}')

scipy.special.perm(2, 5) = 20
scipy.special.comb(2, 5) = 10
math.perm(2, 5) = 20
math.comb(2, 5) = 10

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

2.　mathモジュールはモジュール全体をインポートするのが一般的です。

3.　SciPyライブラリのperm関数は組み合わせの数を小数点で返します。整数で戻り値を返すときは、exact = Trueを指定します。

4.　同様に、SciPyライブラリのcomb関数により組み合わせの個数を計算します。

5.　mathモジュールのperm関数は返り値として整数で組み合わせの数を返します。同様に6.においてcomb関数で組み合わせの個数を計算します。ただし、Pythonのバージョン3.8以降でないと使うことはできません。

順列、組み合わせおよび階乗を計算する関数を作成する

通常、順列はn個からr個を重複なく選ぶと考え$\ _n P_r$と表記しますが、写像では$\ _k P_n$とするのが一般的です。

順列の個数の計算

$\displaystyle \ _n P_r = \frac{n!}{(n-r)!}=\;\overbrace {n(n-1)(n-2)・・・(n-r+1) \quad}^{r個}$

$\displaystyle \ _n C_r =\frac{\ _n P_r}{n!}=\frac{n!}{r!(n-r)!} = \frac{\overbrace {n(n-1)(n-2)\cdots (n-r+1)}^{r個}}{\underbrace {r\times (r-1)\times \cdots 2 \times 1}_{r個}}$

$\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個}}$

$\displaystyle \ _k P_n = \frac{k!}{(k-n)!}=\;\overbrace {k(k-1)(k-2)・・・(k-n+1) \quad}^{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個}}$

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

①階乗：factorial 関数

引数を正の整数nとして、nから1までを掛け合わせます。ただし$\ _5 P_3=5\times 4\times 3$のような計算をする場合のように、大きな順番に3つだけ掛け合わせれば足りることもあります。そこで、2つ目にrという引数を追加し、指定した場合はその個数だけの掛け算とし、指定しない場合には1まで掛け合わせるような工夫をします。なお、0!=1となることも処理に組み込みます。

②順列：P関数

引数として集合Kの個数kと集合Nの個数nを指定します。つまりk個からn個を選んで並べる順列の個数を計算します。P関数は$k \lt p$の場合は0、$n=0$の場合は1となることが必要です。

③：C関数

P関数と同様に組み合わせの個数を計算します。C関数は$k \lt n$の場合は0、$n=0$の場合は1となることが必要です。

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

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!の計算ができるようになります。なお、rがNoneであるときの判断は。is演算子を使います。

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モジュールのpermutations関数による順列の生成

Pythonの標準モジュールであるitertoolsモジュールのpermutations関数により、順列を生成することができます。引数は重複順列と同様です。

itertoolsモジュールによる順列のリストの作成

k_list = ['A', 'B', 'C', 'D', 'E']
n = 3
itertools_perm_list = list(itertools.permutations(k_list,n))
print('itertools.permutations(5, 3) = ',len(itertools_perm_list ))
pprint.pprint(itertools_perm_list)

itertools.permutations(5, 3) =  60
[('A', 'B', 'C'),
 ('A', 'B', 'D'),
 （中略）
('E', 'D', 'A'),
 ('E', 'D', 'B'),
 ('E', 'D', 'C')]

2.　itertoolsモジュールのpermutations関数により、順列のリストを出力することができます。

順列の個数は$5\times4\times3=60$となります。

重複組み合わせを全射にする

全射の考え方と生成するプログラム

写像からみる全射の考え方

ここからが山場です。全射の考え方を理解するため次の問題を考えてみましょう。

問題3

5人の学生が合宿で2つの部屋に分かれて泊まることとします。各学生は、どの部屋を自由に選んでよいものとしますが、空き部屋が出ることは許されません。5人の学生は出席番号で表し、N={0, 1, 2, 3, 4}とします。また、部屋名はK={“A”, ”B”}としたとき、部屋割りとして考えられる重複順列を生成し、場合の数を計算してください。

#2では全学生が部屋A、または部屋Bに集中している重複順列が見られます。宿の方がせっかく2部屋を確保してくれたのに空き部屋にしてしまうのでは、品格を疑われてしまいます。そこで、少なくとも1部屋に1人は泊まるような重複順列を考えます。集合Kに集合Nから対応つけられない要素が存在することを許さないのが全射(surjective)このため、図表5の左のような(A, A, B, A, B)は問題ありませんが、右のように(A, A, A, A, A)や、図にはありませんが、(B, B, B , B, B)のような重複順列は対象になりません。

全射の重複順列を生成する関数

Pythonの標準ライブラリには、全射の重複順列の生成や個数の計算をする関数が見当たらないので自作します。重複組み合わせの全射という意味で関数名をperm_surjective_funcとします。引数は重複順列を生成する関数と同じです。全射の条件を満たしているかは最後の1人にならないと判断できないので、itemをelmに追加するところをn-1とそれ以前に分けて、最後の1人で全射かどうかを判断します。

重複順列を配列として出力

def perm_surjective_func(k_list, n):
array = [()]
for cnt in range(n):
temp = array
array = []
for elm in temp:
for item in k_list:
if cnt < n-1:
array.append(elm + (item,))
else:
if set(k_list).issubset(set(new_elm := elm + (item,))) :
array.append(new_elm)
return array
n = 5
k_list= ['A', 'B']
perm_surjective_list = perm_surjective_func(k_list, n)
print('unrestricted = ',len(k_list)**n,'surjective = ',len(perm_surjective_list))
pprint.pprint(perm_surjective_list)

unrestricted =  32 surjective =  30
[('A', 'A', 'A', 'A', 'B'),
 ('A', 'A', 'A', 'B', 'A'),
 ('A', 'A', 'A', 'B', 'B'),
 ('A', 'A', 'B', 'A', 'A'),
 （中略）
('B', 'B', 'B', 'A', 'B'),
 ('B', 'B', 'B', 'B', 'A')]

8.　n=4の場合、0 から3人目の2までについては、無条件にnew_elmをarrayに追加します。このため、n<1が条件になります。

11. 最後の1人は9.にあてはまらないので、12.で作成した重複順列が全射の要件を満たすnew_elmのみを要素をarrayに追加します。なおnew_elm := elm + (item,)は、new_elmにelm + (item,)を代入したうえで、この中にk_listの要素が含まれているかを判断します。このような”:=”を:ウォルラス演算子（Walrus operator）といい、形からセイウチ演算子と呼ばれます。ただし、ウォルラス演算子はPythonのPythonの v3.8以降でないと使うことはできないので、その場合は次のようにコーディングします。

for elm in temp:

for item in k_list:

new_elm = elm + (item,)

if cnt < n-1:

array.append(new_elm)

else:

if set(k_list).issubset(new_elm):

array.append(new_elm)

全射の重複順列を集合(set)に変換すると{A, B}となり、k_listの個数と等しくなります。これに対して全射でない(A, A, A, A, A)は{A}となり、k_listの個数よりも小さくなります。このように、全射の判断をするために、作成した配列を集合に変換し、その個数と要素の種類を比較するのが定石です。この例では、制約なしの32通りに対し、(A, A, A, A, A)、(B, B, B, B, B)の2通りが取り除かれ、30通りが全射の場合の数であることがわかりました。

全射の重複順列を集合で考える

k=2のような簡単な例であれば、直ぐに計算することはできますが、kの数が増えるにしたがって話は複雑になります。そこで、集合の考え方を使って整理し、kがどんなに大きくなっても対応できるようにしたいと思います。

ここから、全射の重複順列の個数を計算します。ここでのコツはAが空室になる事象を集合A、Bが空室になる事象を集合B、というように空室になる事象を考えることです。

重複順列では、集合Kの要素Aが集合Nと対応付けられない重複順列を集合Aと定義します。この場合、(B, B, B, B, B)が当てはまります。一方(A, A, A, A, A)のように要素Bが集合Nと関連付けられない重複順列を集合Bと定義します。ここから、全射の条件を満たさない重複順列は$A \cup B$になり、2個になります。これに対して全ての重複順列は全体集合(universe)といい集合Uで表します。ここでは集合Uの要素数は32個になります。したがって求める全射の重複順列は集合Aでも集合Bでもないものを数えればよいことになります。これは$\overline{A\cup B})$のようになり、個数は全体集合Uの個数から$A\cup B$の個数を差し引いた30個になります。

2つの集合の演算

全射の計算をする前提として2つの集合演算の一般的な公式を具体例を使い整理します。まず、次の3つの集合を定義します。

全体集合Uとして1から20までの整数を定義します。

2の倍数：集合A={2, 4, 6, 8,10, 12, 14, 16, 18, 20}の10個

3の倍数の集合B={3, 6, 9, 12, 15, 18}の6個

集合Aと集合Bの共通部分は積集合（intersection)といい、 $A \cap B=\{6, 12, 18\}$の3個になります。6の倍数なので簡単に求めることができます。また、集合Aには含まれるが集合Bに含まれない要素の集合を差集合（difference)といい$A-B=A\setminus B=A\cup \overline{B}=\{2, 4 , 8, 10, 14, 16, 20\}$の7個になります。同様に$B-A=B\setminus A=B\cup \overline{A}=\{3, 9, 15\}$の3個になります。ここまでは簡単ですが、集合Aか集合Bのいずれかに含まれている要素である和集合（union）$A \cup B=\{2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20\}$の13個、またAでもBでもない集合Uの補集合$\overline\{A \cup B \}=U\setminus (A \cup B)=\{1, 5, 7, 11, 13, 17, 19\}$の7個となりここまでくるとこれは数えるのには少し骨が折れます。

操作	英語	演算子	記号	内包的記法
和集合	union	\|	$A\cup B$	$\{x \mid x \in A \vee x \in B\}$
積集合	intersection	&	$A\cap B$	$\{x \mid x \in A \wedge x \in B\}$
差集合	difference	-	$A\setminus B$	$\{x \mid x \in A \wedge x \notin B\}$
対称差集合	symmetric_difference	^
補集合	(complement)		$ \overline A$ $U \setminus A$	$\{x \mid x \in U \wedge x \notin A\}$

Pythonを使って集合演算を行う際、Pythonでは3列目の演算子を使うと、それぞれの集合演算をすることができます。

2つの集合の演算

n = 20
U = set(range(1, n + 1))
A = set(range(2, n + 1, 2))
B = set(range(3, n + 1, 3))
union = A | B
intersection = A & B
difference_AB = A - B
difference_BA = B - A
symmetric_difference = A ^ B
complement = (U - (A | B))
print(f'A | B = {union}')
print(f'A & B = {intersection}')
print(f'A - B = {difference_AB}')
print(f'B - A = {difference_BA}')
print(f'U - (A | B)= {complement}')

A | B = {2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20}
A & B = {18, 12, 6}
A - B = {2, 4, 8, 10, 14, 16, 20}
B - A = {9, 3, 15}
U - (A | B)= {1, 5, 7, 11, 13, 17, 19}

2.　整数を要素とする集合を定義するため、range関数で範囲を定めset関数で集合に変換します。

3.　集合Aは2の倍数2の倍数の集合を定義するため、range関数で(2,n+1,2)とすることにより、2から始まり2つおきに整数を設定することができます。

4.　同様に集合Bは3から始まり3つおきの整数としてset(range(3, n + 1, 3))と定義します。

5.　これ以降は、定義した集合に対して演算を行います。

2つの集合のベン図

これらの関係はベン図にするとわかりやすくなります。2集合のベン図はmatplotlibライブラリの拡張ライブラリであるvenn2で描くことができます。なお、venn2は使用する際、一度だけpip install matplotlib_vennによりインストールする必要があります。

２つの集合のベン図を描く

from matplotlib import pyplot as plt
from matplotlib_venn import venn2
fig,ax = plt.subplots()
diagram2 = venn2([ A , B], set_labels=('A:multiples_of_2', 'B:multiples_of_3'))
plt.title('Venn Diagram of Multiples of 2 and 3 up to 20')
diagram2.get_label_by_id('10').set_text('\n'.join(map(str,difference_AB)))
diagram2.get_label_by_id('01').set_text('\n'.join(map(str,difference_BA)))
diagram2.get_label_by_id('11').set_text('\n'.join(map(str,intersection)))
plt.text(0.6, 0.5, ' '.join(map(str,complement)), ha='right', va='top')
fig.patch.set_facecolor('#e6f2ff') #fig.patch.set_facecolor('#e6f2ff'):
plt.tight_layout()
plt.show()

2.　venn2はmatplotlibとは別にインポートする必要があります。

4.　venn2関数は2つの集合（AとB）を引数として受け取り、ベン図を描画します。set_labelsパラメータで各集合のラベルを指定しています。

6.　ベン図の各領域へのテキスト追加: get_label_by_idメソッドを使用して、ベン図の特定の領域にアクセスし、set_textで内容を設定しています。8行目までIDは以下のように対応します：

'10': Aのみの領域

'01': Bのみの領域

'11': AとBの共通部分テキストは'\n'.join(map(str,intersection))を使用して複数の要素を改行で区切って表示しています。

集合intersectionには積集合が整数で列挙されていますが、文字として表示するため、全て文字列に変換します

intersection（集合）の各要素を文字列に変換します。

str関数がintersectionの各要素に適用されます。

変換された文字列の要素を改行文字（\n）で結合します。

なお、集合（set）の場合、要素が昇順に並ぶとは限らないので注意が必要です。

和集合と補集合の個数の計算

ベン図を見ると、集合Aと集合Bの和集合の数は、集合Aと集合Bの個数から積集合を引いた数になることがわかります。なお、集合Aの要素の数をn(A)と定義します。

\begin{align*} n(\overline{A\cup B}) &= n(U) - n(A \cup B) && \text{補集合の性質} \\ &= n(U) - \{n(A) + n(B) - n(A \cap B)\} && \text{包除原理} \\ &= n(U) - \{n(A) + n(B)\} + n(A \cap B) && \text{括弧の展開} \end{align*}

集合演算で確認します。

和集合、和集合の補集合の要素の個数

print(f'n(A | B)={len(A|B)}')
print(f'n(A)+n(B)-n(A & B)={len(A)+len(B)-len(A&B)}')
print(f'n(U)-n(A & B)={len(U-(A|B))}')

n(A | B)=13
n(A)+n(B)-n(A & B)=13
n(U)-n(A & B)=7

1.　$n(A \cup B)$を計算すると13個となり正しく計算することができました。

2.　$n(A)+n(B)-n(A \cap B)=10+6-3=13$となり、1と一致することがわかります。

3.　全体集合の個数n(U)=20から、$n(A \cup B)$を差し引くと7となり正しく計算できたことがわかります。

例題への適用

集合で考えると、全事象Uは$2^5=32$通り、Aは(B, B, B, B, B)の$1^5=1$通り、Bも (A, A, A, A, A)も$1^5=1$通りになります。AもBも空室はありえないので、$n(A\cap B) =\varnothing$、となります。UからAとBを差し引き、32-1-1=30通りになります。集合演算では次のようになります。なお、一般に集合Aの個数はn(A)のように表現します。

n=5,k=2のときの全射の重複順列の個数

$n(U)=2^5=32$

$n(A)= n(B)=1^5$

$n(A\cap B)=0$

$n(A\cup B)=n(A) + n(B) - n(A\cap B) = 1 + 1 - 0=2$

$n(\overline{A\cup B})=n(U)-\{n(A)+n(B)-n(A\cap B)\}=30$

計算結果が合致しました。

部屋数k=3の場合

写像による計算

集合Kの要素が3つになると、話がむつかしくなります。例として、n={0, 1, 2, 3, 4}、k={A, B, C} としてリストを作成します。

図の左のような(A, A, C, A, C)のようにBが選ばれない重複順列はもとより右のように(A, A, A, A, A)は全射になりません。

早速#6で作成したperm_surjective_func関数を使い、重複順列を生成したのち個数を数え、制約なしの重複縦列と比べます。

K=3の場合の全射の計算

n = 5
k_list= ['A', 'B', 'C']
perm_surjective_list = perm_surjective_func(k_list, n)
print('unrestricted = ',len(k_list)**n,'surjection = ',len(perm_surjective_list))
pprint.pprint(perm_surjective_list)

unrestricted =  243 surjection =  150
[('A', 'A', 'A', 'B', 'C'),
 ('A', 'A', 'A', 'C', 'B'),
 ('A', 'A', 'B', 'A', 'C'),
 ('A', 'A', 'B', 'B', 'C'),
 ('A', 'A', 'B', 'C', 'A'),
 ('A', 'A', 'B', 'C', 'B'),
（中略）
('C', 'C', 'C', 'C', 'C'),

2.　perm_surjective_func関数で計算した結果を、リストperm_surjective_listに代入します。

3.　重複順列$3^5=243$通りのうち、全射は150通りになります。この差の分析をして、個数の計算方法を考えます。

3つの集合の演算

全体集合Uとして1から30までの整数を定義します。これに対して、

2の倍数の集合A={2, 4, 6, 8,10, 12, 14, 16, 18, 20, 22, 24,26,28,30}の10個、

3の倍数の集合をB={3, 6, 9, 12, 15, 18,21,24,27,30}の6個、

5の倍数の集合をB={5, 10, 15, 20, 25, 39}

とします。

集合A集合B集合Cの共通部分（intersection) $A \cap B=\{30\}$の1個になります。30の倍数なので簡単に求めることができます。

次に3つの集合の場合の複雑な例として集合A、集合Bの要素ではあるが集合Cの要素ではないような集合が考えられます。特にきまった名称はありませんが、ここではAとBの「積集合からCを除いた部分」と呼ぶことにします。このようなケースは次の3つが考えられます。

AとBの積集合からCを除いた部分　$A \cap B \cap \overline{C}=\{6, 12, 18, 12, 24\}$

AとCの積集合からBを除いた部分$A \cap C \cap \overline{B}=\{10, 20\}$

BとCの積集合からAを除いた部分$B \cap C \cap \overline{A}=\{15\}$

次に集合Aには含まれるが、その他の集合には含まれないような集合を相対的補集合(relative_complement)といいます。このような集合も次の3つのケースがあります。

$A \cap\overline{B}\cap\overline{C}=A \setminus B \setminus C={2, 4, 8, 14, 16, 22, 26, 28}$

$B \cap\overline{A}\cap\overline{C}=B \setminus A \setminus C={3, 9, 21, 27}$

$C \cap\overline{A}\cap\overline{B}=C \setminus A \setminus B={5, 25}$

1から30までの整数

n = 30
U = set(range(1, n + 1))
A = set(range(2, n + 1, 2))
B = set(range(3, n + 1, 3))
C = set(range(5, n + 1, 5))
union_ABC = A | B | C
intersection_ABC = A & B & C
intersection_AB_minus_C = A & B - C
intersection_BC_minus_A = B & C - A
intersection_AC_minus_B = A & C - B
difference_A_minus_BC = A - B - C
difference_B_minus_AC = B - A - C
difference_C_minus_AB = C - A - B
complement_ABC = (U - (A | B | C))
print(f'A | B | C ={union_ABC}')
print(f'A & B & C = {intersection_ABC}')
print(f'A & B - C = {intersection_AB_minus_C}')
print(f'B & C - A = {intersection_BC_minus_A}')
print(f'A & C - B = {intersection_AC_minus_B}')
print(f'A - (B | C) = {difference_A_minus_BC}')
print(f'B - (A | C) = {difference_B_minus_AC}')
print(f'C - (A | B) = {difference_C_minus_AB}')
print(f'U - (A | B | C) = {complement_ABC}')

A | B | C ={2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30}
A & B & C = {30}
A & B - C = {24, 18, 12, 6}
B & C - A = {15}
A & C - B = {10, 20}
A - (B | C) = {2, 4, 8, 14, 16, 22, 26, 28}
B - (A | C) = {27, 9, 3, 21}
C - (A | B) = {25, 5}
U - (A | B | C) = {1, 7, 11, 13, 17, 19, 23, 29}

2.　全体集合として1からn =30までの整数を集合Uとして定義します。定義するときはrangeで定義した範囲にset関数を適用します。同様に2から5で次の通り集合を定義します。

U: 1から30までのすべての整数

A: 2の倍数（2, 4, 6, ..., 30）

B: 3の倍数（3, 6, 9, ..., 30）

C: 5の倍数（5, 10, 15, ..., 30）

6.　積集合の演算子を使って、A,B,Cの積集合を計算します。変数名はintersection_ABCとします。

7.　積と差集合の演算子を使い「積集合からCを除いた部分」を計算します。変数名はintersection_AB_minus_C とします。同様に、Bを除いた部分、Aを除いた部分を計算します。 = A & B & C intersection_AB_minus_C = A & B - C intersection_BC_minus_A = B & C - A intersection_AC_minus_B = A & C - B 集合の交差と差集合を計算しています。&演算子は交差を、-演算子は差集合を表します。

11.　 AではあるがBでもCでもない集合、変数をdifference_A_minus_BC = A - B - Cとします。ここでは$A \setminus (B \cup C)$の式で計算していますが、次の式でも計算することができます。

14.　complement = (U - (A | B | C)) 全体集合Uに対するA, B, Cの和集合の補集合を計算しています。

15.　print(f'A & B & C = {intersection_ABC}') ... print(f'U - (A | B | C) = {complement}') 計算結果を出力しています。f-stringを使用して、各集合演算の結果を見やすく表示しています。

3つの集合のベン図

3つの集合の関係を見るためにベン図を描いてみます。

venn3による3つの集合のベン図を描く

from matplotlib import pyplot as plt
from matplotlib_venn import venn3
fig ,ax = plt.subplots()
diagram3= venn3([A , B, C], set_labels = ('A:multiples_of_2', 'B:multiples_of_3', 'C:multiples_of_5'))
plt.title('Venn Diagram of Multiples of 2,3 and 5 up to 30')
diagram3.get_label_by_id("100").set_text( "\n".join(map(str,difference_A_minus_BC)))
diagram3.get_label_by_id("010").set_text( "\n".join(map(str,difference_B_minus_AC)))
diagram3.get_label_by_id("001").set_text( "\n".join(map(str,difference_C_minus_AB)))
diagram3.get_label_by_id("110").set_text( "\n".join(map(str,intersection_AB_minus_C)))
diagram3.get_label_by_id("011").set_text( "\n".join(map(str,intersection_BC_minus_A)))
diagram3.get_label_by_id("101").set_text( "\n".join(map(str,intersection_AC_minus_B)))
diagram3.get_label_by_id("111").set_text( "\n".join(map(str,intersection_ABC)))
plt.text(0.6, 0.6, ' '.join(map(str,U- (A | B | C))), ha='right', va='top')
fig.set_facecolor('#e6f2ff')
plt.tight_layout()
plt.show()

Matplotlib（グラフ描画ライブラリ）の拡張ライブラリをインポートします。

6-12. diagram3.get_label_by_id("xxx").set_text("\n".join(yyy)) get_label_by_id メソッドを使用して、ベン図の特定の領域にアクセスし、set_text で内容を設定しています。"xxx" の部分は以下のように対応します：

"100": A のみの領域

"010": B のみの領域

"001": C のみの領域

"110": A と B の共通部分（C を除く）

"011": B と C の共通部分（A を除く）

"101": A と C の共通部分（B を除く）

"111": A, B, C の共通部分テキストは '\n'.join() を使用して複数の要素を改行で区切って表示しています。

plt.show() 作成したベン図を表示します。

$ n(A \cup B \cup C)$

$= n(A)+n(B)+n(C)- n(A \cap B) -n(A \cap C) -n(B \cap C)+n(A \cap B \cap C)$

$n(\overline{A\cup B \cup C})=n(U)-n(A \cup B \cup C)$

$=n(U)-n(A)-n(B)-n(C)+ n(A \cap B) +n(A \cap C) +n(B \cap C)-n(A \cap B \cap C)$

これは、ベン図を見ればよくわかります。

3つの集合での法則

3つの集合の積集合、和集合を3つ以上つなげた場合は、計算する順序によらず同じ結果になります。

結合法則 associative property

$A \cup B \cup C=(A \cup B) \cup C=A \cup(B \cup C)$

$A \cap B \cap C=(A \cap B) \cap C=A \cap(B \cap C)$

この法則は、ベン図を見れば明らからで、今後の計算で適用できるものとして考えます。ただし、結合法則が成り立つのは、和集合、積集合が同じ記号が並んだ時だけです。記号が混在するときには、次の分配法則が成り立ちます。

和集合と積集合が混在する場合は次のような法則が成り立ちます。

分配法則 distributive law

$A \cup(B \cap C)=(A \cup B) \cap(A \cup C)$

$A \cap(B \cup C)=(A \cap B) \cup(A \cap C)$

$(A \cap B) \cup C=(A \cup C) \cap(B \cup C)$

$(A \cup B) \cap C=(A \cap C) \cup(B \cap C)$

また、当たり前のようですが、冪等法則も注意が必要です。冪等法則は和集合と積集合についての法則がありますが、ここでは積集合の冪等法則を使います。

和集合の冪等法則　Idempotency of Union

$A \cup A =A$

積集合の冪等法則 Idempotency of Intersection

$A \cap A =A$

$(A \cap C) \cap (B \cap C) = A \cap B \cap C$

ここから、集合の数が3の場合の方除原理の計算は次の通りになります。

\begin{aligned} n(A \cup B \cup C) &= n((A \cup B) \cup C) \\ &= n(A \cup B) + n(C) - n((A \cup B) \cap C) \\ &= n(A)+n(B)- n(A \cap B) +n(C)-n((A \cap C) \cup (B \cap C)) \\ &= n(A)+n(B)- n(A \cap B) +n(C)-(n(A \cap C) +n(B \cap C)-n(A \cap C) \cap (B \cap C)) \\ &= n(A)+n(B)+n(C)- n(A \cap B) -n(A \cap C) -n(B \cap C)+n(A \cap B \cap C) \end{aligned}

写像からみた包除原理

①全体集合

空室も許した制約なしの重複順列$k^n$を計算します。全体集合Uは5人が3部屋を自由に選ぶことができるので$3^5=243$通りになります。

$n(U)= 3^5=243$

②1部屋以上空き部屋になる場合

Aが空き部屋になる集合Aの場合の数は5人をB, Cの部屋に割り振ることになるので、$2^5=32$通りになります。同じように、集合Bも集合Cも32通りになります。そこで空室が出ない重複順列は、全体集合からこれらA, B, Cの3つの集合の数の合計($32\times3=96$)を差し引くことで計算することができます。

$n(A)=n(B)=n(C)=2^5=32$

$243-32\times3=147$

③2部屋以上空き部屋になる場合

②で差し引いた中には (C, C, C)のように集合Aにも集合Bにも含まれる$n(A\cap B)$があり、その場合の数は$1^5=1$になります。$n(A\cap B)$は②で2重に差し引かれているので、逆に足し戻してやる必要があります。このようなものは$n(B\cap C)である(A, A, A), n(C\cap A)$である(B, B,B)の３つあります。

$n(A\cap B)=n(B\cap C)=n(C\cap A)=1^5=1$

$147+1\times3=150$

④3部屋以上空き部屋になる場合

集合の考え方からすると、ＡもＢもＣも空室の場合、$A\cap B\cap C$があれば、③で足し戻し過ぎになるので、さらに差し引く必要が生じます。もっとも今回は、全室空室はありえませんからここは0になります。

$n(A\cap B\cap C)=0^5=0$

$150-0 =150$

ベン図を課題に適用する

計算式は次の通りになります。

n=5,k=3のときの全射の重複順列の個数

$n(\overline{A\cup B\cup C})$

$=n(U)-\{n(A)+n(B)+n(C)\}$

$+\{n(A\cap B)+n(B\cap C)+n(C\cap A)\}-n(A\cap B\cap C)$

$=243-32\times3+1\times3-0=150$

部屋数が4の場合

関数による計算

k=4になると、さらに複雑になります。kがさらに増えることも見据えて検討します。組み合わせと件数を確認します。ここではn=7、k_list= ['A', 'B', 'C', 'D']とします。

４部屋の場合

n = 7
k_list= ['A', 'B', 'C', 'D']
perm_surjective_list = perm_surjective_func(k_list, n)
print('unrestricted = ',len(k_list)**n,'surjection = ',len(perm_surjective_list))
pprint.pprint(perm_surjective_list)

unrestricted =  16384 surjection =  8400
[('A', 'A', 'A', 'A', 'B', 'C', 'D'),
 ('A', 'A', 'A', 'A', 'B', 'D', 'C'),
 ('A', 'A', 'A', 'A', 'C', 'B', 'D'),
 ('A', 'A', 'A', 'A', 'C', 'D', 'B'),
  ・
・
('D', 'D', 'D', 'D', 'C', 'B', 'A')]

1.　#7と同じことをn=7,k=4として実行します。

集合論からk=4の包除原理を計算する

はじめに集合の定理から包除原理を計算します。まずは結論からいうと次のような式になります。

K=4の包除原理

$ n(A \cup B \cup C \cup D)$

$= n(A)+n(B)+n(C)+n(D)$

$-\{n(A \cap B)+n(A \cap C)+n(A \cap D)+n(B \cap C)+n(B \cap D)+n(C \cap D)\}$

$+\{n(A \cap B \cap C)+n(A \cap B \cap D)+n(A \cap C \cap D)+n(B \cap C \cap D)\}$

$-n(A \cap B \cap C \cap D)$

この計算式は次の通り、結合法則、分配法則、和集合の冪等法則を繰り返し適用することにより求めることができます。

\begin{aligned} n(A \cup B \cup C \cup D) &= n((A \cup B \cup C) \cup D) \\ &= n(A \cup B \cup C) + n(D) - n((A \cup B \cup C) \cap D) \\ &= [n(A)+n(B)+n(C)- n(A \cap B) -n(A \cap C) -n(B \cap C)+n(A \cap B \cap C)] \\ &\quad + n(D) - n((A \cup B \cup C) \cap D) \\ &= n(A)+n(B)+n(C)- n(A \cap B) -n(A \cap C) -n(B \cap C)+n(A \cap B \cap C) \\ &\quad + n(D) - n((A \cap D) \cup (B \cap D) \cup (C \cap D)) \\ &= n(A)+n(B)+n(C)- n(A \cap B) -n(A \cap C) -n(B \cap C)+n(A \cap B \cap C) \\ &\quad + n(D) - [n(A \cap D) + n(B \cap D) + n(C \cap D) \\ &\quad - n(A \cap B \cap D) - n(A \cap C \cap D) - n(B \cap C \cap D) + n(A \cap B \cap C \cap D)] \\ &= n(A)+n(B)+n(C)+n(D) - n(A \cap B) -n(A \cap C) -n(A \cap D) \\ &\quad -n(B \cap C) -n(B \cap D) -n(C \cap D) + n(A \cap B \cap C) \\ &\quad + n(A \cap B \cap D) + n(A \cap C \cap D) + n(B \cap C \cap D) \\ &\quad - n(A \cap B \cap C \cap D) \end{aligned}

かなり複雑な数式になります。さすがに地道に計算するのはここまでで、何かもっとうまい方法を見付けたくなります。

k=4の全射の重複順列を写像から計算する

k=4ともなると、matplotlibライブラリにも描くためのサブパッケージはありませんし、ベン図では対応できそうもありません。こんなときは写像の出番です。

①全体集合

空室も許した制約なしの重複順列$k^n$を計算します。全体集合Uは7人を4部屋に割り振る重複順列になるので$4^7=16384$通りになります。

$n(U)=4^7=16384$

②1部屋以上空き部屋になる場合

1部屋以上が空きになるのは、図の左側のようにAが空きになるケースや、右のようにBが空きになるケースが考えられます。このほか、当然C,Dが空き部屋になる場合もあるので合計4ケースになります。

この4つのケースのうち1つ、図の左側のように7人をB, C, Dの3部屋に割り振るので、$3^7=2187$通りになります。同じように、集合B、C、Dも2187通りになるので、空室が出ない重複順列は全体集合 ($2187\times4=8748$)を差し引くことで計算することができます。

$ n(A)=n(B)=n(C) =n(D)= 3^7=2187$

$16384-2187\times4=7636$

一般論として、全射の計算をするため全体集合から加減するときには、次の式で計算します。

空室以外の部屋の組み合わせ（A,B,C,Dのうち3つ$\ _4 C_3 $）×組み合わせ毎の重複組み合わせの数($3^7$)

③2部屋以上が空きになる重複順列を足し戻す

図のようにAもBも空き部屋になる$A\cap B$のようなケースでは、①では1でカウントされていますが、②ではAとBでも二重に差し引かれてしまいます。この不都合を解消するために、いったん差し引いたものを足し戻す必要があります。同様に$A\cap C, A\cap D,B\cap C, B\cap D, C\cap D $を合わせて6ケース、つまり4つの部屋から2つを選ぶので$\ _4 C_2 $通りとなります。

その6ケースのうち1つ、$A\cap B$では C,Dの2部屋に7人が泊まることになるので$2^7=128$通りとなります。このため、6ケース×128=768通りを足し戻す必要があります。

$ n(A\cap B)=n(A\cap C)=n(A\cap D) =n(B\cap C) =n(B\cap D) =n(C\cap D)=n2^7=128$

$7636+128\times6=8404$

④3部屋以上が空きになる重複順列を再び差し引く

図のようにAもBもCも空き部屋$A\cap B\cap C$では③で重複して「足し戻し過ぎ」の状態にあるので、再び差し引く必要があります。

同様に$A\cap B\cap D, A\cap C\cap D, B\cap C\cap D $を合わせて4ケース、つまり4つの部屋から3つを選ぶので$\ _4 C_3 $通りとなります。

その4ケースのうち1つ、$A\cap B\cap C$では Dの1部屋に7人が泊まることになるので$1^7=1$通りとなります。このため、4ケース×1=4通りを再度、差し引く必要があります。

$ n(A\cap B\cap C)= n(A\cap B\cap D)= n(A\cap C\cap D)= n(B\cap C\cap D) =1^7=1$

$8404-1\times4=8400$

⑤4部屋以上が空きになる重複順列があれば差し引く

もし、AもBもCもDも空き部屋という重複順列があれば、引きすぎたものを再度足し戻す必要があります。もっともn=4の場合は0になるので、考える必要はありません。

$n(A\cap B\cap C\cap D)=0^7=0$

重複順列$4^5=16384$通りのうち、全射のものは8400通りになります。

$ n(A \cup B \cup C \cup D)$

$= n(A)+n(B)+n(C)+n(D)$

$-\{n(A \cap B)+n(A \cap C)+n(A \cap D)+n(B \cap C)+n(B \cap D)+n(C \cap D)\}$

$+\{n(A \cap B \cap C)+n(A \cap B \cap D)+n(A \cap C \cap D)+n(B \cap C \cap D)\}$

$-n(A \cap B \cap C \cap D)$

$n(U)=4^7=16384$

$n(A)=n(B)=n(C)=n(D)=3^7=2187$

$n(A\cap B)=n(A\cap C)=n(A\cap D)=n(B\cap C)=n(B\cap D)=n(C\cap D)=2^7=128$

$n(A\cap B\cap C)=n(A\cap B\cap D)=n(A\cap C\cap D)=n(B\cap C\cap D)=1^7=1$

$n(A\cap B\cap C\cap D)=0^7=0$

$n(A \cup B \cup C \cup D)=2187\times4-128\times 6+1\times 4-0=7984$

$n(\overline{A\cup B\cup C\cup D})=n(U)-n(A \cup B \cup C \cup D)=16384-7984=8400$

全射の場合の数の計算

ここまで複雑になると何度も引いたり足し戻したりしていて、本当に正しく計算されているか不安になります。そこで、全射の条件を満たさない2例について最終的に差し引かれるまでの流れを整理します。

(D, D, D, D, D, D, D)のようなに集合A,B,Cに当てはまるケース

①では制約なしの全体集合を計算しているので1でカウントされていますが、全射の条件を満たしていないの②～④の計算の結果、最終的に0に落ち着かせることが必要になります。

②では集合A,B,Cとして3回（$\ _3 C_1 $）差し引かれています。

③では$A\cap B$、$A\cap C$と$B\cap C$の3回（$\ _3 C_2 $）で足し戻されています。

④では$A\cap B\cap C$（$\ _3 C_3 $）で1回、再度差し引かれます。

よって1-3+3-1=0となり思った通りの結果になります。

ここで①は常に1なので$\ _3 C_0$と考えることができます。ところで、$\ _3 C_0 - \ _3 C_1+ \ _3 C_2 - \ _3 C_3 =1-3+3-1=0$となるのでうまく計算できたことがわかります。

(C, D, D, D, D, D, D)のようなに集合A,Bに当てはまるケース

①では制約なしの全体集合を計算しているので1でカウントされています。

②では、A,Bとして2回（$\ _2 C_1 $）差し引かれています。③では、$A\cap B$として足し戻されます。結果$\ _2 C_0 - \ _2 C_1+ \ _2 C_2=1-2+2=0$となりやはり正しく計算されています。

この考え方を拡張するとkがもっと大きくなっても、空き部屋の数をv、差し引く集合の重複数をiとすると、最終的に重複順列としてカウントされるのは、次の式で計算することができます。この式の値は$(x-1)^x$を二項定理にあてはめて展開し、$x=1$を代入して計算することができます。

空き部屋がいくつでカウントされるか

$\sum\limits_{i=0}^{x}(-1)^i\,\ _{x}C_i=\ _x C_0 -\ _x C_1+\ _x C_2-\ _x C_3+\cdots \pm\ _x C_x=0 $ただし$x=0$のときは1

vが奇数の時はマイナス、偶数の時はプラス

二項定理と重複順列の全射が思わぬところで結びつきました。

重複順列の全射の場合の数を計算する関数

最後に、全射の重複順列の場合の数の計算方法を一般化してみます。

部屋の数k=4に対して空き部屋の数をiとします。人数が6人なので、制約なしの場合、重複順列は$4^6$となります。

①の制約なしの場合、$k^n$となりますが、このとき空き部屋は0なのでi=0となります。これ以降の加減は表の通りになります。タイプには、代表的なものを示していますが、これを見ればそれぞれの組み合わせが$\ _k C_i$であることがわかります。また、k=0のときに＋、これ以降は交互にプラスとマイナスを繰り返すので$(-1)^i$であらわします。表を見ると数式は図の通りになります。

このような計算方法を包除原理（Inclusion-exclusion principle）といい、全射の計算で威力を発揮します。

これまで例で取り上げた重複順列について、前節の式をあてはめてみました。

重複組み合わせの全射の個数

$\sum\limits_{i=0}^{k}(-1)^i\,\ _{k} C_i(k-i)^n=\ _{k} C_0k^n-\ _{k} C_1(k-1)^n+\ _{k} C_2(k-2)^n- \cdots\pm\ _{n} C_n(n-n)^n $

上記の計算式を使い、全射の重複順列の個数を計算する関数を作成します。関数名は順列の全射という意味で、perm_surjection_countとし、引数はこれまでと同じようにk,nとします。また、関数を使い、これまで検討した3ケースについて計算し検証します。

# 全射の重複組み合わせの件数を計算

def perm_surjection_count(k, n):
sigma = 0
for i in range(k+1):
sigma += ((-1)**i) * comb(k,i) * (k-i)**n
return int(sigma)
print(perm_surjection_count(2, 5))
print(perm_surjection_count(3, 5))
print(perm_surjection_count(4, 7))

30
150
8400

4.　数式を当てはめます。

これまでに3つの例を挙げて計算してきましたが、結果は合致していることがわかります。計算式は正しそうですが、さらに詳しい証明も欲しくなります。このあたりはまた別の機械に譲ります。