ザ計算力

解答(その8)と解答(その9)によって、
任意の自然数n'に対して、n';p(1),・・・,p(n')が与えられた場合の図の個数は、
σ(364-(n'-1),n')+σ(364-(n'-2),n'-1)
=_{364-(n'-1)+n'-1}C_n'+_{364-(n'-2)+n'-1-1}C_n'-1
= ₃₆₄C_n'+₃₆₄C_n'-1
= 364!/[n'!(364-n')!]+364!/[(n'-1)!(364-n'+1)!]
= {364!/[(n'-1)!(364-n')!]}[1/n'+1/(365-n')]
= {364!/[(n'-1)!(364-n')!]}×365/[n'(365-n')]
= 365!/[n'!(365-n')!]
= ₃₆₅C_n'
だと分かる。

この結果を見て気付いたのだが、解答(その7)で○の隙間に仕切り板を挿入する代わりに、仕切り板の隙間に○の群れを挿入する事を考えれば、左端の仕切り板の左と右端の仕切り板の右も隙間だと言う事にして、365個の隙間の中から○の群れを挿入すべきn'個を選ぶ組み合わせとして無計算で₃₆₅C_n'が求まる。
しかしまあ、計算力の大きさの展示、という観点から言うと、長々と計算した事にも意味があろう。
---
最終更新日時2011/02/04/10:59JST

図が同じでも、場合としては異なる、という事があるので、それぞれの図に対して、その図に何通りの場合が含まれているかをカウントしなくてはいけない。

例えば、ある図についてp(1)=3だとすると、第0隙と第1隙の間に3個の丸が入っている事に成るが、その3個の○が誰と誰なのか、という事が違えば、図が同じでも場合としては異なる。

つまり、一般には、同一の数列q=(q₁,・・・,q₃₆₅)に対応する数列a=(a₁,・・・,a_n)は複数個ある、という事だ。
---
最終更新日時2011/02/06/10:49JST

n人の中から第0隙と第1隙の間のp(1)人を選ぶ組み合わせの数は_nC_p(1)であり、
残りのn-p(1)人の中から第1隙と第2隙の間のp(2)人を選ぶ組み合わせの数は_n-p(1)C_p(2)であり、
・・・
残りのn-p(1)-・・・-p(n'-2)人の中から第n'-2隙と第n'-1隙の間のp(n'-1)人を選ぶ組み合わせの数は_{n-p(1)-・・・-p(n'-2)}C_p(n'-1)であり、
ここまでが既に選ばれていれば、第n'-1隙と第n'隙の間のp(n')人が誰と誰かは既に確定しているから、
1つの図に含まれる場合の数は、n'≧2の場合には、
_nC_{p(1) n-p(1)}C_p(2)・・・_{n-p(1)-・・・-p(n'-2)}C_p(n'-1)

この式は分数の約分によって少し簡単に成る。
_nC_{p(1) n-p(1)}C_p(2)・・・_{n-p(1)-・・・-p(n'-2)}C_p(n'-1)
= {n!/[p(1)!(n-p(1))!]}{(n-p(1))!/[p(2)!(n-p(1)-p(2))!]}・・・{(n-p(1)-・・・-p(n'-2))!/[p(n'-1)!(n-p(1)-・・・-p(n'-2)-p(n'-1))!]}
= n!/[p(1)!・・・p(n'-2)!p(n'-1)!(n-p(1)-・・・-p(n'-2)-p(n'-1))!]

n-p(1)-・・・-p(n'-2)-p(n'-1)=p(n')である事を使うと、この式は、
n!/[p(1)!・・・p(n')!]
とも書ける。

n'=1の場合には、p(1)=nだから、1つの図に含まれる場合の数は、
_nC_n = 1 = n!/p(1)!
---
最終更新日時2010/12/20/10:57JST

解答(その6)で予告されている様に、
(図の個数)×(各々の図に対応する場合の数)×(挙手者数)
を計算したい。

解答(その4)の結果より、
挙手者数 = n - Σ_j=1^n' δ_p(j),1
解答(その14)を書いている時に、解答(その5)は必要ない事を思い出しました。

解答(その10)の結果より、
図の個数 = ₃₆₅C_n'

解答(その12)の結果より、各々の図に対応する場合の数は、
n'≧2の場合には、
n!/[p(1)!・・・p(n')!]
n'=1の場合には、
n!/p(1)! = 1

したがって、(図の個数)×(各々の図に対応する場合の数)×(挙手者数)は、
₃₆₅C_n'{n!/[p(1)!・・・p(n')!]}[n - Σ_j=1^n' δ_p(j),1]
ただし、n'=1に対しては、p(1)!をp(1)!・・・p(n')!と書く事にした。
---
最終更新日時2010/12/21/10:45JST

解答(その6)で予告されている様に、
解答(その13)の結果を、n';p(1),・・・,p(n')について足し上げ365ⁿで割れば、
挙手者数の期待値が求まる。

(挙手者数の期待値) = (1/365ⁿ)Σ_n'=1³⁶⁵ ₃₆₅C_n' Σ_p {n!/[p(1)!・・・p(n')!]}[n - Σ_j=1^n' δ_p(j),1]　(n≧365)
(挙手者数の期待値) = (1/365ⁿ)Σ_n'=1ⁿ ₃₆₅C_n' Σ_p {n!/[p(1)!・・・p(n')!]}[n - Σ_j=1^n' δ_p(j),1]　(n≦365)

ただし、Σ_pは、
p(1) ≧ 1, ・・・, p(n') ≧ 1
p(1) + ・・・ + p(n') = n
を満たす全ての数列p=(p(1),・・・,p(n'))に渡っての和を表すものとする。

Σ_n'=1³⁶⁵ ₃₆₅C_n' Σ_p {n!/[p(1)!・・・p(n')!]}δ_p(j),1
も、
Σ_n'=1ⁿ ₃₆₅C_n' Σ_p {n!/[p(1)!・・・p(n')!]}δ_p(j),1
も、jに依存しない事は明らかだ。したがって、

(挙手者数の期待値) = (1/365ⁿ)Σ_n'=1³⁶⁵ ₃₆₅C_n' Σ_p {n!/[p(1)!・・・p(n')!]}[n - n'δ_p(n'),1]　(n≧365)
(挙手者数の期待値) = (1/365ⁿ)Σ_n'=1ⁿ ₃₆₅C_n' Σ_p {n!/[p(1)!・・・p(n')!]}[n - n'δ_p(n'),1]　(n≦365)
---
最終更新日時2011/02/13/10:48JST

解答(その14)のΣ_pを実行するために、Π₁(M,N)を次の様に定義する。

Π₁(M,N) ≡ Σ_p M!/[p(1)!・・・p(N)!]

ただし、Σ_pは、
p(1) ≧ 1, ・・・, p(N) ≧ 1
p(1) + ・・・ + p(N) = M
を満たす全ての数列p=(p(1),・・・,p(N))に渡っての和を表すものとする。

n'≧2の場合には、解答(その14)のδ_p(n'),1が絡む項は、δ_p(n'),1を取り除いて残りの部分にp(n')=1を代入する事によって計算できるので、次の様に成る。

Σ_p {n!/[p(1)!・・・p(n')!]}n'δ_p(n'),1 = Σ'_p {n!/[p(1)!・・・p(n'-1)!]}n'　(n'≧2)
ただし、Σ'_pは、
p(1) ≧ 1, ・・・, p(n'-1) ≧ 1
p(1) + ・・・ + p(n'-1) = n - 1
を満たす全ての数列p=(p(1),・・・,p(n'-1))に渡っての和を表すものとする。

n'=1の場合は、p(n')=nだから、
δ_p(n'),1 = δ_n,1
∴ Σ_p {n!/[p(1)!・・・p(n')!]}n'δ_p(n'),1 = δ_n,1　(n'=1)
これに合わせて、Π₁(M,0) = δ_M,0と定義しておく。

すると、解答(その14)の結果は、次の様に書き直される。
n≧365の場合には、
(挙手者数の期待値) = (1/365ⁿ)₃₆₅C₁ [nΠ₁(n,1) - δ_n,1]
　　+ (1/365ⁿ)Σ_n'=2³⁶⁵ ₃₆₅C_n' [nΠ₁(n,n') - n'Σ'_p{n!/[p(1)!・・・p(n'-1)!]}]
= (1/365ⁿ)Σ_n'=1³⁶⁵ ₃₆₅C_n' [nΠ₁(n,n') - n'nΠ₁(n-1,n'-1)] ∵ nΠ₁(n-1,0) = nδ_n-1,0 = nδ_n,1 = δ_n,1
= (n/365ⁿ)Σ_n'=1³⁶⁵ ₃₆₅C_n' [Π₁(n,n') - n'Π₁(n-1,n'-1)]
2≦n≦365の場合には、
(挙手者数の期待値) = (1/365ⁿ)₃₆₅C₁ [nΠ₁(n,1) - δ_n,1]
　　+ (1/365ⁿ)Σ_n'=2ⁿ ₃₆₅C_n' [nΠ₁(n,n') - n'Σ'_p{n!/[p(1)!・・・p(n'-1)!]}]
= (1/365ⁿ)Σ_n'=1ⁿ ₃₆₅C_n' [nΠ₁(n,n') - n'nΠ₁(n-1,n'-1)] ∵ nΠ₁(n-1,0) = nδ_n-1,0 = nδ_n,1 = δ_n,1
= (n/365ⁿ)Σ_n'=1ⁿ ₃₆₅C_n' [Π₁(n,n') - n'Π₁(n-1,n'-1)]
因みに、n≧365の場合も2≦n≦365の場合も、δ_n,1=0だから、n'=1の項のδ_n,1部分は不要だが、あった方が分かり易いので、書いておきました。
---
最終更新日2011/03/07/17:21JST

解答(その15)で定義されているΠ₁(M,N)を計算したい。
最初は数学公式を探したが見付からなかったので最も似ている数学公式の利用を考えた。

Π₀(M,N) ≡ Σ_p M!/[p(1)!・・・p(N)!]
ただし、Σ_pは、
p(1) ≧ 0, ・・・, p(N) ≧ 0
p(1) + ・・・ + p(N) = M
を満たす全ての数列p=(p(1),・・・,p(N))に渡っての和を表すものとする。

次式で表される数学公式を見付けた。
Π₀(M,N) = N^M
この公式は、(x₁+・・・+x_N)^Mの展開公式にx₁ = ・・・ = x_N = 1を代入する事によって、得られそうだ。

Π₀は、M≧N≧2の場合には、Π₁と次の関係式で結ばれる。
Π₀(M,N) = Π₁(M,N) + Σ_k=1^N-1 _NC_k Π₁(M,N-k)
この式は、Π₀(M,N)をp(1),・・・,p(N)の中のk個が0である場合毎に分けて書いたものと解すれば、了解される。
Π₁(M,N)の計算が目的だから、M≧Nの場合だけ考えればよい。

Π₀(M,N) = Π₁(M,N) + Σ_k=1^N-1 _NC_k Π₁(M,N-k)にΠ₀(M,N) = N^Mを代入する事によって、
Π₁(M,N) = N^M - Σ_k=1^N-1 _NC_k Π₁(M,N-k)　(M≧N≧2)
これはΠ₁(M,N)についての漸化式として使える。
---
最終更新日時2011/02/22/10:42JST

[Ctrl]ボタンを押したままマウスホイールを使うと本件を拡大して読む事が出来ます。

---

解答(その16)の漸化式を解いてΠ₁(M,N)を求めたい。

まず、直接の計算によって、M≧1では、
Π₁(M,1) = Σ_p(1)=M^M M!/p(1)! = 1

これを解答(その16)の漸化式に代入する事によって、M≧2では、
Π₁(M,2) = 2^M - ₂C₁ Π₁(M,1) = 2^M - 2

このΠ₁(M,2)の式と解答(その16)の漸化式を見くらべて、私は、M≧N≧2では、
Π₁(M,N) = Σ_k=2^N (-1)^N-k _NC_k (k^M - k)
だろう、という予想を立てた。

2≦k'≦N-1で Π₁(M,k') = Σ_s=2^k' (-1)^k'-s _k'C_s (s^M - s) だと仮定すると、N≧3では解答(その16)の漸化式の右辺は、
N^M - Σ_k'=1^N-1 _NC_N-k' Π₁(M,k')　(k' = N-k)
= N^M - N - Σ_k'=2^N-1 _NC_k' Σ_s=2^k' (-1)^k'-s _k'C_s (s^M - s)　∵_NC_N-k' = _NC_k'
ここで、Σによる2重和を取り出して考えると、和の範囲2≦s≦k',2≦k'≦N-1は、s≦k'≦N-1,2≦s≦N-1と書き表す事も出来るので、
Σ_k'=2^N-1 Σ_s=2^k' = Σ_s=2^N-1 Σ_k'=s^N-1
これを使って書き直すと、N≧3では解答(その16)の漸化式の右辺は、
N^M - N - Σ_s=2^N-1 Σ_k'=s^N-1 _NC_k' (-1)^k'-s _k'C_s (s^M - s)
さらに、r=k'-sと置くと、この式は、次の形に成る。
N^M - N - Σ_s=2^N-1 Σ_r=0^N-1-s _NC_r+s (-1)^r _r+sC_s (s^M - s)
ここで、
_NC_{r+s r+s}C_s = {N!/[(r+s)!(N-r-s)!]}[(r+s)!/(s!r!)] = N!/[(N-r-s)!s!r!]
　= {N!/[(N-s)!s!]}{(N-s)!/[r!(N-s-r)!]} = _NC_{s N-s}C_r
を使うと、N≧3では解答(その16)の漸化式の右辺は、
N^M - N - Σ_s=2^N-1 _NC_s (s^M - s) Σ_r=0^N-1-s (-1)^r _N-sC_r
ここで
0 = (1+x)^N-s|_x=-1 = Σ_r=0^N-s _N-sC_r (-1)^r = Σ_r=0^N-s-1 _N-sC_r (-1)^r + _N-sC_N-s (-1)^N-s
∴Σ_r=0^N-1-s (-1)^r _N-sC_r = - _N-sC_N-s (-1)^N-s = - (-1)^N-s
を使うと、N≧3では解答(その16)の漸化式の右辺は、
N^M - N + Σ_s=2^N-1 (-1)^N-s _NC_s (s^M - s) = Σ_s=2^N (-1)^N-s _NC_s (s^M - s)
これと解答(その16)の漸化式によって、N≧3では、
k'=NでもΠ₁(M,k') = Σ_s=2^k' (-1)^k'-s _k'C_s (s^M - s)だと分かる。
これで、2≦k'≦N-1でΠ₁(M,k') = Σ_s=2^k' (-1)^k'-s _k'C_s (s^M - s)が成り立つならばk'=NでもΠ₁(M,k') = Σ_s=2^k' (-1)^k'-s _k'C_s (s^M - s)が成り立つ事が示された事に成るので、数学的帰納法によって、N≧2なる全てのNに対してΠ₁(M,N) = Σ_k=2^N (-1)^N-k _NC_k (k^M - k)が成り立つ。
---
最終更新日時2011/02/26/09:39JST

解答(その15)のΠ₁(M,0) = δ_M,0と解答(その17)の結果
Π₁(M,1) = 1　(M≧1),
Π₁(M,N) = Σ_k=2^N (-1)^N-k _NC_k (k^M - k)　(M≧N≧2)
を解答(その15)の式に代入するために、
Π₁(n,n') - n'Π₁(n-1,n'-1)
を計算する。

n≧2,n'=1の場合には、
Π₁(n,n') - n'Π₁(n-1,n'-1) = Π₁(n,1) - Π₁(n-1,0) = 1 - δ_n-1,0 = 1 - δ_n,1 = 1

n≧2,n'=2の場合には、
Π₁(n,n') - n'Π₁(n-1,n'-1) = Π₁(n,2) - 2Π₁(n-1,1) = (2ⁿ - 2) - 2 = 2ⁿ - 4

n≧n'≧3の場合には、
Π₁(n,n') - n'Π₁(n-1,n'-1) =Σ_k=2^n' (-1)^n'-k _n'C_k (kⁿ - k) - n'Σ_k=2^n'-1 (-1)^n'-1-k _n'-1C_k (k^n-1 - k)
= n'ⁿ - n' + Σ_k=2^n'-1 (-1)^n'-k _n'C_k (kⁿ - k) - n'Σ_k=2^n'-1 (-1)^n'-1-k _n'-1C_k (k^n-1 - k)
= n'ⁿ - n' + Σ_k=2^n'-1 (-1)^n'-k [_n'C_k (kⁿ - k) + n' _n'-1C_k (k^n-1 - k)]
ここで
_n'C_k (kⁿ - k) + n' _n'-1C_k (k^n-1 - k) = (k _n'C_k + n' _n'-1C_k)k^n-1 - (_n'C_k + n' _n'-1C_k)k,
k _n'C_k + n' _n'-1C_k = kn'!/[k!(n'-k)!] + n'(n'-1)!/[k!(n'-1-k)!]
= kn'!/[k!(n'-k)!] + (n'-k)n'!/[k!(n'-k)!] = n'n'!/[k!(n'-k)!]
= n' _n'C_k,
_n'C_k + n' _n'-1C_k = n'!/[k!(n'-k)!] + n'(n'-1)!/[k!(n'-1-k)!]
= n'!/[k!(n'-k)!] + (n'-k)n'!/[k!(n'-k)!] = (n'-k+1)n'!/[k!(n'-k)!]
= (n'-k+1) _n'C_k
∴_n'C_k (kⁿ - k) + n' _n'-1C_k (k^n-1 - k) = n' _n'C_k k^n-1 - (n'-k+1) _n'C_k k = _n'C_k [n'k^n-1 + k² - (n'+1)k]
を使うと、n≧n'≧3では、
Π₁(n,n') - n'Π₁(n-1,n'-1) = n'ⁿ - n' + Σ_k=2^n'-1 (-1)^n'-k _n'C_k [n'k^n-1 + k² - (n'+1)k]
= Σ_k=2^n' (-1)^n'-k _n'C_k [n'k^n-1 + k² - (n'+1)k]
---
最終更新日時2011/02/28/10:04JST

宇田雄一著「古典物理学」138ページの「私は、因果律の意味②を少し広げて、ある時刻以前のすべての時刻における世界の状態が正確に決まれば、それより後の時刻の状態も正確に決まるという考え方だとする方が良いと思っている」という記述を思い出した。

a_n = f(n) が　n≦k で成り立てば n=k+1 でも成り立つ事を証明し、それによって a_n = f(n) が任意の n に対して成り立つ事を証明する私の方法は、
∀s≦n; a_s = f(s)
という命題を考え、これをe(n)で表せば、
命題 e(n) が n=k で成り立てば n=k+1 でも成り立つ事を証明し、それによって e(n) が任意の n に対して成り立つ事を証明する事に当たり、普通の数学的帰納法に帰着する。
---
最終更新日時2010/12/31/16:44JST