數學題︰小明有多少種方法上樓梯?

數學題︰小明有多少種方法上樓梯?
Photo Credit: Eddie Keogh / AP Photo / 達志影像
我們想讓你知道的是

如果容許小明跨級上樓梯,他有多少種方法?

史丹福回家時時常要行上很長的樓梯,有一次就忽發奇想地想到一條很有趣的數學問題。假如小明要行上一道100級的樓梯,他可以每次最少行上1級,但他也可以跨步,由於他的腿真的很長,他最多可以一次跨100級。他有多少種方法去行上這道100級的樓梯?

Ledder
圖片由作者提供

方法1︰

  • 如果小明用1步走完樓梯,明顯只有一種方法,就是一步跨100級。
  • 如果小明用2步走完樓梯,他必須在中間的99級樓梯中選擇1級踏上,所以共有99C1種方法。
  • 如果小明用3步走完樓梯,他必須在中間的99級樓梯中選擇2級踏上,所以共有99C2種方法。
  • 如果小明用4步走完樓梯,他必須在中間的99級樓梯中選擇3級踏上,所以共有99C3種方法。
  • 如此類推,如果小明用100步走完樓梯,他必須在中間的99級樓梯中選擇99級踏上,所以共有99C99種方法。

最後答案就是「1 + 99C1 + 99C2 + 99C3 + … + 99C99」。這條式要怎麼計算呢?

根據二項式定理(Binomial theorem)︰(1+x)n = 1 + nC1 x + nC2 x2 + nC3 x3 + … + nCn xn
代入x =1,我們就得到︰1 + nC1 + nC2 + nC3 + … + nCn = 2n
再代入 n = 99,我們就得到︰1 + 99C1 + 99C2 + 99C3 + … + 99C99= 299
所以小明共有299種方法行上樓梯。

編按︰此處的nCk代表從n個元素抽k個元素出來時,所構成的可能組合數量(假如元素一樣、排序不同,仍視為相同組合)。例如99C13就代表從99個元素之中抽13個出來的組合數量,用上樓梯的例子來說,就是從99級樓梯中選取其中13級出來,總共有99C13種方法。公式如下(詳見《維基百科》相關條目)︰

Screenshot-2018-5-21_組合_-_維基百科,自由的百科全書

方法2︰
第一個方法已經很精彩了,但思路清晰的朋友也許會想到一個更簡潔美麗的方法,小明可以選擇踏上或者不踏上第一級,可以選擇踏上或者不踏上第二級,可以選擇踏上或者不踏上第三級,如此類推,他最後可以選擇踏上或者不踏上第99級,所以他自然有299種方法行上樓梯。

編按︰方法2可以理解成把每一種上樓梯的方式編碼,寫成一個長達99位的數字串,這個數字串只有0和1組成,如果小明上樓梯的方式會踏上第n級樓梯,對應的數字串第n個位就會是1,否則為0。全部99個位皆是0的數字串「000...000」,對應「一步跨100級」的方法;所有位都是1的數字串「111...111」則對應「逐級走上去」的方法。由於每個數字串均對應一種上樓梯方法,反之亦然,總共有299個數字組合,因此答案是299

本文獲授權轉載,原文見史丹福狂想曲

相關文章︰

責任編輯︰鄭家榆
核稿編輯︰王陽翎

或許你會想看
更多『評論』文章 更多『生活』文章 更多『史丹福』文章
Loader