前天上離散的最後一題是:
爬八階樓梯，每次可爬1或2或3階的方法數為何
我那時候第一個想到的解法是，整數解個數
也就是很像老師之前有上的一題:
x+2y+3z=20的整數解個數
不過這顯然是組合問題
所以我把原本的生成函數改成指數生成函數，變成
(e^x)(e^x e^-x/2)(1+x/3!+x/6!...)
(也就是很像老師上課講的含偶數個0的序列有幾種)
我想問的是
(1)這一題這樣解可以嗎?想法是否有錯誤
(因為我不知道1+x/3!+x/6!...的公式，沒辦法驗算)
(2)像x+2y+3z=20這個問題是否可以用遞迴去解，
因為用暴力法展開很繁瑣(遞迴的列表暴力法比較好作)
還是，遞迴只能解排列，不能解組合
6 則留言:
因為我覺得第一次走2階之後都走1階和最後一次走2階之前都走1階是不一樣的, 所以我當是排列，我算的答案是 81，和窮舉法算出來一致，你可以用遞迴而且不用算出 a_n 通式, 只需利用遞迴關係加上初始值算出 a_8; 也可以用生成函數(非指數)取 x^8 的係數, 不過前者比較快，整數解個數用不上，因為我當它是排列。
謝謝您抽空解答,感恩
你用生成函數解，我覺得是錯的，因為假設一步的走一次，兩步的走兩次，三步的走一次，這樣的方法數應該是4!/2!；但你如果用生成函數去求，它會是8!/(1!*4!*3!)，所以不match。
你可以用遞迴an=a(n-1)+a(n-2)+a(n-3)，初始條件a0=1,a1=1,a2=2，算出來的答案應該是81，(我有嘗試去解an不過我發現特徵方成的根不好解，所以還是一步一步遞迴，比較實在)。
這一題應該是要先組合，然後再排列的問題，比方說x+2y+3z=8，解出x=1,y=2,z=1，你如果把它想成是組合問題，解只有一種，這樣會少算很多，因為它有可能是先走一步的，再走兩步的，最後是三步的；也有可能先走三步的，再一步的，最後兩步的，等等下去，應該要把它想成是排列問題，方法數應該是4!/2!，所以我覺得不適合用生成函數解，如果硬要用整數解去解的話，你應該分項討論，其實也不會很難。
首先; 整數解是沒辦法解的, 因為你不知道你算出來的解一樣的數字有幾個, 雖然先求組合解再求排列的想法並沒有錯, 但是這是不可行的(對general case).
再來; 討論生成函數, 先告訴大家答案
Σ_{n=1}^8(x+x^2+x^3)^n.
(sum from n=1 to n=8)
我不知道這是不是屬於一般離散數學的範圍, 想法是這樣, 先固定走的次數(就是次方n), 比如走一次, 那可以是 1,2 or 3階共三種, 所以生成函數就是(x+x^2+x^3), 走兩次的話, 有1+1, 1+2, 1+3, 2+1, 2+2, 2+3, 3+1, 3+2, 3+3 共九種, 生成函數是 (x+x^2+x^3)^2, 依此類推, 這樣的思路是固定次數, 可是由於我們要的是固定總和, 所以以固定次數的方式累加每一種可能. 要走到 8 階至多走八次, 所以加到 8 次方 就夠了. 有時間的人可以驗證看看.
另外; 這個是可以推廣的, 以此題來說假設階梯數是 n, 可以走 1,2,3,...,m 階, 那麼生成函數就是
Σ_{n=1}^∞(Σ_{i=1}^m x^i)^n.
最後給的生成函數中的 n 是 index 不是階梯數, 改成 k 會好一點. 所以方法數是 x^n 的係數.
張貼留言