遞推計數法

1. 一個樓梯有10個台階. (1) 如果每步可以跨一個或兩個台階, 共有多少種上樓梯的方法? (2) 如果每步可以跨一個, 兩個, 或三個台階, 共有多少種上樓梯的方法?

2. 一條直線把一個平麵分成２個部分；兩條直線最多把平麵分成４個部分；三條直線最多把平麵分成幾個部分？Ｎ條直線最多把平麵分成幾個部分？

3. 一個平麵把空間分成２個部分；兩一個平麵最多把空間分成４個部分；三個平麵把空間分成幾個部分？Ｎ個平麵把空間分成幾個部分？

4. Catalan 數。在一個n × n的方格上，要從左下角走到右上角，沿著格子邊向右或者向上走，但不能跨過整個正方形從左下角到右上角的對角線。請問，一共有多少條路線？

5. 在一所學校裏長長的走廊裏，有一排編號為1到999的箱格（Lockers）。箱子都是關著的。一個無聊的學生，從一端走到另一端，把關著的箱子隔一個打開一個：打開一號箱，留下二號箱；打開三號留下四號，直到另一端，然後，又掉過頭來，打開一個留下一個。請問，最後被打開的那個箱子是幾號？