写像で重複順列、順列を考える

写像の考え方とPythonを使って重複順列、順列について、整理します。

制約なしの重複順列

写像で見る重複順列

重複順列(product sequence with repetition)について理解するため考えます。

問題1

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

重複順列など場合の数で写像を使う場合、慣習的に定義域を集合N、終域の集合をKとします。集合Nから集合Kへの対応を図にします。また、ここから数字0,1,2,3,4は学生、A,Bは部屋を表すこととします。左の図は、0,1,3はA、2,4はBに泊まることを表しています。いっぽう、右の図は全員がAに泊まり、Bには誰も泊まらないことを示しています。

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

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

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

1つの集合Kの要素に対して複数の集合Nが対応すること、つまり相部屋OKということです。
集合Kの要素の中に対応する要素がないこと、つまり空き部屋OKということです。

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

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

pythonではitertoolsモジュールのproduct関数を使うと出力することができます。product関数では次の引数を取ります。

変数	内容
k_list	終域の要素を渡します。例の場合は部屋の種類A,Bをタプルで指定します。
Repeat	定義域Nの数を渡します。ここでは、人数が5人なのでrepeat=5とします。

戻り値として0,1,・・・が選んだ部屋AかBかを表す一覧が生成されます。この関数の戻り値はイテレータという特殊な形式になるので注意が必要です。

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

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

unrisricted= 32
[('A', 'A', 'A', 'A', 'A'),
 ('A', 'A', 'A', 'A', 'B'),
 ('A', 'A', 'A', 'B', 'A'),
 ('A', 'A', 'A', 'B', 'B'),
 ('A', 'A', 'B', 'A', 'A'),
　　　　・
　　　　・
('B', 'B', 'B', 'B', 'B')]

1.　 itertoolsモジュールはPythonの標準ライブラリ1つなので、Pythonがインストールされていれば使うことができます。ただし、ビルドイン関数ではないので、使用する都度、importする必要があります。

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

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

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

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

product関数はデカルト積を求めるもので、目的外利用のような気もしますが、結果が出ればOKということで進めます。

生成方法の考え方

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

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$

重複順列を生成する関数

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

n回forループを回し、リスト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),・・のように推移します。

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

プログラムの中で、タプルelmは作成途中の1つ1つの重複組み合わせを、itemは各人がどの部屋に入るかを表します。

関数の作成

前節の考え方に沿って、重複順列を生成するPythonの関数を作成します。関数名は制約なし(unristricted)の順列(permutation)という意味でperm_unristricted_funcとし、itertoolsと同様にk_listとnの2つの引数として渡します。

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

def perm_unristricted_func(k_list, n):
array = [()]
for cnt 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_unristricted_list = perm_unristricted_func(k_list, n)
print('unristricted=',len(perm_unristricted_list))
pprint.pprint(perm_unristricted_list)

unristricted= 32
[('A', 'A', 'A', 'A', 'A'),
 ('A', 'A', 'A', 'A', 'B'),
 ('A', 'A', 'A', 'B', 'A'),
 ('A', 'A', 'A', 'B', 'B'),
 ('A', 'A', 'B', 'A', 'A'),
 ('A', 'A', 'B', 'A', 'B'),
 ・
・
('B', 'B', 'B', 'B', 'A'),
 ('B', 'B', 'B', 'B', 'B')]

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として取り出したitemを右側にitemを結合して新しいタプルとし、arrayに追加します。要素が1つだけのタプルは(item,)のように要素にカンマを付けます。

このことにより、arrayが、k_listからなる長さnの順列のリストとなり戻り値とします。最終的にproduct関数と同じ結果になります。

個室にする場合　～　順列

写像からみた順列

場合の数の中で最も基本的な順列を写像の視点から見るために、次の問題を考えます。

問題2

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

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

pythonの標準モジュールによる順列の生成と場合の数の計算

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

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

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

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

injective= 60
[('A', 'B', 'C'),
 ('A', 'B', 'D'),
 ('A', 'B', 'E'),

('E', 'D', 'A'),
 ('E', 'D', 'B'),
 ('E', 'D', 'C')]

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

場合の数は$5\times4\times3=60$となります。

scipyライブラリのperm関数による順列の場合の数の計算

scipyライブラリのperm関数により順列の場合の数を計算することができます。このほか新しいバージョンではmathモジュールにもperm関数が追加されました。

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

from scipy.special import perm
import math
print(f'scipy.specialパッケージのperm関数：{perm(len(k_list), n)}')
print(f'mathモジュールのperm関数：{math.perm(len(k_list), n)}')

scipyライブラリのperm関数：60.0
mathモジュールのperm関数：60

1.　scipyライブラリは関数単位でimportすることが多いようです。

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

3.　mathモジュールのperm関数は整数で組み合わせが返されます。ただし、pythonの v3.8以降でないと使うことはできません。

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

順列の個数の計算

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

$\displaystyle \ _k P_n =\;\overbrace {k(k-1)(k-2)・・・(k-n+1) \quad}^{n個}= \frac{k!}{(k-n)!}$

順列を生成する関数を作成

順列を生成する関数を自作します。順列は単射になるのでperm_injective_funcという関数名にします。重複順列を生成するperm_unristricted_func関数とほぼ同じ流れになりますが、単射にするため、itemをelmに結合する時点で先客がいる場合候補から外れるのでarrayに追加しないようにします。

順列のリストを出力する

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 = ['A', 'B', 'C', 'D', 'E']
n = 3
perm_injective_list = perm_injective_func(k_list, n)
print('unristricted = ',len(k_list)**n,'injection = ',len(perm_injective_list))
pprint.pprint(perm_injective_list)

unristricted =  125 injection =  60
[('A', 'B', 'C'),
 ('A', 'B', 'D'),
 ('A', 'B', 'E'),
 ('A', 'C', 'B'),
 ('A', 'C', 'D'),
 ('A', 'C', 'E'),
 ('A', 'D', 'B'),
 ('A', 'D', 'C'),
 ('A', 'D', 'E'),
・
・
('E', 'D', 'C')]

8.　if item not in elmの条件文で、入ろうとした部屋に誰かが入っていないかを判断します。

9.　8.により単射の要件を満たす可能性のある場合に限り、elmにitemを結合しarrayに追加します。

perm_injective_func関数では、学生1人1人についてリストに追加するときに単射の判断をしていますが、最後の1人のところで判断する方法も考えられます。この場合、8行目の判断の回数が少なくてすむ代わりに、終了直前までarrayに単射の要件を満たさないタプルも候補として残しておく必要があるので、どちらの効率が良いか一概には言えません。

空き部屋を出さない全射

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

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

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

問題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に追加するところを最後とそれ以前に分けて、最後の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:
new_elm = elm + (item,)
if cnt < n-1:
array.append(new_elm)
else:
if len(set(new_elm)) == len(k_list):
array.append(new_elm )
return array
n = 5
k_list= ['A', 'B']
perm_surjective_list = perm_surjective_func(k_list, n)
print('unristricted = ',len(k_list)**n,'surjective = ',len(perm_surjective_list))
pprint.pprint(perm_surjective_list)

unristricted =  32 surjective =  30
[('A', 'A', 'A', 'A', 'B'),
 ('A', 'A', 'A', 'B', 'A'),
 ('A', 'A', 'A', 'B', 'B'),
 ('A', 'A', 'B', 'A', 'A'),
 ('A', 'A', 'B', 'A', 'B'),
 ('A', 'A', 'B', 'B', 'A'),
・
・
 ('B', 'B', 'B', 'A', 'B'),
 ('B', 'B', 'B', 'B', 'A')]

8.　作成途中の重複順列に今回追加するitemを結合して、new_elmというタプルとして仮置きします。

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

11. 最後の1人は9.にあてはまらないので、12.で作成した重複順列が全射の要件を満たすnew_elmのみを要素をarrayに追加します。

全射の重複順列を集合(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の場合

全射の重複順列を生成する関数を作成しましたが、場合の数を計算するだけであれば、集合論の考え方を使い整理することができます。ここでのコツはAの間が空いてしまう事象をA、Bの間が空いてしまう事象をB、というように空室になる事象を考えることです。

集合で考えると、全事象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('unristricted = ',len(k_list)**n,'surjection = ',len(perm_surjective_list))
pprint.pprint(perm_surjective_list)

unristricted =  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'),

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

①全体集合

空室も許した制約なしの重複順列$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$

以上の関係はBENN図にすると少し違った視点で見ることができ、わかりやすくなるかもしれません。

全射の組み合わせの数をベン図で表現

import matplotlib.pyplot as plt
from matplotlib_venn import venn3
a = set()
b = set()
c = set()
perm_unristricted_list = perm_unristricted_func(k_list, n)
for elm in perm_unristricted_list:
if 'A' not in elm:
a.add(elm)
if 'B' not in elm:
b.add(elm)
if 'C' not in elm:
c.add(elm)
fig ,ax = plt.subplots()
ax.set_title('U=243 surjection N=5, K=3')
venn3(subsets=[a, b, c],set_labels=('A_vacant','B_vacant','C_vacant'))
fig.set_facecolor('#e6f2ff')
plt.show()

図のような出力がされます。赤で示した。

1. ベン図はmatplotlibを使って主力します。

2.　3つの集合のベン図はmatplotlib_vennのvenn3を使います。matplotlib_venn はmatplotlibとは別にインストールする必要があるので、使用するときに1回だけ次のコマンドを実行する必要があります。

pip install matplotlib_venn

3～5. 集合A,B,Cの補集合を集合a,b,cで初期します。pythonでは集合の初期化はset()関数を使います。

7. perm_unristricted_listからelmとして制約なしの重複順列を1つ1つ読み込みます。

8.　7の中にAが存在しないかを判断し、存在しない場合は集合Aに当てはまるのでaに追加します。集合の場合はappendメソッドではなくaddメソッドを使います。

16. venn図を描画します。このとき、集合A,B,Cは空き室となるという意味でlabelはvacantを付けます。

17. set_facecolorメソッドにより背景に色を付けることができます。

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

$n(A)= n(B) = n(C) =32$

$n(A) –{n(A \cap B)+ n(A \cap C)}=32-(1+1)=30$

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('unristricted = ',len(k_list)**n,'surjection = ',len(perm_surjective_list))
pprint.pprint(perm_surjective_list)

unristricted =  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')]

k=4ともなるとベン図では対応できそうもありません。こんなときに写像の考え方が役立ちます。

①全体集合

空室も許した制約なしの重複順列$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通りを足し戻す必要があります。

$ 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$では③では重複して引き戻す、つまり足されすぎているので、再び差し引く必要があります。このような、ケースはABCDの4部屋から3部屋選ぶことになるので$\ _4 C_3 $通りとなります。その各々について、$1^7$通りを差し引きます。

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

包除理論による全射の場合の数の計算

ここまで複雑になると何度も引いたり足し戻したりしていて、本当に正しく計算されているか不安になります。そこで、いくつかを例にとり検証します。まず、(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$となるので、最後は$\ _3 C_3=1$となり完結します。

もう一つ、まず、(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)^v$を二項定理にあてはめて展開し、$x=1$を代入して計算することができます。

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

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

最終的にvが奇数の場合には1つだけマイナス、偶数の場合は1つだけプラスすることで、全射でないケースを0個としてカウントすることができます。

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

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

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

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

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

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

$\sum\limits_{i=0}^{k}(-1)^i\,\ _{k} C_i(k-i)^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

これまでに3つの例を挙げて計算してきましたが、結果は合致していることがわかります。

全単射

最後に出席番号0から4の5人が、AからEまでの5部屋、つまり空き部屋が出ないように分けるとしたときの場合の数を計算します。つまり全射と単射の両方を満たす全単射(bijective)といいます。写像を図であらわすと次の通りです。

perm_injective_func関数を使いperm_injective_listを、perm_surjective_func関数を使いperm_surjective_listをそれぞれ作成し比較します。件数が多いので比較をした結果のみを表示します。また、順列と全射による場合の数もそれぞれ行い、結果を比較します。

単射としての順列と全射の重複順列が等しいこと

k_list = ['A', 'B', 'C', 'D', 'E']
n = 5
perm_injective_list = perm_injective_func(k_list, n)
perm_surjective_list = perm_surjective_func(k_list, n)
perm_surjective_list== perm_injective_list, len(perm_surjective_list)

(True, 120)

生成したリストも等しくなり、当然のことながら件数も120通りとなり等しいことがわかります。

全単射での件数の比較

$\ _{5} C_0 5^5-\ _{5} C_1 4^5+\ _{5} C_2 3^5-\ _{5} C_3 2^5+\ _{5} C_4 1^5-\ _{5} C_5 0^5$

$=1\times5^5-5\times4^5+10\times3^3-10\times2^2+5\times1^5-1\times0^5=120$

$5!=120$

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

なぜ、全射の式と単射の式の結果が異なるかを、直感的には次のように考えられます。

まとめ

これまで、区別のある学生を区別のある部屋に割り振ることを題材に写像の考え方を見てきました。重複順列、順列を写像という視点でまとめてみました。この際に、特に制限の場合、全射、単射の3つのパターンがあることを見てきました。個数は次の式により計算することができます。

制約なし	単射	全射
重複順列	順列	包除理論による全射
$_k\prod{_n}=k^n$	$\ _k P_n =\frac{k!}{(k-n)!}$	$\sum\limits_{i=0}^{k}(-1)^i\,\ _{k} C_i(k-i)^n$