カウンタ

COUNTER FROM 2016031871846

日誌

確率論及統計論 >> Article details

2016/03/18

第I章 数学的補助手段  1 組合わせの理論

Tweet ThisSend to Facebook | by kaizen
伏見康治「確率論及統計論」輪講  第0回 20160408@Nagoya O.K., K.H.
20160513@Nagoya O.K., S.K.
#で始まる行は輪講で付け加えた行
担 当・目次(wikiに連携)
第I章 数学的補助手段
 1 組合わせの理論wiki:組合わせ(数学))<小川清>
 2 母函数wiki:母関数)<担当未定・資料作成中>
 3 漸近展開(wiki:漸近展開)<担当未定・資料作成中>
 4 自然数の分割数自然数(分割数)<担当未定・資料作成中>
 5 結晶内原子配列に関する秩序無秩序の問題(結晶構造)(秩序変数)<担当未定・資料作成中>
 6 命題算、集合算(命題論理)<担当未定・資料作成中>

第I章 数学的補助手段
「理論上の問題では組み合わせ理論の範囲内で物事が処理されて、確率の言葉で述べる必要のないことが多い」p.3

 節1 組合わせの理論 *1
「実際多くの組み合わせの定理が確率論の命題として自然にでてくる」p.3

「諸公式を樹てる時の原則は、Aがm通り、Bがn通り起きれば、
(1) AかBが起る数は   m+n    (1.0)
(2) AとBとが起る数は  m X n  (1.0a)
通りであると云う2つに限る」p.3

「(1)順列:異なるn個のものを異なるn個の場所に配置する数Pnは
P_n=1 \cdot 2 \cdot \cdots \cdot n = n!,  \cdots (1.1)
P_n=1 \cdot 2 \cdot \cdots \cdot n = n!, (1.1) 
である。」

# n!はnの階乗と呼ぶ。P: Permutation
P_n = n \cdot P_{n-1} ¥cdots (1.2)
P_n = n \cdot P_{n-1} ¥cdots (1.2)

#式に・を付け加えた

漸化式(ぜんかしき)

#漸化式のありがたみ。係数がどんどんちいさくなるので、最後に1または0になり、式は有限で終わる。書き下すことが可能。値が有限であることは保証しない。

P_1 = 1は瞭か」p.4

#1!=1だから。

#表をここに入れる。描きは暫定
\frac{n,1,2,3,4,5,6,7,8,9,10}{n!,1,2,6,24,120,720,5040,40320,362880,3628800}
\frac{n,1,2,3,4,5,6,7,8,9,10}{n!,1,2,6,24,120,720,5040,40320,362880,3628800}      (1.2a)

「52枚のカードを並べる仕方は8.065... X 10^{47}

「限られた大きさの鍵で幾通りの異なるものが作られるかと云う様な実際問題で重要な意義を持つ」p.4

n! = (n-1)(n-1)!+(n-2)(n-2)!+・・・1・1! +1 (1.3)

#証明始
# n! = \mathrm{P}_n   = 1・2・3・・・n             公式(1.1)より
# = (1・2・3・・・) ・n = \mathrm{P}_{n-1}  \cdot n = n ¥cdot \mathrm{P}_{n-1}   
#   = (n-1 + 1) \mathrm{P}_{n-1}  = (n-1) \mathrm{P}_{n-1}  +  \mathrm{P}_{n-1} 
#  = (n-1)(n-1)! + \mathrm{P}_{n-1}    (1.3a)
#ここで2項目を見ると、最初の式の-1番目のものであるので、同様に展開できることがわかる。そうすると(1.3)になる。
#証明終

#n!はすぐにばかでかくなるが、計算式を展開してnが小さくなったり、階乗以外の形にかきくだせれれば、解が意味のある大きさになる。
#計算可能性の、有限時間での計算可能問題との共通点に注目。
#意味のある時間以内に計算できるかどうか。


(2)順列、等しいものがある場合。n個のものの内n1個は互いに等しく、n2個も互いに等しく、・・・(n1+n2+・・・+nv=n)ある場合、n個の場所へ並べる仕方の数は
 P_{n_1n_2{¥cdots}n_{¥gamma}}\frac{n! } {n_1! n_2! \cdots n_{¥gamma}! }      (n=n_1+n_2+・・・+n_{¥gamma})  (1.4)
である。」p4

# 分母はn個の順列。分子はそれぞれの同じものの相互の順列は階乗。その分を余分に計算しているので同じものの数の順列でそれぞれ割る。


(3)  順列,場所の数が物の数より小さいとき。 n個の異なるものから、m個を選んでm個の場所へ配置する仕方の数は
n(n-1) ・・・(n-m+1) = \frac{n! } {(n-m)! }         (1.5)
」p5

#具体例で検討
# 10個から5つの場所にならべる = 10・9・8・7・6
#になる。10-5は5だが、最後の場所の値は6。n-m+1と書く。
#逆算 n-m+1 - n = m+1 。両端を含む場合は、+1だという説明をどこかで探す
#一方の端だけを含む計算がn-m。


(4) 組合せ n個の異なるものからm個のものを選び出す数は(3)の場合の配置の区別がないから
{}_n\mathrm{C}_m  =  \frac{n! } {m! (n-m)! }  = \begin{pmatrix} n \\ m \end{pmatrix} ¥cdots (1.6)
{}_n\mathrm{C}_m  =  \frac{n! } {m! (n-m)! }  = \begin{pmatrix} n \\ m \end{pmatrix} ¥cdots (1.6)


#Cはconbination
#右式は、二項分布の二項係数
#(1.5)の式で、n個のものからm個を選んで並ぶ数から出発する。
#m個のものの順番はどうでもいいので、m!で割る。これは、m個のものが等しいものであったことと同等。
# 組み合わせを、順列を考えて、その後ですべてが同じものだとしたときと同様に選んだものの順列がどの順番でもよいので割るという形で展開していると理解するとよい。


\begin{pmatrix} n \\ m \end{pmatrix} \begin{pmatrix} n-1 \\ m-1 \end{pmatrix} \begin{pmatrix} n-1 \\ m \end{pmatrix}  (1.7)


#右辺の第一項は、或る特定のものを選んだ場合で、その組み合わせの数はn-1個からm-1個を選び出す数。
#右辺の第二項は、或る特定のものを選んでいない場合で、その組み合わせの数はn-1個からm個を選び出す数。
#左辺から右辺を導出するのは難しそう。右辺から左辺を導出してみる。

#証明始
\begin{pmatrix} n-1 \\ m-1 \end{pmatrix} + \begin{pmatrix} n-1 \\ m \end{pmatrix}   =\frac{(n-1)! } {(m-1)! ((n-1)-(m-1))! }+   \frac{(n-1)! } {m! ((n-1)-m)! }
#第一項下辺右の括弧をはずし上下にmをかける。第二項の上下に(n-m)をかける。
=\frac{m(n-1)! } {m(m-1)! (n-m)! }+   \frac{(n-m)(n-1)! } {m! ((n-1)-m)! (n-m)}
#第一項でm(m-1)! はm!, 第二項で((n-1)-m)!(n-m) は(n-m)!
=\frac{m(n-1)! } {m! (n-m)! }+   \frac{(n-m)(n-1)! } {m! (n-m)! }
#分母が同じになったので、分子の加算をすると
\frac{n! } {m! (n-m)! }\begin{pmatrix} n \\ m \end{pmatrix} 
#証明終

#参考
 # ( n, m) = ((n-1)+1,(m-1)+1) = (n-1, (m-1)+1) + (? ,(m-1)+1) + ((n-1)+1,m-1) + ((n-1)+1,?)
= .....左辺の展開で書こうとするとうまくかけない。


(5) 分割. n個の等しいものを,m個の異なる場所に分割配置する仕方の数(但し同じ場所にいくつ入ってもよい)は
 {}_n\mathrm{N}_m    =\begin{pmatrix} n-1 \\ m-1 \end{pmatrix}                (1.8)

  

#分割が、なんでここに出てくるのか良く分からない。
#他の文献では、母函数、漸化式が出てからの場合がある。

#「証明」の記述の場合分けで「1つしかものが入っていない場合」と、「1つ以上入る場合」という表現がある。1つと「2つ以上入る場合」の意味と理解。


{}_n\mathrm{N}_m    = {}_{n-1}\mathrm{N}_{m-1}     + {}_{n-1}\mathrm{N}_m     (1.8a)

#証明始
{}_n\mathrm{N}_m    =\begin{pmatrix} n-1 \\ m-1 \end{pmatrix}                (1.8)から
\begin{pmatrix} n-2 \\ m-2 \end{pmatrix} + \begin{pmatrix} n-2 \\ m-1 \end{pmatrix}       (1.7)から
={}_{n-1}\mathrm{N}_{m-1}  + {}_{n-1}\mathrm{N}_m  
#証明終

#この式に番号がなかったので(1.8a)とする。
#右辺第一項は、第一の場所に一つだけ入っている場合。第二項は、すでに一つ入れておいて、それ以外の場合を網羅した場合。すでに一つ入れているのでn-1が前提。


(6) P_{n_1 n_2 \cdots n_{\gamma}}に対する漸化式 


P_{n_1 n_2 \cdots n_{\gamma}}P_{n_2 \cdots n_{\gamma}}\sum^{n_1}_{m=1}\begin{pmatrix} n-n_1+1 \\ m \end{pmatrix} \begin{pmatrix} n_1 -1 \\ m-1 \end{pmatrix}  (1.9)

P_{n_1 n_2 \cdots n_{\gamma}}P_{n_2 \cdots n_{\gamma}}\begin{pmatrix} n \\ n_1 \end{pmatrix}                 (1.9a)

\begin{pmatrix} n \\ n_1 \end{pmatrix}  =  \sum^{n_1}_{m=1}\begin{pmatrix} n-n_1+1 \\ m \end{pmatrix} \begin{pmatrix} n_1-1 \\ m-1 \end{pmatrix}     (1.10)


(7) 繰り返しを許す組合わせ
異なるn種類のものが夫々無限にあるとし、これ等からm個を取出す仕方の数は
{}_n\mathrm{C'}_m     = \begin{pmatrix} n+m-1 \\ m \end{pmatrix}                         (1.11)

#なぜここでCに’をつけたのか?


{}_n\mathrm{C'}_m    {}_{n+m-1}\mathrm{C}_m     = \begin{pmatrix}  n+m - 1 \\  m \end{pmatrix}                    (1.11a)


#ここの操作の意味がまだ理解できていない
#この式に番号がなかったので(1.11a)とする。

(8) 異なるn種の無限個からm個を選んで,m個の異なる場所へ夫々一つ宛配置する仕方の数は
         n^m                       (1.12)



(9) 異なるn個のものを, 1個づつ含むm1個の組に,2個づつ含むm2個の組みに, ・・・,k個づつ含むmk個の組みに分割する仕方の数は
¥frac{n! } {m_1! m_2! (2!)^{m_2}¥cdots m_k!(k!)^{m_k}  }                     (1.13) 




C_m(n_1,n_2,\cdots, n_v) = \sum^{n_1}_{k=0}{C_{m-k}(n2,\cdots,nv)}  (1.14)

  C_m (n_1,n_2,\cdots, n_v) = \sum^{n_1}_{k_1=0}\sum^{n_2}_{k_2=0}\cdots\sum^{k_{v-1}}_{k_{v-1}=0}{C_{m-k - \cdots - k_{v-1}}(n_v)  (1.14a)

k_1 + k_2 + \cdots + k_{¥gamma} = m                  ( k_{¥mu} = 0,1,¥cdots,n_{¥mu})      (1.15)  


(k_1 + 1) + (k_2 + 1) + ¥cdots + (k_{¥gamma} + 1 ) = m + ¥gamma         (1.15a)

\begin{pmatrix}  m+ ¥gamma -1 \\  ¥gamma -1 \end{pmatrix} = ¥begin{pmatrix} m + ¥gamma -1 ¥¥  m ¥end{pmatrix}               (1.15b)

\begin{pmatrix}  k_m \\  ¥gamma_m \end{pmatrix}   ¥begin{pmatrix} k_{m-1} + ¥gamma_m ¥¥  ¥gamma_{m-1} ¥end{pmatrix} ¥cdots  ¥begin{pmatrix} k_1 - ¥gamma_2 - ¥cdots - ¥gamma_m¥¥  ¥gamma_1  ¥end{pmatrix} (1.15c)

C_m (n_1 n_2 \cdots n_{\gamma}) = \sum_{r_1 + 2r_2 + \cdots + mr_m =m}  \begin{pmatrix} k_m \\ \gamma_m \end{pmatrix} \begin{pmatrix}k_{m-1} - \gamma}_m \\ r_{m-1 \end{pmatrix} \cdots \begin{pmatrix} k_1 - r_2 - \cdots - r_m \\ r_1 \end{pmatrix} (1.16)

r_1 + 2r_2 + ¥cdots + mr_m = m (r_{¥mu} = 0,1,¥cdots) (1.16a)

「例:不完全気体の統計力学」
I_n = ¥int W_n (q_1 q_2 ¥cdots q_n) dq_1 dq_2 ¥cdots dq_n          (1.17)

W_n  = W_{n_1}  ¥cdot W_{n_2} ¥cdots            (1.17a)

W_n(q_1) = W(q_1)W(q_2) ¥cdots W(q_n)              (1.17b)
 
W_1(q_1) = U_1(q_1), W_2(q_1,q_2) = U_2(q_1,q_2) + U_1(q_1) U_1(q_2), W_3(q_1 q_2 q_3) = U_3(q_1 q_2 q_3) + U_2(q_2 q_3)U_1(q_1) + U_2(q_3 q_1) U_1(q_2) + U_2(q_1 q_2)U_1(q_3) + U_1(q_1) U_1(q_2) U_1(q_3) ¥cdots                          (1.18)
 
J_{¥gamma} = ¥int U_{¥gamma} (q_1, ¥cdots, q_{¥gamma}) dq_1 ¥cdots dq_{¥gamma}    (1.19)   

In = ¥int W_n dq_1 ¥cdots dq_n = ¥sum ¥int U_1(q_1)U_1(q_2) ¥cdots U_2(q_{¥alpha} q_{¥beta}) U_2(q_{¥gamma} q_{¥delta} ¥cdots dq_1 ¥cdtos dq_n 
     (1.19a)



J_1^{n_1} J_2^{n_2} J_3^{n_3} ¥cdots            ( n_1 + 2n_2 + 3n_3 + ¥cdots = n)           (1.19b)


I_n = ¥sum_{¥sum s_s = n} ¥frac{n! J_1^{n_1} J_2^{n_2} ¥cdots}{n!(1!)^{n_1} n_2!(2!)^{n_2} ¥cdots}              (1.20)

U_2(q_1 q_2) = W_2(q_1 q_2) - W_1(q_1) W_1 (q_2) ,
U_3(q_1 q_2 q_3) = W_3(q_1 q_2 q_3) - W_2(q_2 q_3) W_1(q_1) - W_2 (q_3 q_1) W_1(q_2)
 - W_2(q_1 q_2) W_1(q_3) + 2W_1(q_1) W_1(q_2) W_1(q_3) ,

¥cdots                  (1.21)
#原文。先頭行の最後のW2はW1の誤植。

#証明始
U_3(q_1 q_2 q_3) = W_3(q_1 q_2 q_3) - U_2(q_2 q_3) U_1(q_1) - U_2 (q_3 q_1) U_1(q_2)
 - U_2(q_1 q_2) U_1(q_3)  - U_1(q_1) U_1(q_2) U_1(q_3)
 = W_3(q_1 q_2 q_3) - (W_2(q_2 q_3)- W_1(q_2)W_1(q_3))  W_1(q_1) - (W_2 (q_3 q_1)- W_1(q_3)W_1(q_1)) W_1(q_2) 

 -( W_2(q_1 q_2) - W_1(q_1)W_1(q_2)) W_1(q_3) - W_1(q_1) W_1(q_2) W_1(q_3)

 = W_3(q_1 q_2 q_3) - W_2(q_2 q_3)W_1(q_1) + W_1(q_2)W_1(q_3) W_1(q_1) - W_2 (q_3 q_1)W_1(q_2)+ W_1(q_3)W_1(q_1) W_1(q_2) 
 - W_2(q_1 q_2)W_1(q_3) + W_1(q_1)W_1(q_2) W_1(q_3) - W_1(q_1) W_1(q_2) W_1(q_3)
= 右辺式
#証明終

担 当・目次(wikiに連携)
第I章 数学的補助手段
 1 組合わせの理論wiki:組合わせ(数学))<小川清>
 2 母函数wiki:母関数)<担当未定・資料作成中>
 3 漸近展開(wiki:漸近展開)<担当未定・資料作成中>
 4 自然数の分割数自然数(分割数)<担当未定・資料作成中>
 5 結晶内原子配列に関する秩序無秩序の問題(結晶構造)(秩序変数)<担当未定・資料作成中>
 6 命題算、集合算(命題論理)<担当未定・資料作成中>
13:54 | Impressed! | Voted(0) | Comment(0)