递推计数法

1. 一个楼梯有10个台阶. (1) 如果每步可以跨一个或两个台阶, 共有多少种上楼梯的方法? (2) 如果每步可以跨一个, 两个, 或三个台阶, 共有多少种上楼梯的方法?

2. 一条直线把一个平面分成２个部分；两条直线最多把平面分成４个部分；三条直线最多把平面分成几个部分？Ｎ条直线最多把平面分成几个部分？

3. 一个平面把空间分成２个部分；两一个平面最多把空间分成４个部分；三个平面把空间分成几个部分？Ｎ个平面把空间分成几个部分？

4. Catalan 数。在一个n × n的方格上，要从左下角走到右上角，沿着格子边向右或者向上走，但不能跨过整个正方形从左下角到右上角的对角线。请问，一共有多少条路线？

5. 在一所学校里长长的走廊里，有一排编号为1到999的箱格（Lockers）。箱子都是关着的。一个无聊的学生，从一端走到另一端，把关着的箱子隔一个打开一个：打开一号箱，留下二号箱；打开三号留下四号，直到另一端，然后，又掉过头来，打开一个留下一个。请问，最后被打开的那个箱子是几号？