java - 在n个竞争对手的比赛中安排k个位置

Question

这是我在mathexchange.com上的帖子的副本。
设E（n）为n个参赛者比赛的所有可能的结束安排的集合。
很明显，因为这是一场比赛，n个竞争者中的每一个都想赢。
因此，安排的顺序确实很重要。
我们还可以说，如果两个竞争对手以相同的时间结果结束，他们将赢得相同的位置。
例如，e（3）包含以下安排：
{（1,1,1），（1,1,2），（1,2,1），（1,2,2），（1,2,3），（1,3,2），（2,1,1），（2,1,2），（2,1,3），（2,3,1），（3,1,2），（3,2,1）}。
例如，不用说，这种安排（1，3，3）是无效的，因为两个竞争对手本应以第三名结束，但实际上却以第二名结束。所以上面的安排“转移”到（1，2，2）。
定义k为e（n）子集中竞争对手的不同位置数。
例如：
（1,1,1）----->k=1
（1,2,1）----->K=2
（1,2,3,2）----->k=3
（1,2,1,5,4,4,3）----->K=5
最后，设M（n，k）为E（n）的子集个数，其中竞争对手以恰好k个不同的位置结束。
例如，我们得到M（3,3）=M（3,2）=6和M（3,1）=1。

-------------------------------------------------------------------------------------------

目前的问题是
这是我一个人想出来的问题经过一段时间的思考，我得出了以下关于e（n）的递归公式：
（如果你想自己推导一个公式，不要继续阅读！）
| e（n）=c（n，l）*e（n-l）其中e（0）=1的l=1到n的和
以及此函数的Java代码，使用BigInteger类：

public static BigInteger E (int n)
{
    if (!Ens[n].equals(BigInteger.ZERO))
        return Ens[n];
    else
    {
        BigInteger ends=BigInteger.ZERO;
        for (int l=1;l<=n;l++)
            ends=ends.add(factorials[n].divide(factorials[l].multiply(factorials[n-l])).multiply(E(n-l)));
        Ens[n]=ends;
        return ends;
    }
}

阶乘数组是一个预先计算的阶乘数组，用于更快的二项式系数计算。
ens数组是一个存储/缓存e（n）值的数组，由于需要重复计算某些e（n）值，因此它确实加快了计算速度。
这种重复关系背后的逻辑是，l象征着我们有多少“第一”点。对于每一个l，二项系数c（n，l）表示我们可以从n个竞争者中选择l个第一名。一旦我们选择了他们，我们就需要弄清楚我们可以用多少种方法来安排我们剩下的n-l竞争对手，也就是| E（n-l）|。
我得到以下信息：
|E（3）|=13
| E（5）=541
| E（10）=102247563
|E（100）|模1000 000 007=619182829----->20毫秒。
和e（1000）mod 1000 000 007=581423957--->39秒。
我发现e（n）也可以可视化为以下适用的集合数：
每i=1，2，3n，原始集合的每个i元组子集的所有元素的GCD（最大公约数）都等于1。
但我不能百分之百确定，因为我无法计算大n的这种方法。
然而，即使预先计算因子并记住E（n），高n的计算时间也增长得很快。
是否有人能够验证上述公式和值？
有谁能得出一个更好更快的公式吗也许是生成函数？
至于M（n，k）我完全不知道。我完全不知道如何计算，因此我无法发布任何有意义的数据点。
可能是P（n，k）=n！/（N-K）！是的。
有人能想出M（n，k）的公式吗？
我不知道哪一个函数更难计算，不管是E（n）还是M（n，k），但是帮助我处理这两个函数都是非常有价值的。
我希望这些解决方案是通用的，并且即使对于大n也能有效地工作。不幸的是，我并不是在寻找详尽的搜索。
我要找的是纯粹基于组合方法和有效公式的解。
我希望我在整个职位上的措辞和要求足够清楚顺便说一下，我可以用Java编程我对Mathematica也很了解：）。
提前多谢了，
玛坦。

Answer 1

E（n）是Fubini numbersm（n，k）=s（n，k）*k！，其中s（n，k）是aStirling number of the second kind，因为s（n，k）是不同放置分区的数目，并且k！是对它们进行排序的方法数。