程序员最近都爱上了这个网站  程序员们快来瞅瞅吧！  it98k网:it98k.com

这是我在 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,2,1), (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）的，其中的竞争者结束在正好 ķ不同的位置。

例如，我们得到M(3,3) = M(3,2) = 6和M(3,1) = 1。

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

到目前为止是问题

这是我独自想出的问题。经过一段时间的思考，我想出了以下|E(n)| 的 递归公式：（如果您想自己推导出公式，请不要继续阅读！）

|E(n)| = C(n,l)*|E(nl)| 从 l=1 到 n 的总和 其中 |E(0)| = 1

这个函数的 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阵列是memoized /高速缓存的阵列E（n）的值，其真加快了计算，由于需要的重复计算某些E（n）的值。

这种递推关系背后的逻辑是l象征着我们有多少“第一”点。对于每个l，二项式系数C(n,l)象征着我们可以通过多少种方式从n 个竞争者中选出l 个第一名。一旦我们选择了他们，我们需要弄清楚我们可以用多少种方式来安排我们剩下的nl 个竞争对手，这就是|E(nl)| . 我得到以下信息：

|E(3)| = 13

|E(5)| = 541

|E(10)| = 102247563

|E(100)| mod 1 000 000 007 = 619182829 -------> 20 毫秒。

和 |E(1000)| mod 1 000 000 007 = 581423957 -------> 39 秒。

我发现|E(n)| 也可以可视化为以下适用的集合数：

对于每个i = 1, 2, 3 ... n，原始集合的每个i-tuple子集的所有元素的 GCD（最大公约数）都等于 1。但我对此不是 100% 确定，因为我无法为大n计算这种方法。然而，即使预先计算阶乘并记住E(n)'s，更高n's的计算时间增长得非常快。有没有人能够验证上述公式和值？谁能推导出更好、更快的公式？也许有生成函数？

至于M(n,k) .. 我完全一无所知。我完全不知道如何计算它，因此我无法发布任何有意义的数据点。也许是P(n,k) = n!/(nk)!。 谁能找出M(n,k)的公式？

我不知道哪个函数更难计算，无论是E(n)还是M(n,k)，但是帮助我解决它们中的任何一个都将非常可观。

我希望解决方案是通用的，并且即使对于大的n也能有效地工作。不幸的是，详尽的搜索不是我想要的。我正在寻找的是纯粹基于组合方法和有效公式的解决方案。

我希望我的措辞和我在整个帖子中的要求足够清楚。顺便说一下，我可以使用 Java 编程。我也非常了解 Mathematica :) 。

非常感谢提前，

马坦。

解决方案

E(n) 是富比尼数。M(n, k) = S(n, k) * k!，其中 S(n, k) 是第二类斯特林数，因为 S(n, k) 是不同放置分区的数量，而 k ！是对它们进行排名的方法的数量。