题目

桌上有十枚棋子,每次至少拿1枚,拿完为止,有多少种不同拿法?

提问时间：2021-03-12

答案

解法一（排列组合法）：
1次拿完方法数：1,
2次拿完方法数：相当于在10个元素间的9个空挡中插1个隔板,
C(9,1)=9.
3次拿完方法数：相当于在10个元素间的9个空挡中插2个隔板,
C(9,2)=36.
.
10次拿完方法数：相当于在10个元素间的9个空挡中插9个隔板,
C(9,9)=1.
总数C(9,0)+C(9,1)+C(9,2)+...+C(9,9)=2^9=512.
方法二（递推函数法）：
记桌上有n个棋子时,有f(n)种拿法,显然f(1)=1.
n>1时：
第1次拿1个的方法数,就是桌上有n-1个棋子时的拿法数f(n-1),
第1次拿2个的方法数,就是桌上有n-12棋子时的拿法数f(n-2),
.
第1次拿n-1个的方法数,就是桌上有1个棋子时的拿法数f(1),
第1次拿n个的方法数,等于1,
f(n)=f(n-1)+f(n-2)+...+f(1)+1,
f(n-1)=f(n-2)+...+f(1)+1,代入上式,得
f(n)=2f(n-1),
由f(1)=1,f(n)=2^(n-1).
f(10)=2^9=512.