这道题如果编程计算，用动态规划最方便，可以直接递推也可以利用已有的结论；而在组合数学中，应用

则可以得到漂亮简洁的结论。

一、直接动态规划

我们用dp[i][j]表示有j个人，i种名次。那么显然有如下关系成立：

dp[i][i]=i!

dp[1][j]=1

dp[i][j]=i*dp[i][j-1]+i*dp[i-1][j-1](j>i>1)

第一条是没有并列的情况，直接全排列；

第二条是全部并列，显然只有1种；

第三条是状态转移方程：当j-1个人排完名次之后加入一个人，有两种情况：

而答案就是dp[i][j]对i求和。写个程序算一下前几项：

从图像看对数曲线近似呈直线，但斜率缓慢增加，经查阅资料，n很大时有

a(n)\approx \frac{n!}{2(ln2)^{n+1}}

由上式容易知道

\lim_{n \rightarrow \infty}{\frac{na(n-1)}{a(n)} }=ln2

更多内容请参阅该oeis词条和

，本人英语水平太差，就不翻译了。