宏東 發問於 科學及數學數學 · 1 十年前

怎樣證明組合數一定是正整數?

nCm=nPm/m!=n!/((n-m)!*m!)

有一個問題:

設n,m是正整數, 且n大於m, 怎樣證明n!/((n-m)!*m!)一定也是正整數?

2 個解答

評分
  • 1 十年前
    最愛解答

    Let P(n) be the proposition that

    C(n,m) are all integers for all positive integers n where 0 <= m <= n

    P(1) is obviously true since

    C(1,0) = 1; and C(1,1) = 1 are all integers

    Assume P(k) is true, that is,

    C(k,0), C(k,1), C(k,2) ... ,C(k,k) are all integers

    Then

    For 0 <= m <= k

    C(k+1,m) = (k+1)! / [(k+1 - m)! m!]

    = {k! / [(m - 1)! (k - m)!]}{(k+1) / [m(k + 1 - m)]}

    = {k! / [(m - 1)! (k - m)!]}[1/m + 1/(k +1 - m)]

    = k! / [m! (k - m)!] + k! / [(m - 1)! (k +1 - m)!]

    = C(k, m) + C(k, m-1) is an integer

    Also C(k+1,k+1) = 1 is integer

    Therefore C(k+1,m) is integer for 0 <= m <= k + 1 => P(k+1) is true

    So inductively, P(n) is true for all positive integers n

  • 1 十年前

    用 induction,用 Pascal triangle。

還有問題嗎?立即提問即可得到解答。