全射の重複順列、包除原理

全射の重複順列について、写像とPythonを使って整理します。制約なしの場合に比べ全射となると複雑な計算が必要になります。この考え方は包除原理といい、とても奥深いものがあります。

重複順列を全射にする

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

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

問題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の数を2,3,4と増やしていきながら集合の考え方に沿って全射の重複順列の個数を計算し、最終的にkがどんなに大きくなっても対応できるよう一般化します。

2つの集合の演算

集合演算の種類とPythonでの計算

全射の計算をする前提として2つの集合演算の一般的な公式につき、具体例を使い整理します。まず、全体集合Uとして1から20までの整数を定義します。次に2つの集合を定義します。

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

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

これらの集合から、2つの集合についての集合演算を行います。

集合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個となります。

ここまでくるとこれは数えるのには少し骨が折れます。なお、一般に集合Aの個数はn(A)のように表現します。

操作	英語	演算子	記号	内包的記法
和集合	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\}$
補集合	(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
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によりインストールし、実行する際にはmatplotlibのpyplotとは別にインポートする必要があります。

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

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のみの領域　A - B = {2, 4, 8, 10, 14, 16, 20}

　'01': Bのみの領域　B - A = {9, 3, 15}

　'11': AとBの共通部分 A & B = {18, 12, 6}

このため、map関数を使い、各要素にstr関数を適用して文字列を要素とするmapオブジェクトに変換したのち文字列'\n'に対してjoinメソッドの引数に指定します。Joinメソッドはイテラブルを引数として取ることができます。なお、’\n’は改行を表す特殊文字で、要素を横に並べるために使用しています。

9. 補集合はvenn2には出力する機能が無いので、注釈のようにテキストとして表示します。

U - (A | B)= {1, 5, 7, 11, 13, 17, 19}

plt.text(x, y, ' '.text, ha='right', va='top')において

xはテキストの表示場所の水平方向の位置を示します。グラフはおおむね-0.8から0.8の範囲で描画されていますが、その中での座標を示します。Haはhorizontal alignment（水平方向の配置）の略で、rightとした場合、文字列の右端が0.6の場所に来ることを指名したいます。

同様に、垂直方向はyが-0.5から0.5の範囲の中での表示位置を示します。

Vaはvertical alignment（垂直方向の配置）の略でtopとした場合、文字列は0.5を上端として表示することを示します。

なお、グラフの表示位置はplt.xlim(-1, 1)plt.ylim(-1, 1)

のように明示的に示すこともできます。

4つの集合（A∩B, A-B, B-A, U-(A∪B)は

互いに素（重なりがない） pairwise disjoint
すべてを合わせると全体集合Uになるcollectively exhaustive"

となり分全体集合Uの完全な分割（partition）といわれています。要素xがUの任意の要素である場合、xは必ずこれら4つの集合のいずれか1つに属することになります。

なお、集合（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*}

このようにn(A \cup B)を計算する方法を包除原理といいます。

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

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が空室になる事象を集合Aとし、(B, B, B, B, B)が当てはまります。また、Bが空室になる事象を集合Bとし、(A, A, A, A, A)が当てはまります。そこで、AもBも空室になることはありえないもので$n(A\cap B) =\varnothing$となり、重複順列は$A \cup B=2$になります。したがって求める全射の重複順列は集合Aでも集合Bでもないものを数えればよいことになります。これは$\overline{A\cup B})$のようになり、個数は全体集合Uの個数32から$A\cup B$の2個を差し引いた30個になります。

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$

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

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}の15個、

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

5の倍数の集合C={5, 10, 15, 20, 25, 30}の5個

とします。

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

次に3つの集合の場合の複雑な例として集合A、集合Bの要素ではあるが集合Cの要素ではないような集合が考えられます。特にきまった名称はありませんが、ここではAとBの「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}$

これらの演算を行うと次のようになります。

3つの集合の演算

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 \cap\overline{B}\cap\overline{C}=A \setminus B \setminus C={2, 4, 8, 14, 16, 22, 26, 28}$

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

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

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

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

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

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

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

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}

この計算から、3つの集合の包除原理は次の式になります。

3つの集合の包除原理

$ 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)$

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

写像からみた包除原理

①全体集合

空室も許した制約なしの重複順列$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として実行します。

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

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

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

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

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

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)$

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$

③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(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がもっと大きくなっても、空き部屋の数を、差し引く集合の重複数をiとすると、最終的に重複順列としてカウントされるのは、次の式で計算することができます。

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

この式の値は$(x-1)^n$を二項定理にあてはめて展開し、$x=1$を代入して計算することができます。

$\displaystyle (1-x)^n=\sum_{k=0}^{n} \ _nC_k x^k=\ _nC_0x^0-\ _nC_1x^1+\ _n C_2x^2-\ _nC_3x^3+\cdots \ _n C _n x^n$

$x=1$を代入すると

$( 1-1)^n=\sum\limits_{k=0}^{n}\ _nC_k=\ _nC_0-\ _nC_1+\ _nC_2-\ _nC_3+\cdots\ _nC_n=0$

ただし、n=0のときは1になります。$0^0=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

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

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

最後に、全射の重複順列の場合の数の計算方法の一般化を試みます。部屋の数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_surjective_countとし、引数はこれまでと同じようにk,nとします。また、関数を使い、これまで検討した3ケースについて計算し検証します。

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

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

surjective(2, 5):   30
surjective(3, 5):  150
surjective(4, 7): 8400

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

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