$5$ 个人比赛排名，允许并列，求可能的名次数．
【难度】
【出处】
无
【标注】
【答案】
$541$
【解析】
假设 $n$ 个人比赛成绩有 $m$ 种，其中 $m,n\in\mathbb N^{\ast}$，对应的名次数为 $f(n,m)$．
情形一 $m=1$．
显然名次数为1，即$$f(n,m)=1.$$情形二 $m>n$．
显然这种情况不可能出现，因此$$f(n,m)=0.$$情形三 $2\leqslant m\leqslant n$．
考虑 $n-1$ 个人的情况，此时可能的名次数为 $f(n-1,m)$．
对 $n$ 个人，若第 $n$ 个人的成绩与前 $n-1$ 个人成绩中的某个成绩相同，则前 $n-1$ 个人的名次数为 $f(n-1,m)$，故可能的名次数为 $mf(n-1,m)$；
若第 $n$ 个人的成绩与前 $n-1$ 个人的成绩均不同，则前 $n-1$ 个人的名次数为 $f(n-1,m-1)$，故对应的名次数为 $mf(n-1,m-1)$．
因此 $n$ 个人可能的名次数为 $m[f(n-1,m)+f(n-1,m-1)]$．
综上知，\[f(n,m)=\begin{cases} 1,& m=1,\\ m\left[f(n-1,m)+f(n-1,m-1)\right],& 2\leqslant m\leqslant n,\\ 0,& m>n.\end{cases}\]按照这个递推公式可以填表，按列求和即得．
下表为 $n=5$ 的情形．\[\begin{matrix}
m\backslash n & 1 & 2 & 3 & 4 & 5 \\
1 & 1 & 1 & 1 & 1 & 1\\
2 & 0 & 2 & 6 & 14 & 30\\
3 & 0 & 0 & 6 & 36 & 150\\
4 & 0 & 0 & 0 & 24 & 240\\
5 & 0 & 0 & 0 & 0 & 120\\
\sum & 1 & 3 & 13 & 75 & 541
\end{matrix}\]
显然名次数为1，即$$f(n,m)=1.$$
显然这种情况不可能出现，因此$$f(n,m)=0.$$
考虑 $n-1$ 个人的情况，此时可能的名次数为 $f(n-1,m)$．
对 $n$ 个人，若第 $n$ 个人的成绩与前 $n-1$ 个人成绩中的某个成绩相同，则前 $n-1$ 个人的名次数为 $f(n-1,m)$，故可能的名次数为 $mf(n-1,m)$；
若第 $n$ 个人的成绩与前 $n-1$ 个人的成绩均不同，则前 $n-1$ 个人的名次数为 $f(n-1,m-1)$，故对应的名次数为 $mf(n-1,m-1)$．
因此 $n$ 个人可能的名次数为 $m[f(n-1,m)+f(n-1,m-1)]$．
综上知，\[f(n,m)=\begin{cases} 1,& m=1,\\ m\left[f(n-1,m)+f(n-1,m-1)\right],& 2\leqslant m\leqslant n,\\ 0,& m>n.\end{cases}\]按照这个递推公式可以填表，按列求和即得．
下表为 $n=5$ 的情形．\[\begin{matrix}
m\backslash n & 1 & 2 & 3 & 4 & 5 \\
1 & 1 & 1 & 1 & 1 & 1\\
2 & 0 & 2 & 6 & 14 & 30\\
3 & 0 & 0 & 6 & 36 & 150\\
4 & 0 & 0 & 0 & 24 & 240\\
5 & 0 & 0 & 0 & 0 & 120\\
\sum & 1 & 3 & 13 & 75 & 541
\end{matrix}\]
答案
解析
备注
