编号 1～10 球放入编号 1～10 箱子，i 号球只能放入 ≤i 号箱子，求有一空箱的放法数

luyuanhong

这是台湾网友 YAG 发表在“陆老师的《数学中国》园地”的一个帖子，

欢迎大家一起来想想如何解答：

fungarwai

2^10-11=1013



这数列又出现了！

第一次是更短的组合数等幂和



第二次是田忌赛马

fungarwai

设有n+1个箱子x[1],x[2],x[3],...,x[n],x[n+1]
n个箱子恰有1个空的方法有a(n)个
在x[1],x[2],x[3],...,x[n]恰有1个空时，x[n+1]放第n+1个球，有a(n)个方法
用第n+1个球补上x[1],x[2],x[3],...,x[n]中的1个空，此时x[n+1]空，有a(n)个方法
在x[1],x[2],x[3],...,x[n]没有空时，把第n+1个球放在其中一个箱，空出x[n+1]，有n个方法
a(n+1)=2a(n)+n,a(1)=0
a(n+1)+(n+1)+1=2[a(n)+n+1]=(2^n)[a(1)+1+1]=2^(n+1)
a(n)=2^n-n-1

luyuanhong

谢谢楼上 fungarwai 的解答。我已将此帖转贴到“陆老师的《数学中国》园地”。

luyuanhong