[其他] 組合數學一問

[znmkhxrw (QQ)]

在導多變數泰勒展開式的係數時觀察到某個式子(後述)必須要成立

但是直接驗證那式子對不對發現好困難...但是帶入某些數字驗算都是對的

想請問一下有沒有辦法直接證出下面這個式子：

----------------------------------------------------------------

Let n,k€N(natural numbers)

and S:= {(x_1,...,x_n)│x_1+...+x_n = k, x_i nonnegative integer}

                                k!
Define f：S → N by f(x) = ────────
                           x_1!x_2!...x_n!


Prove that  Σ  f(x) = n^k
           x€S

--------------------------------------------------------------
                                                             n
S集合的個數其實就是x_1+...+x_n = k的非負整數解的個數，也就是H
                                                             k

f(x)就是x的排列方法數，舉例來說 k=4, n=3, 其中一組解(2,1,1)

x_1 + x_2 + x_3 = k

 2     1     1

f(x)=4!/(2!1!1!)= 12 就是以下這12種排列方式(以a代表x_1,b代表x_2,c代表x_3)


aabc abac abca aacb acab acba

baac baca bcaa

caab caba cbaa


謝謝幫忙！



--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.227.0.48
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1472480093.A.B54.html
※ 編輯: znmkhxrw (36.227.0.48), 08/29/2016 22:16:17
→ arthurduh1  : 就是二項是定理的推廣
→ arthurduh1  :         *式
→ arthurduh1  : f(x) 是 (z_1+z_2+...+z_n)^k 中
→ arthurduh1  : z_1^{x_1} z_2^{x_2} ... z_n^{x_n} 之係數
→ arthurduh1  : k!想成是把 x_i 個 z_i 全部拿來作排列，且每個
→ arthurduh1  : z_i 都視作不同；分母除掉的就是 x_i 個 z_i 的
→ arthurduh1  : 內部排序
→ arthurduh1  : google: Multinomial Theorem
看懂了!! 之前都在用2項式沒反應過來這個XDD

感謝你幫忙！
※ 編輯: znmkhxrw (36.227.0.48), 08/29/2016 22:26:38