スターリング数の２タイプ
１．集合分割の数
このワークシートはMath by Codeの一部です。
ｎ個の要素を重複なくｋ組に分割する数が第２種のスターリング数。
＜特別な場合を考えよう＞
いきなり一般的に考えると難しそうですが、
極端なパターンでは公式がすぐにできますよ。
たとえば、S2(n,k)とかくとしたら、S2(4,3)=6です。
U={a,b,c,d}を３つに分けるとき、４＝２＋１＋１なので、4C2=6から計算できるからです。
4個の要素から２個選ぶと、３組の残り２組は自動的に決まりすね。
一般化しよう。
S2(n,n-1)=nC2
要素数よりも１個少ない部分集合に分割するには１個だけ、２個組にすればいいね。
その２個組の要素を決めてしまえば、残りは１個ずつだから決まる。
だから、nC2と同じになる。
またもっと、簡単な法則がいくつもある。
S2(n,n)=1
これは、n=kのときだから、個数と組数が同じなら、１個で１組なので１通りが自動的に決まるからね。
S2(n,nより大）＝０
組数が個数を超えることは不可能だから、０通りだね。
S2(n,1)=1
これも極端だ。ちょうど１組作るということは、１通りしかないね。
＜１つ手前から規則性をみつける＞
ｎ個のｋ組ができる前のn-1個のときから始めよう。１個の追加をどうするかを考えてみよう。
n-1個でk組になっていたら、組数を維持するためにどこかの組にいれるから、ｋ通り選べる。
n-1個でk-1組になっていたら、組数をふやすために、１個で単独組にするから、１倍になる。
ということは、
S2(n,k)= S2(n-1,k-1)+S2(n-1,k) * k
という漸化式になるね。
質問：第２種のスターリング数S2(n,k)をもとめるコードはどうしたら作れますか。
特別なケースをif文で返し、一般の場合だけ漸化式を使う、再帰関数を作ろう。
[IN]Python
#===============================
def S2(n,k):
if n < k :
return 0
elif n == k:
return 1
else:
if k==1:
return 1
if n == k + 1:
return n*(n-1)//2
else:
return S2(n-1,k-1) + k * S2(n-1,k)
print("n\\k",end="")
for j in range(1,11):
res = "{:>6}".format(j)
print(res, end=",")
print(res, "{:>6}".format("B(n)"),end="")
print()
for i in range(1,12):
print("{:>2}".format(i),end=":")
bell=0
for j in range(1,12):
ans = S2(i,j)
bell += ans
res = "{:>6}".format(ans)
print(res, end=",")
print("{:>6}".format(bell))
print()
#===================================
[OUT]
n\k 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10 B(n)
1: 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1
2: 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2
3: 1, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 5
4: 1, 7, 6, 1, 0, 0, 0, 0, 0, 0, 0, 15
5: 1, 15, 25, 10, 1, 0, 0, 0, 0, 0, 0, 52
6: 1, 31, 90, 65, 15, 1, 0, 0, 0, 0, 0, 203
7: 1, 63, 301, 350, 140, 21, 1, 0, 0, 0, 0, 877
8: 1, 127, 966, 1701, 1050, 266, 28, 1, 0, 0, 0, 4140
9: 1, 255, 3025, 7770, 6951, 2646, 462, 36, 1, 0, 0, 21147
10: 1, 511, 9330, 34105, 42525, 22827, 5880, 750, 45, 1, 0,115975
11: 1, 1023, 28501,145750,246730,179487, 63987, 11880, 1155, 55, 1,678570
ちなみに、この表の各行はｎ個の要素のあらゆる分割方法をならべてあるから、これの合計してみた。
これは、ｎ個の要素を組数を指定しない分割数になるね。ｎ個の分割総数はベル数B(n)と言われる。
第２種スターリング数の一般項
ここまでは、極端な場合や隣接するつながりを考えて動的に考えてきたね。
では、静的に考えて一般化できないだろうか。
そもそも、ｋ個の組の順序を問わないことで難しくなってしまっているともいえる。
だから、ｋ個を番号のついた箱のように考えて、区別をつけて調べることにしよう。
言い換えるとn人の男の集合Nから、k人の女の集合Kへの全射の数を考えてみる。
・Nの男がKの女を自由に選べば、ｎ人のどの男もｋ通り選べるので、kｎ通りの写像があるね。
全射の数を出すにはどうしたらよいでしょう？
写像の集合から、男に選ばれない女の数がいるものを取り除けばよいね。
・PIE（包除原理）を思い出そう。
PIEは、どれかに入ることの否定の求め方だった。
オアの否定の個数は、全体からアンドする要素が増えるごとにー＋を交互にひいて求めることだった。
全射の写像数＝全体写像数ー（女子のだれかが選ばれない）
＝全体写像数ー（１人あぶれ写像）＋（２人あぶれ写像）ー（３人あぶれ写像）+…
のようになるはずだ。
ｋ人の女子をf1,f2,.....fkとする。
f1があぶれるのは男がf1以外から選ぶ(k-1)n通りある。１人の女子はkC1あるから、
1人は選ばれない写像数はkC1(k-1)n。
女子1人fiが選ばれない写像をF1 , 女子３人fi,fj,fkが選ばれない写像をF3のようにかき、
写像の個数を| |でかこむと次のようなきれいな式ができる。
|F1|=kC1(k-1)n。|F2|=kC2(k-2)n。・・・|Fi|=kCi(k-i)n・・・・|Fk|=kCk(k-k)n。
だから、全射の写像数＝kｎ - kC1(k-1)n + kC2(k-2)n ....+(-1)nkCk(k-k)n
この全射は、ｋ人の女を区別しているから、この区別をｋ！で割ってキャンセルすればよい。
そうすると、同じ数になった女は区別できないので、この数は第２種のスターリング数になるでしょう。
S2(n,k)=1/k! (kｎ - kC1(k-1)n + kC2(k-2)n ....+(-1)nkCk(k-k)n )
質問：第２種のスターリング数の一般項をもとめるにはどうしたらいいですか。
コードを作って計算して確かめることもできるね。
＜数式処理（CAS)はすばらしい＞
上のアプリのように
geobebraの数式処理（CAS)
に数式をほぼそのまま入れる方法もあるね。
PIEのx番目の項に符号を交互につけて(-1)x nCr(k,x) (k-x)n
をΣ計算しよう。
x=1からkまで変化させたSumなので、sum((-1)x nCr(k,x) (k-x)n, x, 1, k)を全写像knにたして、
k!つまり、nPr(k,k)で割ると、公式S(n,k)が作れるね。
n=4, k=2に値を入れて求めるには、S(n,k)の行を選んで、メニューアイコン
を選び、
左側のx, n, kに対して、nの右ワクに4, kの右ワクに2を入れるとsubstitute; のあとに計算結果が表示される。通常の数式のメニューでは、行の削除は削除ですが、数式処理では行の消去を選びます。
慣れるとかなり便利になると思います。
すばらしいです。
pythonのmathパッケージで階乗計算ができるから、それから組み合わせを求められるね。
#S2(n,k)=1/k! (k^ｎ - kC1(k-1)^n + kC2(k-2)^n ....+(-1)^nkCk(k-k)^n )
from math import factorial
def combi(n, r):
return factorial(n) // (factorial(n - r) * factorial(r))
def S2gene(n,k):
if n < k :
return ""
else:
return (k**n + sum([(-1)**x * combi(k,x) * (k-x)**n for x in range(1,k+1)]))//factorial(k)
print("n\\k",end="")
for j in range(1,12):
res = "{:>6}".format(j)
print(res, end=",")
print()
for i in range(1,12):
print("{:>2}".format(i),end=":")
for j in range(1,12):
res = "{:>6}".format(S2gene(i,j))
print(res, end=",")
print()
#==================================
[OUT]
n\k 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
1: 1, , , , , , , , , , ,
2: 1, 1, , , , , , , , , ,
3: 1, 3, 1, , , , , , , , ,
4: 1, 7, 6, 1, , , , , , , ,
5: 1, 15, 25, 10, 1, , , , , , ,
6: 1, 31, 90, 65, 15, 1, , , , , ,
7: 1, 63, 301, 350, 140, 21, 1, , , , ,
8: 1, 127, 966, 1701, 1050, 266, 28, 1, , , ,
9: 1, 255, 3025, 7770, 6951, 2646, 462, 36, 1, , ,
10: 1, 511, 9330, 34105, 42525, 22827, 5880, 750, 45, 1, ,
11: 1, 1023, 28501,145750,246730,179487, 63987, 11880, 1155, 55, 1,
を選び、
左側のx, n, kに対して、nの右ワクに4, kの右ワクに2を入れるとsubstitute; のあとに計算結果が表示される。通常の数式のメニューでは、行の削除は削除ですが、数式処理では行の消去を選びます。
慣れるとかなり便利になると思います。
すばらしいです。
pythonのmathパッケージで階乗計算ができるから、それから組み合わせを求められるね。
#S2(n,k)=1/k! (k^ｎ - kC1(k-1)^n + kC2(k-2)^n ....+(-1)^nkCk(k-k)^n )
from math import factorial
def combi(n, r):
return factorial(n) // (factorial(n - r) * factorial(r))
def S2gene(n,k):
if n < k :
return ""
else:
return (k**n + sum([(-1)**x * combi(k,x) * (k-x)**n for x in range(1,k+1)]))//factorial(k)
print("n\\k",end="")
for j in range(1,12):
res = "{:>6}".format(j)
print(res, end=",")
print()
for i in range(1,12):
print("{:>2}".format(i),end=":")
for j in range(1,12):
res = "{:>6}".format(S2gene(i,j))
print(res, end=",")
print()
#==================================
[OUT]
n\k 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
1: 1, , , , , , , , , , ,
2: 1, 1, , , , , , , , , ,
3: 1, 3, 1, , , , , , , , ,
4: 1, 7, 6, 1, , , , , , , ,
5: 1, 15, 25, 10, 1, , , , , , ,
6: 1, 31, 90, 65, 15, 1, , , , , ,
7: 1, 63, 301, 350, 140, 21, 1, , , , ,
8: 1, 127, 966, 1701, 1050, 266, 28, 1, , , ,
9: 1, 255, 3025, 7770, 6951, 2646, 462, 36, 1, , ,
10: 1, 511, 9330, 34105, 42525, 22827, 5880, 750, 45, 1, ,
11: 1, 1023, 28501,145750,246730,179487, 63987, 11880, 1155, 55, 1,
２．置換を巡回置換に分解する数
要素を順番をつけて並べたものや並べ方の数を順列といいました。
要素の順番を入れ替えるのを操作としてとらえることを置換といいます。
とくに要素を順送りで入れ替える、サイクルで入れ替えることを巡回置換といいます。
巡回置換は３つ以上だとわかりやすいのですが、
２つの交換、互換も、１つを自分と入れ替える？ことも特別に巡回置換と言ってしまいましょう。
質問：そう決めたときに、要素数Nの巡回置換の数はいくつあるかを考えてみましょう。
１要素でも、２要素でも１通りです。
３要素ならば、１番の行き先が２番になるか、３番になるかで２通りありますね。
４要素ならば、１番の行き先は残り４−１＝３つの番号のどれかです。
その行き先の行き先は残りの４−２＝２つの番号のどれかです。最後の行き先は自動で決まります。
だから、３×２×１になりますね。
もうおわかりのように、
N個の巡回置換C(N)=(N-1)!
になるのです。
さて、これを準備として、第１種のスターリング数を決めます。
第２種はN個をK組にわける数でした。
第１種はN個をK組の巡回置換にわける数です。
だから、ただ分けるのでなく、組の中の巡回の仕方まで入ってくるのですね。
＜第２種を利用して第１種も考えてみよう＞
第２種では、極端な場合と漸化式からしくみをとらえました。
第１種でもそうしてみよう。
第１種のスターリング数をS1(n,k)とします。
S2(n,n-1)=nC2でした。この分け方では、１組だけ２個で、あとは１個です。どの組の巡回置換も１です。
だから、S1(n,n-1)=nC2
S2(n,n)=1でした。1個ずつにしたら巡回置換はみな１です。
S1(n,n)=1。
S2(n,nより大）＝０これはS1でも同じです。
S2(n,1)=1。これはn個のかたまりを１つの巡回置換にしますから、C(n)と同じですね。
S1(n,1)=C(n)です。
いよいよ、ｎ個のｋ組ができる前のn-1個のときから始めよう。１個の追加をどうするかを考えてみよう。
・n-1個でk組になっていたら、組数を維持するためにどこかの組にいれるから、ｋ通り選べるけど、行き先のサイズで巡回置換が変わってしまうような気がします。冷静に考えるとそうではなく、追加した１個の行き先は追加前のn-1個のどれかになるだけです。それ以外の行き先の数に変化はありません。
・n-1個でk-1組になっていたら、組数をふやすために、１個で単独組にするから、１倍になる。
ということは、
S2(n,k)= S2(n-1,k-1)+S2(n-1,k) * (n-1)
という漸化式になるね。
質問：これらの規則を利用して、第1種のスターリング数S1(n,k)をもとめるコードはどうしたら作れますか。
from functools import cache
from math import factorial
@cache
def C(n):
return factorial(n-1)
def S1(n,k):
if n < k :
return 0
elif n == k:
return 1
else:
if k==1:
return C(n)
if n == k + 1:
return n*(n-1)//2
else:
return S1(n-1,k-1) + (n-1) * S1(n-1,k)
print("n\\k",end="")
for j in range(1,11):
res = "{:>6}".format(j)
print(res, end=",")
print()
for i in range(1,8):
print("{:>2}".format(i),end=":")
for j in range(1,11):
res = "{:>6}".format(S1(i,j))
print(res, end=",")
print()
n\k 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
1: 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2: 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
3: 2, 3, 1, 0, 0, 0, 0, 0, 0, 0,
4: 6, 11, 6, 1, 0, 0, 0, 0, 0, 0,
5: 24, 50, 35, 10, 1, 0, 0, 0, 0, 0,
6: 120, 274, 225, 85, 15, 1, 0, 0, 0, 0,
7: 720, 1764, 1624, 735, 175, 21, 1, 0, 0, 0,
３．スターリング数の見える化
スターリング数は
組み合わせ論としてはおもしろいテーマだけど、
数字だけでは、意味を忘れてしまいかねない。
意味を見える化すると、イメージがはっきりするね。
質問：第２種スターリング数を視覚化するにはどうしたらよいですか。
スターリング数は集合を分割する数だった。
どう分割しているかがわかるように、ｎ個の集合としては、１からｎまでの数を文字にする。
ｋ個の組にしては、分割した文字列をリストにしたものを１組としてしよう。
すると、ｋ組というのはリストがｋ個あつまったもの、リストのリストを作ってみよう。
ｎを入力すると、１からｎまでの数を文字にしたｎ要素のリストを作ろう。
それが、
source = list(map(lambda x:str(x),list(range(1,n+1))))
でできる。
見慣れないと意味不明な感じですが、関数の入れ子として内側から外側へと、
合成関数のように読み取りましょう。
やっていることは単純。
・range(1,n+1)は1以上n以下の範囲で、list()でかこんでリストにする。
・それをラムダを使って、各要素ｘをstr(x)で数値を数字に写像mapしたものをlistにしてます。
・結果はsource=['1','2',.....,'n']です。
そのあとのnとkの関係性による。変形は再帰関数の手法を使って考えましょう。
１個に決まる場合は[[ １つの文字列]]、n個にバラける場合はsourceそのものだけを１個入れたリストを返します。
k=n-1の場合は、n個の要素から２個選ぶitertoolsパッケージを利用します。
漸化式はnもkも１たりないリストのときは、孤独のリスト[str(n)]をくっつけましょう。
nだけ足りないときは、リストのなかのリストをとりだし、その中の各要素から選んだものに[str(n)]を
まぜればいいね。
ただし、要素から取り出すときはリストを集合にして引き算をして、リストに戻して、加工したものを
くっつけましょう。
#[IN]Python================================
from itertools import combinations as combi
def S2V(n,k):
res = []
source = list(map(lambda x:str(x),list(range(1,n+1))))
if n < k :
return [[]]
elif n == k:
return [source]
else:
if k==1:
return [["".join(source)]]
if n == k + 1:
for items in combi(source,2):
x,y = items
pair= x+y
left = sorted(list(set(source) - set(items)))
res.append([pair] + left)
return res
else:
for itemA in S2V(n-1,k-1):
res.append(itemA + [str(n)])
for itemB in S2V(n-1,k):
for arry in itemB:
withn = arry + str(n)
left = sorted(list(set(itemB)- set([arry]))) #set()が文字列を分解しないようにset([])とする
res.append([withn] + left)
return res
def printS2(n,k):
msg = f"S2({n},{k})->"
print(msg)
print(S2V(n,k))
return True
print("第２種スターリング数の見える化")
for i in range(3,5):
for j in range(1,i+1):
printS2(i,j)
#===================
[OUT]
第２種スターリング数の見える化
S2(3,1)->
[['123']]
S2(3,2)->
[['12', '3'], ['13', '2'], ['23', '1']]
S2(3,3)->
[['1', '2', '3']]
S2(4,1)->
[['1234']]
S2(4,2)->
[['123', '4'], ['124', '3'], ['34', '12'], ['134', '2'], ['24', '13'], ['234', '1'], ['14', '23']]
S2(4,3)->
[['12', '3', '4'], ['13', '2', '4'], ['14', '2', '3'], ['23', '1', '4'], ['24', '1', '3'], ['34', '1', '2']]
S2(4,4)->
[['1', '2', '3', '4']]
質問：第１種スターリング数を見える化するにはどうしたらよでしょうか。
巡回置換C(n)は（ ）の中に巡回する数字の順に書き出す場合の数でした。
これを見える化するには、１を先頭にかくことにすると、２以降数字の順列を作り、
１のあとにくっつけましょう。それがCVs(n)です。
CにつけたVはビジュアル化という意味です。sはリストのリストを返す、複数という意味での
ネーミングです。
そのあとは、再帰的なS1(n,k)の作り方にそって、S1V(n,k)のコードをかこう。
言語の内部では、巡回置換ということは扱えないので、
あくまでも数字列のリストのリストとして、
第２種と同じようにデータをもたせておこう。
表示するときだけ、リストのリストの各文字列に（ ）をつけてプリントすればよいね。
#[IN]Pyhton===================================
#第１種スターリング数の見える化
from itertools import combinations as combi
def CVs(n):
source = list(map(lambda x:str(x),list(range(2,n+1))))
res = []
for per in perm(source,n-1):
per=['1'] + list(per)
item = "".join(per)
res.append([item])
return res
def S1V(n,k):
res = []
source = list(map(lambda x:str(x),list(range(1,n+1))))
if n < k :
return [[]]
elif n == k:
return [source]
else:
if k==1:
return CVs(n)
if n == k + 1:
for items in combi(source,2):
x,y = items
pair= x+y
left = sorted(list(set(source) - set(items)))
res.append([pair] + left)
return res
else:
for itemA in S1V(n-1,k-1):
res.append(itemA + [str(n)])
for itemB in S1V(n-1,k):
for i in range(1,n): #ｎの行き先をi(１からn-1)にするため、iをniに置き換える。
for arry in itemB:
temp = arry
if str(i) in arry:
withn = temp.replace(str(i),str(n)+str(i))
left = sorted(list(set(itemB)- set([arry]))) #set()が文字列を分解しないようにset([])とする
res.append([withn] + left)
return res
def printS1(n,k):
msg = f"S1({n},{k})->"
print(msg, end=" ")
for items in S1V(n,k):
for cycle in items:
item = "(" + cycle + ")"
print(item, end="")
print(", ",end="")
print()
return True
print("第１種スターリング数の見える化")
for i in range(3,5):
for j in range(1,i+1):
printS1(i,j)
#=======================================
[OUT]
第１種スターリング数の見える化
S1(3,1)-> (123), (132),
S1(3,2)-> (12)(3), (13)(2), (23)(1),
S1(3,3)-> (1)(2)(3),
S1(4,1)-> (1234), (1243), (1324), (1342), (1423), (1432),
S1(4,2)-> (123)(4), (132)(4), (412)(3), (142)(3), (43)(12), (413)(2), (42)(13), (143)(2), (41)(23), (423)(1), (243)(1),
S1(4,3)-> (12)(3)(4), (13)(2)(4), (14)(2)(3), (23)(1)(4), (24)(1)(3), (34)(1)(2),
S1(4,4)-> (1)(2)(3)(4),