包除原理　N,Kラベルあり　全射

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

重複順列を全射にする

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

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

Figure 1.13 では全学生が部屋 A 、または部屋 B に 集中している重複順列が見られます。宿の方がせっかく 2部屋を確保してくれたのに空き部屋にしてしまうのでは、品格を疑われてしまいます。そこで、少なくとも 1部屋に 1 人は泊まるような重複順列を考えます。全射とは、写像の終域のすべての要素が、定義域のある要素から対応づけられていることを要求する、すなわち、終域の中に、対応する定義域の要素が存在しない要素があってはならないのが全射（surjective）です。Figure 1.13 の左のような (A, A, B, A, B) は問題ありませんが、右のように (A, A, A, A, A) や、図にはありませんが、 (B, B, B , B, B) のような重複順列は対象になりません。

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

全射の重複順列を生成するため、ある写像が全射の要件を満たすかを判断する必要があります。そこで、全射の場合には単射とは異なり、写像だけではなく集合Kの要素がないと判断できませんそこで、引数として、写像をseq、全射であるかの判断の基準となる集合Kの要素をtargetとします。

cycle of (5, 3, 3, 4, 1, 3) = False
cycle of (5, 4, 2, 1, 3, 0) = True

2.　すべてのtargetの要素は、数なくとも一つはseqの要素と対応している必要があります。このため、taegtの要素をidxとして順次読み込みます。

3.　idx not in seqはidxがシーケンスseqの中に存在しなければTrueが返されます。

4.　3.がTrueになったときは全射ではなくなるのでFalseを返します。

5.　targetの全ての要素でseqとの対応が見られた場合、2行目のループから抜けるのでTrueを返します。

抽出

arbitrary_perm_list(2, 5) :count = 32
surjective_list_from_arbitrary(2, 5) : count = 30

4.　 generate_arbitrary_perm関数を使い重複順列を生成し、結果をarbitrary_perm_listに代入します。

7.　 is_surjective関数を使い、全射の要件を満たす写像のみをinjective_listに追加します。

この例では、制約なしの 32通りに対し、$(A, A, A, A, A)$、$(B, B, B, B, B)$ の 2通りが取り除かれ、30通りが全射の場合の数であることがわかりました。全射の条件を満たしているかは最後の 1 人にならないと判断できないので、 item を elm に追加するところを n-1 とそれ以前に分けて、最後の 1 人で全射かどうかを判断します。

この原理を使い、全射の重複分割を生成する関数を作成します。Code 1.18では、重複順列をすべて作ってから全射のものを絞り込んでいましたが、ここでは、n-1個目までは制限なしにリストを生成し、重複分割を生成し、最後の1つで全射の要件を満たさない写像のみを追加するようにします。このことにより少しではありますが、効率よく処理することが期待されます。

surjective_list_from_arbitrary== perm_surjective_list

3.　n-1個までは重複順列を同じように無条件にリストに追加します。

9.　最終的に戻り値にするリストをresultとして初期化します。

10. 最後のn個めは、is_surjective関数を使い全射の写像のみをresultに追加します。

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

Example 1.4 のように $k=2$ であれば、簡単に計算することができますが、数が増えるにしたがって計算が格段に複雑になります。そこで、 $k$ の数を 2,3,4 と増やしていきながら集合の考え方に沿って全射の重複順列の個数を計算し、最終的に $k$ がどんなに大きくなっても対応できるよう一般化します。そこで要素が 2 つの集合演算について確認したのち、全射の重複順列の個数の計算をします。

2 つの集合の演算

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

全体集合 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 ではない要素は、集合の補集合（complement）と呼び、$\setminus A$ でと表記します。$\setminus A=U-A$ の関係にあります。
• A でも B でもない集合は、全体集合 U の補集合といい、$\overline\{A \cup B \}=U\setminus (A \cup B)=\{1, 5, 7, 11, 13, 17, 19\}$ の 7 個となります。

また、集合 A の個数は $n(A)$ と表記します。

全体集合 $U$ を、1 から 20 までの整数からなる集合とし、次のように内包的に定義します。

$U = \{\, x \in \mathbb{Z} \mid 1 \leq x \leq 20 \,\}

次に、以下の 2 つの部分集合を定義します。

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

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

これらの集合に対して、以下のような集合演算が行えます。

積集合（intersection）：集合 $A$ と $B$ の共通部分は積集合と呼ばれ、$A \cap B = {6, 12, 18}$ の 3 個になります。これは 6 の倍数で構成されており、簡単に求めることができます。

差集合（difference）：集合 $A$ に含まれ、$B$ に含まれない要素全体の集合は差集合と呼ばれ、$A - B = A \setminus B = \{2, 4, 8, 10, 14, 16, 20\}$ の 7 個になります。同様に、$B - A = B \setminus A = \{3, 9, 15\}$ の 3 個です。

和集合（union）：集合 $A$ または $B$ のいずれか、あるいは両方に含まれる要素の集合は和集合と呼ばれ、$A \cup B = \{2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20\}$ の 13 個になります。

補集合（complement）：ある集合 $X$ に対する補集合とは、全体集合 $U$ の中で $X$ に属さない要素全体の集合を意味します。記号では $U \setminus X$ または $\overline{X}$ のように表されます。たとえば、$A$ の補集合は $U \setminus A = \{1, 3, 5, 7, 9, 11, 13, 15, 17, 19\}$ です。

和集合の補集合：$A$ または $B$ のいずれかに属する要素をまとめた和集合 $A \cup B$ に含まれない要素の集合は、$A$ にも $B$ にも含まれない要素全体を表し、次のように表します。

$\overline\{A \cup B\} = U \setminus (A \cup B) = \{1, 5, 7, 11, 13, 17, 19\}$

となります。記号 $\overline{A \cup B}$ は、和集合の補集合を簡潔に表す記法としてよく用いられます。

また、集合 $A$ の要素数は $n(A)$ のように表記します。

Pythonによる集演算とベン図の描画

Python による集合演算

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

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))と定義します。

2つの集合のベン図

集合の関係を視覚的に理解するには、ベン図（Venn diagram）視覚的に理解しやすくなります。

集合の関係は、ベン図（Venn diagram）を用いることでベン図は、Pythonのグラフ描画ライブラリである matplotlib に依存する独立したベン図描画専用のパッケージである matplotlib-venn を使用することで描画できます このうちvenn2 関数は、2つの集合のベン図を描画する関数として提供されています。

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

6.　ベン図の各領域へのテキスト追加: get_label_by_id メソッドを使用して、ベン図の特定の領域にアクセスし、set_text で内容を設定しています。get_label_by_id メソッドの引数であるID は1桁目の1は1番目の集合Aの要素を表示するという意味です。同様に2桁目の0は2番目の集合Bの要素ではないことを示します。したがって、それぞれの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)$ と定義します。

このように $n(A \cup B)$ を計算する方法を包除原理（Inclusion-exclusion principle）といいます。

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となり、正しく計算できたことがわかります。

Example 1.4への適用

全射の重複順列の個数を計算します。はじめに全体集合$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個になります。

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

3つの集合の演算

写像による計算

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

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

エラー! 参照元が見つかりません。で作成した generate_surjective_perm関数を使い、重複順列を生成したのち個数を数え、制約なしの重複縦列と比べます。

generate_arbitrary_perm(3, 5) = 243 
generate_surjective_perm  (3, 5) = 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}$

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

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つの集合の関係を見るためにベン図を描いてみます。

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

6.　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つ以上つなげた場合は、計算する順序によらず同じ結果になります。

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

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

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

ここでは結合法則と積集合の冪等法則を使って次のような変形が必要になります。

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

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

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

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

写像からみた包除原理

全射ではない写像では、定義域対応していない終域の要素が存在します。このような要素を未対応要素（non-attained element）と呼び、その数を未対応要素数（defect）と呼びます。そので、未対応要素数defectをキーワードに包除原理による場合の数を計算します。

①全体集合

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

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

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

③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)の３つあります。

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

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

ベン図を課題に適用する

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

4つの集合の演算から一般化する

関数による計算

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

arbitrary =  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つの集合の包除原理を計算する

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

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

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

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

k=4ともなると、matplotlibライブラリにも描くためのサブパッケージもなく、そもそも複雑すぎてベン図では対応できません。こんなときは写像の出番です。①で重複順列を計算し②から④で全射の要件を満たさない重複順列を

①全体集合

空室を許容する制約なし写像である重複順列$k^n$を計算します。全体集合Uは7人を4部屋に割り振る重複順列になるので$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$)を差し引くことで計算することができます。

③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通りを足し戻す必要があります。

④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通りを再び差し引く必要があります。

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

もし、AもBもCもDも空き部屋という重複順列があれば、引きすぎたものを再度足し戻す必要があります。もっともn=4の場合は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$

全射の場合の数の計算

n=4にもなると何度も加減を繰り返すので、本当に正しく計算されているか不安になります。そこで、全射の条件を満たさない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\,{}_xC_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)^d=\sum_{i=0}^{d} {}_dC_i x^i={}_dC_0x^0-{}_dC_1x^1+{}_d C_2x^2-{}_dC_3x^3+\cdots {}_d C _d x^d$

$x=1$を代入すると

$( 1-1)^d=\sum\limits_{i=0}^{d}{}_dC_i={}_dC_0-{}_dC_1+{}_dC_2-{}_dC_3+\cdots{}_dC_d=0$ $

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

この場合は空き部屋がでないので、最終的に1でカウントされます。これを式に当てはめると0^0=_0C_0=0!/(0!\times0!)=1となります。整数の0乗は1というのはわかるとして$0^0=1$というのは違和感を感じますが、この例を見ると確かに頷けます。

まとめると次のようになります。

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

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

最後に、全射の重複順列の場合の数の計算方法の一般化を試みます。部屋の数k=4に対して空き部屋の数をiとします。人数が6人なので、制約なしの場合、重複順列は$4^6$となります。

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

表を見ると数式は図の通りになります。

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

これまで例で取り上げた重複順列を一般化すると次のようになります。

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

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

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

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

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

3.　 n-2 つまり最後より 1 つ手前までの要素は重複順列と同様に、perm_list に重複順列を生成します。

10. 最後の要素については、これまでに作成した重複順列が全射の要件を満たす new_elm のみを要素を perm_list に追加します。なお 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:

perm_list.append(new_elm)

else:

if set(k_list).issubset(new_elm):

perm_list.append(new_elm)

全射の重複順列を集合(set)に変換すると $\{A, B\}$ と表記し、 k_list の個数と等しくなります。これに対して全射でない $(A, A, A, A, A)$ は $\{A\}$ となり、k_list の個数よりも小さくなります。このように、全射の判断をするために、作成した配列を集合に変換し、その個数と要素の種類を比較するのが定石です。

上記のプログラムは、最後1つの要素を追加する際に全射か否かを判断するis_surjective関数を適用し、全射の写像を抽出しました。この方法単純ではありますが、写像を作成する過程で、この後全射の要件を満たすことができないことがあきあらかな作成過程も最後まで残ってしまうので、

全射の重複分割を生成するにあたり、

例えばn=7,k=4で、5回目のループで()となった時点で、残り2回のループでBCDの3つをすべて選択することはできないので、全射の写像として完成させることができなくなります。このため、この時点でリストに追加しないようにします。

perm_surjective_with_constraint(4, 7) = 8400
perm_surjective_list_by_filtering == perm_surjective_with_constraint

9.　 k - len(set(new_elm)は全射の要件を満たすために、何種類k_listから選べばよいかを示しています。一方n - i – 1は、あと何回ループを回すのか示しています。このため前者が後者以下の場合は全射の写像として完成させることができるので、候補としてnext_permに追加します。また、前者が後者より大きくなった時点で候補から外れるのでnext_permには追加しません。