Counting 問題

A "composition" of a positive integer n is a sequence s={s_1,s_2,...,s_k} of positive integers that Sum{s_i} =n.

Show that the number of compositions of n is 2^(n-1).

請問以上問題,除了數學歸納法外,有沒有其他方法可解決?

{ 當然希望是一些比較constructive的方法。 :) }

1 Answer

Rating
  • 1 decade ago
    Favorite Answer

    這樣的問題應該用【遞迴數列】的方式就可以吧!

    不需用【數學歸納法】

    【問題】已知 n 為正整數,而 n 拆解成數個正整數之和的方式有 F(n) 種方式(不同順序視為不同解),試證明 F(n) = 2^(n-1)。

    【範例】

    (1) n = 1 : 1 = 1 --> F(1) = 1。

    (2) n = 2 : 2 = 2 = 1+1 --> F(2) = 2。

    【解】

    (1) F(1) = 1 = 2^(1-1)、F(2) = 2 = 2^(2-1)

    (2) 當 n > 1 時,有 F(n) = 1 + [ F(1) + F(2) + .... + F(n-1) ]

    因為 n = n = (n-1) + { 1 } = (n-2) + { 2 } = (n-3) + { 3 } = .... = 1 + { n-1 }

    { k } 表示將 k 繼續進行拆解,則共有 F(k) 種方法。

    所以 F(n+1) - F(n)

    = ( 1 + [ F(1) + F(2) + .... + F(n-1) ] )

    - ( 1 + [ F(1) + F(2) + .... + F(n) ]

    = F(n)

    --> F(n+1) = 2*F(n) --> F(n+1) = 2*2*...*2*F(2) = 2^n

    (3) 由 (1)、(2) 可知若 n 為正整數,則 F(n) = 2^(n-1)。

    2009-11-04 19:34:03 補充:

    (2) 的部份也可以這樣思考:

    定義 { n | (s_1,s_2,...,s_k) } 表示 n 的所有正整數的有序拆解,

    以及 # { n | (s_1,s_2,...,s_k) } = F(n)

    2009-11-04 19:34:10 補充:

    則當 n > 1 時:

    F(n) = # { n | (s_1,s_2,...,s_k) }

    = #{ n | (s_1,s_2,...,s_k), s_1 = 1 } + #{ n | (1+s_1,s_2,...,s_k) ,s_1 > 1}

    = #{ n-1 | (s_2,...,s_k) } + #{ n-1 | (s_1,s_2,...,s_k) }

    =F(n-1) + F(n-1) = 2*F(n-1)

    所以 F(n) = 2*F(n-1) = 2*2*...*2*F(1) = 2^(n-1)

    2009-11-04 20:50:02 補充:

    另外一個比較直接的方式,是利用【排列組合】的概念。

    定義 F(n,k) 表示 n = s_1 + s_2 + ... + s_k 的正整數解個數,令 t_i = s_i -1 ,則:

    因為 s_1 + s_2 + ... + s_k = n

    --> (t_1+1) + (t_2+1) + ... + (t_k+1) = n

    --> t_1 + t_2 + ... + t_k = n-k

    也就是 F(n,k) 為 t_1 + t_2 + ... + t_k = n-k 的非負整數解個數

    2009-11-04 20:51:28 補充:

    所以 F(n,k) = H(k,n-k) = C(n-1,n-k) = C(n-1,k-1)

    這樣就得到

    F(n) = F(n,1) + F(n,2) + ... + F(n,n)

    = C(n-1,0) + C(n-1,1) + ... C(n-1,n-1)

    = 2^(n-1)

    【備註】H(m,n) 表示 < 重複組合數 >、C(m,n) 表示 < 組合數 >

    Source(s): 自己
Still have questions? Get your answers by asking now.