Re: [其他] 離散學的考古題

[Honor1984 (希望願望成真)]

※ 引述《JumjumpTiger (維尼維尼吃蜂蜜)》之銘言：
: 大家好 因為姊姊最近要考試了
: （她讀數學系研究所）
: 被其中一題證明題難住了想上來問問板上的大家有沒有人知道該用什麼方法證明呢？
: http://i.imgur.com/7SZGsMa.jpg
: 謝謝大家><

令a = min{k, n-k}

這一題應該是假設k >= n-k

也就是a = n-k


[C(n,k)]^2


         a
= C(n,k)ΣC(n-a, k-j)C(a, j)
        j=0


   a      n!         (n-a)!          a!
= Σ ---------------------------------------
  j=0  k! (n-k)! (k-j)!(n-a-k+j)! (a-j)!j!


  n-k      n!           k!          (n-k)!
= Σ ---------------------------------------
  j=0  k! (n-k)!    (k-j)!j!    (n-k-j)! j!


  n-k            n!
= Σ -----------------------------------
  j=0    (k-j)! (n-k-j)! j! j!

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.249.186.26
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1488119884.A.AE1.html
※ 編輯: Honor1984 (111.249.186.26), 02/26/2017 22:57:10
推 LPH66       : 由和式的對稱性, 不需要 k >= n-k 也是對的
→ LPH66       : 只是上限就要改成 min(k,n-k) 就是了
→ Honor1984   : 如果是k <= n - k，被加函數就變不出j!(n-k-j)!
推 LPH66       : 呃, 所以我沒說是從原證明改啊..就只是由對稱性而已
→ LPH66       : 然後我有點覺得交換 k 和 n-k 就是 k<=n-k 的證明了