小明上樓梯

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

方法1：

如果小明用1步走完樓梯，明顯只有一種方法，就是一步誇100級。

如果小明用2步走完樓梯，他必須在中間的99級樓梯中選擇一級踏上，所以共有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種方法行上樓梯。

方法2：

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