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

1个回答

  • 解法一(排列组合法):

    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.