[b]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/b][br]数や関数を並べた列、たいていは[b][color=#0000ff]数列｛An｝[/color][/b]に対して、[br]これを係数をする[b]多項式、形式的なべき級数 ΣAnｘ^nや[b]Σ(Anｘ^n/n!)[/b][/b]を[br][color=#0000ff]｛An｝の[b]母関数[/b][/color]といいます。[br]ｎは有限でなくてもよく、このべき級数も収束するかは問わない[b]形式的な[/b]べき級数です。[br]無限次元にしたとしても、無限の程度を問うわけでもなく、形式的に有界にしていないだけです。[br]規則性を見つけるための無限なので、使う部分はわりと低次元の項どうしの計算だったりします。[br][br]そもそも多項式は、整数と同じで、[b]たし算、定数倍、積で閉じた[/b]集合体、[b]環[/b]なので、[br]整数と同じように自由に＋,×,ｋ倍ができるね。[br][br]また、[b]項別に微分をしたり、級数の和を求めるなどの[/b]式の変形ができたり、[br]いろんな視点とからめて数学分野を横断する技として使えます。[br][br]・例１[br]{An}={1 }のとき、an=[1,1,1,1,1,......]の母関数はf(x)=1+x+x[sup]2[/sup]+x[sup]3[/sup]+.......ですね。[br]これを等比数列の和の公式と極限を使って、f(x)=1/(1-x)とかけますね。[br]つまり、母関数f(x)は、[b]1/(1-x)=1+x+x[sup]2[/sup]+x[sup]3[/sup]+.....[/b]. のように、[br][b][color=#0000ff]まとめた式＝バラした式[/color][/b]の形にかけるね。[br][br]・例２[br]{An}={nCr | 0≦r≦n, nはn∈N の定数｝のとき、an=[nC0, nC1,......,nCn-1,nCn}の母関数は[br]f(x)=(1+x)[sup]n[/sup]=nC[sub]0[/sub]x[sup]0[/sup]+nC[sub]1[/sub]x+....+nC[sub]n-1[/sub]x[sup]n-1[/sup]+nC[sub]n[/sub]x[sup]n[/sup]ですね。[br]ここで母関数ｆにx=1を代入すると、2[sup]n[/sup]=nC[sub]0[/sub]+nC[sub]1[/sub]+....+nC[sub]n-1[/sub]+nC[sub]n[/sub]が、[br]ここで母関数ｆにx=-1を代入すると、0=nC[sub]0[/sub]-nC[sub]1[/sub]+....+(-1)[sup]n[/sup]nC[sub]n[/sub][sub][/sub]が得られます。[br]母関数の[b]ｘに値を代入[/b]すると、[b][color=#0000ff]バラした値＝まとめた値[/color][/b]ができるね。[br][br]・例３[br]母関数を[b]微分[/b]する。例１の1/(1-x)=1+x+x[sup]2[/sup]+x[sup]3[/sup]+......は[br]左辺の微分=d((1-x)[sup]-1[/sup])/dx=-1(1-x)[sup]-2[/sup](1-x)'=1/(1-x)[sup]2[/sup][br]右辺の微分=0+[b]1+2x+3x[sup]2[/sup]+.....[/b]=Σkx[sup]k-1[/sup]=Σkx[sup]k[/sup]/x=1/xΣkx[sup]k[/sup]だ。[br]これから、1/(1-x)[sup]2[/sup]=1/xΣkx[sup]k[/sup]。つまり、[b]x/(1-x)[sup]2[/sup]=Σkx[sup]k[/sup][/b]と言える。[br][b]右辺は{An}={n|n∈N},an=[1,2,3,4,....]の形式的なべき級数、つまり母関数といえる。[br][/b]母関数を[b]微分[/b]することで、別の母関数を作ることができたということだね。[br][br]・例４[br]母関数の指数を[b]取り出す個数[/b]と考えて、[b]かけ算[/b]してみよう。[br](1+x+x[sup]2[/sup]+x[sup]3[/sup]+x[sup]4[/sup])(1+x+x[sup]2[/sup]+x[sup]3[/sup])(1+x+x[sup]2[/sup])=1+3x+6x[sup]2[/sup]+9x[sup]3[/sup]+11x[sup]4[/sup]+11x[sup]5[/sup]+9x[sup]6[/sup]+6x[sup]7[/sup]+3x[sup]8[/sup]+x[sup]9[/sup][br]３つの母関数は5円玉が4枚以下、10円玉が3枚以下、50円玉が2枚以下の取り出しとする。[br]３つの母関数の積の母関数は、係数は場合の数を、指数は取り出した合計個数をあらわします。[br]3x[sup]8[/sup]は合計8枚の取り出しが3通りあることに対応する。[br][br]・例５[br]母関数をｎ回[b]かけ算[/b]する。[br]例１の1/(1-x)=1+x+x[sup]2[/sup]+x[sup]3[/sup]+.....をｎ回かけると、[br]1/(1-x)[sup]n[/sup]=(1+x+x[sup]2[/sup]+x[sup]3[/sup]+.....)(1+x+x[sup]2[/sup]+x[sup]3[/sup]+.....)(1+x+x[sup]2[/sup]+x[sup]3[/sup]+.....)........(1+x+x[sup]2[/sup]+x[sup]3[/sup]+.....)[br]右辺を展開したときの[b]ｘ[sup]k[/sup][/b]の係数は、n個のカッコから指数和がｋになるように取り出す数、[br]たとえると[b]ｎ個の箱から重複をゆるして合計ｋ個[/b]とりだす数、[br]つまり、k個の物とn-1個のしきり物からｋ個選ぶ組み合わせ、つまり、[b][sub]n+k-1[/sub]C[sub]k[/sub][/b]となるね。[br]1/(1-x)[sup]n[/sup]=Σ[sub]n+k-1[/sub]C[sub]k[/sub]x[sup]k[/sup]となり、数列｛[sub]n+k-1[/sub]Ck｝の母関数は(1+x+x[sup]2[/sup]+x[sup]3[/sup]+.....)[sup]n[/sup]=1/(1-x)[sup]n[/sup][br]母関数を[b]かけ算[/b]すると、別の母関数ができました。[br][br]・例６[br]母関数の指数を[b]シフトしてｎ回かける。[/b][br]例１の1/(1-x)=1+x+x[sup]2[/sup]+x[sup]3[/sup]+.....を両辺ｘ倍すると、x/(1-x)=x+x[sup]2[/sup]+x[sup]3[/sup]+.....[br]となるね。これは、１個以上選ぶことを表してるね。[br]これをｎ回かけると、x[sup]n[/sup]/(1-x)[sup]n[/sup]=(x+x[sup]2[/sup]+x[sup]3[/sup]+.....)[sup]n[/sup]=x[sup]n[/sup](x+x[sup]2[/sup]+x[sup]3[/sup]+.....)[sup]n[/sup]となる。[br]これと例５から、(x+x[sup]2[/sup]+x[sup]3[/sup]+.....)[sup]n[/sup]＝x[sup]n[/sup]Σ[sub]n+k-1[/sub]C[sub]k[/sub]x[sup]k[/sup][b](k＝０から∞）=[/b]Σ[sub]r-1[/sub]C[sub]r-n[/sub]x[sup]r[/sup][b](n+k=r=nから∞）[br][/b]数列{[b][sub]r-1[/sub]C[sub]r-n[/sub][/b]}の母関数ができたね。[br]n+k=rの置き換えをしたので、ｒはｎ以上。[br][b]xrの係数は、n個から重複を許してｒ個取り出す数であり、それが[sub]r-1[/sub]C[sub]r-n[/sub]になる[/b]ことがわかった。[br][br]・例７[b][br]合計金額[/b]と考えて[b]かけ算[/b]すると、係数は種類をまぜた組み合わせを表す。[br](1+x[sup]5[/sup]+x[sup]10[/sup]+x[sup]15[/sup]+x[sup]20[/sup])(1+x[sup]10[/sup]+x[sup]20[/sup])(1+x[sup]50[/sup]+x[sup]100[/sup]+x[sup]150[/sup])[br]=1+x[sup]5[/sup]+2x[sup]10[/sup]+........... + 2x[sup]160[/sup]+2x[sup]165[/sup]+3x[sup]170[/sup]+2x[sup]175[/sup]+2x[sup]180[/sup]+x[sup]185[/sup]+x[sup]190[/sup][br]３つの母関数の指数は5円玉4枚以下、10円2枚以下、ｈが50円3枚以下で作れる金額を表す。[br]積の母関数の係数が場合の数で、指数はまぜた合計金額になる。[br][b]3x[sup]170[/sup][/b]は合計金額が[b]170円になるのが3通り[/b]あることを表しているね。[br][br]・例８[br]文字ｘにｔｘのように区別文字つきのｘを代入して種類を特定できる。[br]例１の1/(1-x)=1+x+x[sup]2[/sup]+x[sup]3[/sup]+.....のｘにｔｘを代入すると、1/(1-tx)=1+tx+t[sup]2[/sup]x[sup]2[/sup]+t[sup]3[/sup]x[sup]3[/sup]+.....[br]母関数の指数を[b]取り出す個数[/b]と考えて、[b]かけ算するときに区別文字を入れる。[/b][br](1+ax+a[sup]2[/sup]x[sup]2[/sup]+a[sup]3[/sup]x[sup]3[/sup]+a[sup]4[/sup]x[sup]4[/sup])(1+bx+b[sup]2[/sup]x[sup]2[/sup]+b[sup]3[/sup]x[sup]3[/sup])(1+cx+c[sup]2[/sup]x[sup]2[/sup])の展開でx[sup]8[/sup]は合計8枚の取り出し方になる。[br]係数はa[sup]3[/sup]b[sup]3[/sup]c[sup]2[/sup]+a[sup]4[/sup]b[sup]3[/sup]c+a[sup]4[/sup]b[sup]2[/sup]c[sup]2[/sup]これから、a,b,cから合計８枚選ぶ組み合わせは(3,3,2),(4,3,1),(4,2,2)。[br][sup][br][/sup]

数の分割[b][color=#0000ff]decompose,divide,partition[/color][/b]とは、[br]その数自身または、それ以外の数の和の組み合わせの式のことで、[br]分割数はその総数です。[br]たとば、３の分解は３，２＋１，１＋１＋１があり、分割数は３（通り）です。[br][br][br]・例９[br]xにｘpを代入すると、(x[sup]p[/sup])[sup]n[/sup]=x[sup]np[/sup]から、[br]例１の母関数f(xp)は、[b]1/(1-[b]x[sup]p[/sup][/b])=1+x[sup]p[/sup]+x[sup]2p[/sup]+.....[b]x[sup]kp[/sup]+[/b][/b] [br]n個からp個単位で取り出すことを表します。このpを1,2,3,4,....として母関数をかけたものは[br][br][size=150][b]1/{(1-[b]x[sup]1[/sup][/b])[/b][b](1-[b]x[sup]2[/sup][/b])[/b][b](1-[b]x[sup]3[/sup][/b])[/b][b](1-[b]x[sup]4[/sup][/b]).....}[b]=Σ[b]x[sup]k[/sup][b][b]Σ[b]x[sup]2k[/sup][b][b]Σ[b]x[sup]3k[/sup][b][b]Σ[b]x[sup]4k[/sup][b][b]Σ..... = 1 + 1x+2x[sup]2[/sup]+3x[sup]3[/sup]+5x[sup]4[/sup]+7x[sup]5[/sup]+....[br][/b][/b][/b][/b][/b][/b][/b][/b][/b][/b][/b][/b][/b][/b][/size][size=150][br][color=#0000ff]ｎの和分解[b]decompose[/b]の数はｘ[sup]n[/sup]の係数に等しい。[br][/color][/size][b][br]（検証）母関数の係数を分離したリストを作る[br]1/(1-[b]x[sup]1[/sup][/b])=1+[b][b]x[sup]1[/sup][/b][/b]+x[sup]2[/sup]+[b]x[sup]3[/sup]+[/b][b]x[sup]4[/sup][b][b]+[/b][b]x[sup]5　[/sup][/b][/b][/b][/b] -> [1,1,1,1,1,1] [br][b]1/(1-[b]x[sup]2[/sup][/b])=1+[b][b]x[sup]2[/sup][/b][/b]+x[sup]4[/sup][/b] -> [1,0,1,0,1,0] [br][b]1/(1-[b]x[sup]3[/sup][/b])=1+[b][b]x[sup]3[/sup][/b][/b][/b] -> [1,0,0,1,0,0] [br][b]1/(1-[b]x[sup]4[/sup][/b])=1+[b][b]x[sup]4[/sup][/b][/b][/b] ->[1,0,0,0,1,0] [br][b]1/(1-[b]x[sup]5[/sup][/b])=1+[b][b]x[sup]5[/sup][/b][/b][/b] ->[1,0,0,0,0,1] [br]右辺の積は[b]1+[b][b]x[sup]1[/sup][/b][/b]+2x[sup]2[/sup]+3[b]x[sup]3[/sup]+5[/b][b]x[sup]4[/sup][b][b]+7[/b][b]x[sup]5[/sup][/b][/b][/b][/b] +.......[br]x[sup]4[/sup]の係数は5。これは、4の[4, 3+1, 2+2, 2+1+1, 1+1+1+1]の５通りの和分解に一致する。[br]x[sup]5[/sup]の係数は7。これは、５の[5, 4+1, 3+2, 3+1+1,2+2+1,2+1+1+1,1+1+1+1+1]の7通りの和分解に一致する。[br][br][br][color=#9900ff][b][u][size=150]質問：例９の考え方を使って、整数Nの和分解をする関数を作るにはどうしたらようでしょうか。[br][/size][/u][/b][/color][br]多項式の係数を取り出します。つぎに逆順にして繰り上がらないｘ進法（ｘが巨大）として[br]係数をかけ算します。筆算でもできますよ。[br][1,1,1,1,1,1] reverse-> 111111[br][1,0,1,0,1,0] reverse-> 010101[br][1,0,0,1,0,0] reverse-> 001001[br][1,0,0,0,1,0] reverse-> 010001[br][1,0,0,0,0,1] reverse-> 100001[br]10になっても繰り上がりせずに、111111×010101(mod 1000000) = 332211[br]332211×1001(mod 1000000)=543211[br]543211×10001(mod 1000000)=653211[br]653211×100001(mod 1000000)=753211となります。つまり、[br][br][b]111111*10101*1001*10001*100001 % 1000000= 753211[br][/b][br]このreverseして、[1,1,2,3,5,7]になりますね。[br]これで、1から５まで和分解の数がわかる係数の数列ができました。[br][br]このような発想でｎを和分解する関数[b]decompo[/b](n)を作ってみよう。[br]ポイントは、１からｎまでのそれぞれの倍数を表す母関数リスト[b]genef[/b]は[b]静的[/b]に作れます。[br]だから、宣言型、関数型プログラミングが向いています。[br][br]次に母関数のかけ算ですが、逆転してからかけ算して、最後にもとに戻すのは[br]筆算には向いています。プログラミングでは、あえて逆転せずにそのままできます。[br]係数リストの番号が、母関数の次数を表していると考えれば、０次の定数項が０番、[br]１次の係数がリストの１番、、、、と考えると、ｎ次の係数はリストのｎ番となるからです。[br][br]ｎ個の関数１の倍数の[b]genef[/b][0]からｎの倍数の[b]genef[/b][n-1]までを全部かけ算して、[br]xnの係数を求めよう。[br]このかけ算は、かけ算の結果、[b]状態が変化する[/b]プロセスなので[br]動的な、通常の手続きのくり返し型のプログラミングが向いているでしょう。[br][b][IN]Python=========================================================[br][color=#0000ff]def decompo(n):[br] max_id = n+1[br] genef = [] # 反復後の母関数係数のリスト[br] indexs = [x for x in range(max_id)][br] for i in range(1,max_id):[br] genef.append(list(map(lambda x : 1 if x % i ==0 else 0, indexs)))[br] print(f"{n}の和分解をするために、母関数をかける。prev*current")[br] prev = genef[0] [br] # prevの初期値はgenefの先頭の母関数[br] for i in range(1,max_id-1):[br] ans = [0]*(3*n)[br] current = genef[i] #currentはgeneの１以上の母関数[br] print(f"prev = {prev},current = {current}")[br] for k in range(max_id): # current のk番を動かす[br] if current[k]==1:[br] for j in range(max_id): #prevをkけたシフトしてansに加算[br] ans[j + k] += prev[j][br] for l in range(max_id):[br] prev[l] = ans[l] #ansの内容をprevに必要な分だけコピー[br] print(f"関数積 {prev}から、{n} の分解数＝{ans[n]}")[br] return True[br][/color][br]decompo(4)[br]decompo(6)[br]decompo(9)[br][/b][OUT]=============================================[br]4の和分解をするために、母関数をかける。prev*current[br]prev = [1, 1, 1, 1, 1],current = [1, 0, 1, 0, 1][br]prev = [1, 1, 2, 2, 3],current = [1, 0, 0, 1, 0][br]prev = [1, 1, 2, 3, 4],current = [1, 0, 0, 0, 1][br]関数積 [1, 1, 2, 3, 5]から、4 の分解数＝5[br]6の和分解をするために、母関数をかける。prev*current[br]prev = [1, 1, 1, 1, 1, 1, 1],current = [1, 0, 1, 0, 1, 0, 1][br]prev = [1, 1, 2, 2, 3, 3, 4],current = [1, 0, 0, 1, 0, 0, 1][br]prev = [1, 1, 2, 3, 4, 5, 7],current = [1, 0, 0, 0, 1, 0, 0][br]prev = [1, 1, 2, 3, 5, 6, 9],current = [1, 0, 0, 0, 0, 1, 0][br]prev = [1, 1, 2, 3, 5, 7, 10],current = [1, 0, 0, 0, 0, 0, 1][br]関数積 [1, 1, 2, 3, 5, 7, 11]から、6 の分解数＝11[br]9の和分解をするために、母関数をかける。prev*current[br]prev = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],current = [1, 0, 1, 0, 1, 0, 1, 0, 1, 0][br]prev = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5],current = [1, 0, 0, 1, 0, 0, 1, 0, 0, 1][br]prev = [1, 1, 2, 3, 4, 5, 7, 8, 10, 12],current = [1, 0, 0, 0, 1, 0, 0, 0, 1, 0][br]prev = [1, 1, 2, 3, 5, 6, 9, 11, 15, 18],current = [1, 0, 0, 0, 0, 1, 0, 0, 0, 0][br]prev = [1, 1, 2, 3, 5, 7, 10, 13, 18, 23],current = [1, 0, 0, 0, 0, 0, 1, 0, 0, 0][br]prev = [1, 1, 2, 3, 5, 7, 11, 14, 20, 26],current = [1, 0, 0, 0, 0, 0, 0, 1, 0, 0][br]prev = [1, 1, 2, 3, 5, 7, 11, 15, 21, 28],current = [1, 0, 0, 0, 0, 0, 0, 0, 1, 0][br]prev = [1, 1, 2, 3, 5, 7, 11, 15, 22, 29],current = [1, 0, 0, 0, 0, 0, 0, 0, 0, 1][br]関数積 [1, 1, 2, 3, 5, 7, 11, 15, 22, 30]から、9 の分解数＝30[br][br]例10　[br]６色の色紙がそれぞれ６枚ずつあるとする。これから重複を許して６枚選ぶ組み合わせを求める。[br]同じ母関数を６回かけよう。[br][b](1+[b][b]x[sup]1[/sup][/b][/b]+x[sup]2[/sup]+[b]x[sup]3[/sup]+[/b][b]x[sup]4[/sup][b][b]+[/b][b]x[sup]5[/sup][/b][/b][/b][/b]+[b][b]x[sup]6[/sup])[/b][/b][sup]6 [/sup]を展開して、ｘ[sup]6[/sup]の係数をもとめればよいね。[br]6=6, 5+1, 4+2, 4+1+1, 3+3, 3+2+1, 3+1+1+1, 2+2+2, 2+2+1+1, 2+1+1+1+1,1+1+1+1+1+1から多項定理から、[br]6C1+6*5+6*5+6*5C2+6!/(3!3!)+6P3+6*5C3+6!/(2!2!2!)+6C2*4C2+6C1*5C4+6C6[br]=6+30*2+60+20+120+60+15+90+30+1=462通りだね。[br][br][color=#9900ff][b][u][size=150]質問：例10の6種6枚から重複して6選ぶ重複組み合わせをコードで求めるにはどうしますか。[br][/size][/u][/b][/color][br]例９では母関数がnだけあったけれど、重複組み合わせでは、同じ１つの母関数をｎ乗するだけだから、[br]むしろ、しくみは簡単になるね。[br]母関数の係数であるgeneリストは定数項もあるので、1をn+1個並べたもの。[br]かならずかけ算になるので、ifは不要になるし、１倍だから、[br]シフトするだけというしくみも同じになるね。[br][br]#[IN]Python[br][color=#0000ff]def dblcombi(n):[br] max_id = n+1[br] gene = [1]*max_id[br] print(f"{n}の重複組み合わせを求めるために、母関数を{n}回かける。")[br] prev = gene [br] # prevの初期値はgenefの先頭の母関数[br] for i in range(1,max_id-1):[br] ans = [0]*(3*n)[br] print(f"prev^{i} = {prev}")[br] for k in range(max_id): #current のk番を動かす[br] for j in range(max_id): #prevをkけたシフトしてansに加算[br] ans[j + k] += prev[j][br] for l in range(max_id):[br] prev[l] = ans[l] #ansの内容をprevに必要な分だけコピー[br] print(f"prev^{n} = {prev}から、{n}枚の組み合わせ数＝{ans[n]}")[br] return True[br][/color][br]dblcombi(6)[br]dblcombi(8)[br]#=========================[br][OUT][br]6の重複組み合わせを求めるために、母関数を6回かける。[br]prev^1 = [1, 1, 1, 1, 1, 1, 1][br]prev^2 = [1, 2, 3, 4, 5, 6, 7][br]prev^3 = [1, 3, 6, 10, 15, 21, 28][br]prev^4 = [1, 4, 10, 20, 35, 56, 84][br]prev^5 = [1, 5, 15, 35, 70, 126, 210][br]prev^6 = [1, 6, 21, 56, 126, 252, 462]から、6枚の組み合わせ数＝462[br]8の重複組み合わせを求めるために、母関数を8回かける。[br]prev^1 = [1, 1, 1, 1, 1, 1, 1, 1, 1][br]prev^2 = [1, 2, 3, 4, 5, 6, 7, 8, 9][br]prev^3 = [1, 3, 6, 10, 15, 21, 28, 36, 45][br]prev^4 = [1, 4, 10, 20, 35, 56, 84, 120, 165][br]prev^5 = [1, 5, 15, 35, 70, 126, 210, 330, 495][br]prev^6 = [1, 6, 21, 56, 126, 252, 462, 792, 1287][br]prev^7 = [1, 7, 28, 84, 210, 462, 924, 1716, 3003][br]prev^8 = [1, 8, 36, 120, 330, 792, 1716, 3432, 6435]から、8枚の組み合わせ数＝6435

数列｛An｝の母関数は数列を係数にしてつくった。[br]それ以外に係数/n!にして作る方法もある。[br]この形式を使うと、収束するときの関数などでも便利に使えるようになる。[br][br]例2.1[br]｛An}=[1,1,1,1,.....]で　[b]Σ x[sup]k[/sup]/k!=1+x+x[sup]2[/sup]/2!+ .....＝e[sup]x[/sup][/b][br] 　無限級数の和は、自然対数eを使った指数関数になる。[br]　言い換えると、数列{1}の母関数が、e[sup]x[/sup]のマクローリン展開を与えていることになる。[br][br]そんなわけで、この形を指数型の母関数と呼ぶことが多い。[br]例2.2[br]例2.1を[b]ｎ回かけて展開[/b]すると、f(x)= [b](1+x/1+x[sup]2[/sup]/2!+ .....)[sup]n[/sup]=e[sup]nx[/sup][/b][br]この母関数の右辺は例2.1の[b]ｘにnxを代入したと見る[/b]ことができるね。[br]だから、f(x)=Σ(nx)[sup]k[/sup]/k!=Σ[b](n[sup]k[/sup])[/b]x[sup]k[/sup]/k!となる。だから、[br]これは｛An}=n[sup]k[/sup]、n通りがk回反復する数だから、n個から重複OKでｋ個選ぶ数[br][b]重複順列の母関数[/b]だとわかるね。[br][br]例2.3[br]例2.1の式を変形すると、x+x[sup]2[/sup]/2!+ .....=e[sup]x[/sup]−１。これをｍ回かけた式は(e[sup]x[/sup]−１)[sup]m[/sup][br]一方で、2項定理の式から[br][b](e[sup]x[/sup]−１)[sup]m[/sup][/b]=((e[sup]x[/sup])+(-１))[sup]m[/sup]=Σ ([sub]m[/sub]C[sub]m-k[/sub](e[sup]x[/sup])[sup]m-k[/sup](-1)[sup]k[/sup])=Sum([sub]m[/sub]C[sub]k[/sub] (-1)[sup]k[/sup]e[sup](m-k)x [/sup],ｋ,0,ｍ)[br]また、例2.1のｘに(m-k)xを代入すると、e[sup](m-k)x[/sup]=Sum((m-k)[sup]n[/sup]x[sup]n[/sup]/n!, n,０,∞）[br]これを上の式に代入して、(e[sup]x[/sup]−１)[sup]m[/sup]=Sum([sub]m[/sub]C[sub]k[/sub] (-1)[sup]k [/sup](Sum( (m-k)[sup]n[/sup]x[sup]n[/sup]/n! ), n, 0, ∞), k, 0, m)[br]sumとsumの間の[sub]m[/sub]C[sub]k[/sub] (-1)[sup]k [/sup]は、nの変化を受けないから定数扱いしてSumの中に入れられる。[br]その後、2重のΣはよこの合計をたてに合計しても、たての合計をよこに合計しても最後は同じなので、[br]Σの内、外を入れえよう。[br]＝Sum([b]Sum[/b][b] ((-1)[sup]k[/sup][sub]m[/sub]C[sub]k[/sub] (m-k)[sup]n[/sup][/b]) , k, 0, m) [b]x[sup]n[/sup]/n![/b]) , n, 0, ∞) [br]結局、[br](e[sup]x[/sup]−１)[sup]m[/sup]＝Σ (Σ[b]((-1)[sup]k[/sup][sub]m[/sub]C[sub]k[/sub] (m-k)[sup]n[/sup][/b])) [b]x[sup]n[/sup]/n![/b]) [br]ｍ！で両辺をわると、[br](e[sup]x[/sup]−１)[sup]m[/sup][color=#0000ff]/m![/color]=Σ (Σ[b]((-1)[sup]k[/sup][sub]m[/sub]C[sub]k[/sub] (m-k)[sup]n[/sup][/b])/[color=#0000ff]m![/color]) [b]x[sup]n[/sup]/n![/b]) =Σ S2(n,k) x[sup]n[/sup]/n![br]第２種スターリング数の指数型の母関数が(e[sup]x[/sup]−１)[sup]m[/sup][color=#0000ff]/m!となったね。[br][/color][br]例2.4[br]０個もありうるときは[b]Σ x[sup]k[/sup]/k!=[/b][b]1+x+x[sup]2[/sup]/2!+ .....＝e[sup]x　[br][/sup][/b]１個以上のときは、０乗の項がないので、[b]x[sup]2[/sup]/2!+ .....＝e[sup]x[/sup][/b]−１[br]こう考えると、場合の問題に指数型母関数を使うこともできるね。[br]１から５までの数をｒ個並べるとき、1,2,3は1個以上並べ、4,5は0個以上並べるとしたら、[br]母関数の積は([b]e[sup]x[/sup][/b]−１)[sup]3[/sup]([b]e[sup]x[/sup][/b])[sup]2[/sup]=([b]e[sup]3x[/sup][/b]−3[b]e[sup]2x[/sup][/b]+3[b]e[sup]x[/sup][/b]−1)([b]e[sup]2x[/sup][/b])=[b]e[sup]5x[/sup][/b]−3[b]e[sup]4x[/sup][/b]+3[b]e[sup]3x[/sup][/b]−[b]e[sup]2x [br][/sup][/b][b]=Σ (5x)[sup]k[/sup]/k!+[b]Σ (-3(4x)[sup]k[/sup]/k!)+[/b][b]Σ( +3(3x)[sup]k[/sup]/k!)+[/b][b]Σ(- (2x)[sup]k[/sup]/k!) =[b]Σ (5[sup]k[/sup]-3*[b][b]4[sup]k [/sup][/b][/b][/b][/b][/b][b][b]+3*3[sup]k[/sup][/b][/b][b][b]- 2x[sup]k[/sup][/b][/b][b])x[sup]k[/sup]/k![br][/b]Σの線形性からΣを分配法則のように１つにまとめることができるね。[br]だから、ｘ[sup]r[/sup]の係数[b][b][b]5[sup]r[/sup]-3*[b][b]4[sup]r [/sup][/b][/b][/b][/b][/b][b][b]+3*3[sup]r[/sup][/b][/b][b][b]- 2[sup]r[/sup][/b][/b]が、求める場合の数になる。[br]r=5のときは5**5-3*4**5 +3*3**5- 2**5＝750通りになるね。[br][br]例2.5[br]ｍ人をA,B,Cの3部屋に空き部屋ができないように1人以上入れるとき振り分け方の数[br]A,B,Cの３つの記号をｍ個並べるのと同じだから、例2.4と同様にできる。[br]母関数の積は([b]e[sup]x[/sup][/b]−１)[sup]3[/sup]＝[b]e[sup]3x[/sup][/b]−3[b]e[sup]2x[/sup][/b]+3[b]e[sup]x[/sup][/b]−1=[b][b][b]Σ (3[sup]k[/sup]-3*[b][b]2[sup]k [/sup][/b][/b][/b][/b][/b][b][b]+3[/b][/b][b])x[sup]k[/sup]/k! -1[/b][b][sup][br][/sup][/b]だからx[sup]m[/sup]の係数[b][b][b]3[sup]m[/sup]-3*[b][b]2[sup]m [/sup][/b][/b][/b][/b][/b][b]+3[/b]が求める場合の数になる。[br]たとえばm=8のときは、3^8-3*2^8+3 = 5796通りになるね。

[color=#0000ff]オイラーは２種類の分割が同数になることを、母関数が一致することで証明した。[br][/color][br]２種類の分割とは、[br][br][b][size=150]数Nを異なる整数に和分解と数Nを奇数だけに和分解のことだ。[br][/size][/b][br]例4.1[br]・６を異なる整数に和分解する方法は4通り[br]　6,5+1,4+2,3+2+1[br]・６を奇数だけに和分解する方法は4通り[br]　5+1,3+3,3+1+1+1,1+1+1+1+1+1[br]例4.2[br]・9を異なる数に和分解する方法は8通り[br] 9, 8+1,7+2,6+3,6+2+1,5+4,5+3+1,4+3+2[br]・9を奇数だけに和分解する方法は8通り[br] 9, 7+1+1,5+3+1,5+1+1+1+1,3+3+3,3+3+1+1+1,3+1+1+1+1+1+1,1+1+1+1+1+1+1+1+1[br][br]オイラーは巧妙な方法で分割数が同一であることを一般的に証明しました。[br][b]ｎを異なる数に和分解する母関数Q[/b]は（１＋ｘ[sup]i[/sup])（iは1,2,3,.....)の積になります。[br]理由は、それぞれはnの分解に1,2,3,...を使うかどうかの選択を表しているので、同じ数を2回以上使うことはないからです。[br]6=3+3という分割ができませんが、6=3+2+1の分割はできますね。[br][br][b]Q=(1+x)(1+x[sup]2[/sup])(1+x[sup]3[/sup]).......... = 1+x+x[sup]2[/sup]+2x[sup]3[/sup]+2x[sup]4[/sup]+3x[sup]5[/sup]+4x[sup]6[/sup]+..........[br][/b][br]証明のために、Qの符号をマイナスにした式[br]P=(1-x)(1-x[sup]2[/sup])(1-x[sup]3[/sup])..........を用意しよう。[br]PQ=(1+x)(1+x[sup]2[/sup])(1+x[sup]3[/sup])..........・(1-x)(1-x[sup]2[/sup])(1-x[sup]3[/sup]).........[br]=(1+x)(1-x)(1+x[sup]2[/sup])(1-x[sup]2[/sup])(1+x[sup]3[/sup])(1-x[sup]3[/sup]).........[br]=(1-x[sup]2[/sup])(1-x[sup]4[/sup])(1-x[sup]6[/sup])...............[br]PQ/P=(1-x[sup]2[/sup])(1-x[sup]4[/sup])(1-x[sup]6[/sup]).........../(1-x)(1-x[sup]2[/sup])(1-x[sup]3[/sup]).........[br]=1/(1-x)(1-x[sup]3[/sup])(1-x[sup]5[/sup]).........[br][b][color=#0000ff]＝Rとします。指数が偶数の項が約分して、奇数だけが残りました。[br][/color][/b]さてこれは何でしょう。[br]PQ/P＝Qであることは明らかですが、[br]最後の式Rは例1や例９に出てきた、分数式を級数の和に直すと意味を思い出せるね。[br]1/(1-x)=1+x[sup]1[/sup]+x[sup]2[/sup]+x[sup]3[/sup]+x[sup]4[/sup]+.... (１をいくつか使う）[br]1/(1-x[sup]3[/sup])=1+x[sup]3[/sup]+x[sup]6[/sup]+x[sup]9[/sup]+x[sup]12[/sup]+....（３をいくつか使う）[br]1/(1-x[sup]5[/sup])=1+x[sup]5[/sup]+x[sup]10[/sup]+x[sup]15[/sup]+x[sup]20[/sup]+....（５をいくつか使う）[br]つまり、これらの積[b]Rは奇数だけをいくつか使った和分解を表す母関数です[/b]。[br]だから、Q=Rとなるのです。[br][br]オイラーは、すばらしいですね。