a(n+1,m)=(m+1)a(n,m)+(n-m+1)a(n,m-1)

fungarwai

田忌赛马
n匹马能取胜m次的方法数为a(n,m)
若前n匹马能取胜m次，第n+1匹马放在能取胜的m匹马上，或第n+1匹马放在原位：(m+1)a(n,m)
若前n匹马能取胜m-1次，第n+1匹马放在不能取胜的m-1匹马上：(n-m+1)a(n,m-1)
a(n+1,m)=(m+1)a(n,m)+(n-m+1)a(n,m-1)

将n个箱子编号为1,2,3,...,n，n个球编号为1,2,3,...,n，编号i的球只能放入编号1,2,3,...,i
n个箱子恰有m个空箱子的方法数为a(n,m)
n个箱子恰有m个空箱子时，第n+1个球放进m个空箱子的其中1个或者第n+1个箱子：(m+1)a(n,m)
n个箱子恰有m-1个空箱子时，第n+1个球放进n-(m-1)个非空箱子：(n−m+1)a(n,m−1)
a(n+1,m)=(m+1)a(n,m)+(n-m+1)a(n,m-1)

luyuanhong

楼上 fungarwai 的帖子很好！我已将此帖转贴到“陆老师的《数学中国》园地”。