n 人比赛中 k 组位置的安排

Question

这是我在 mathexchange.com 上的 post 的副本。

设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)这个排列是无效的，因为应该的两个竞争者] 以第三名结束，其实以第二名结束。所以上面的排列"transfers"变为(1,2,2).

定义k为distinctpositions 的竞争对手在 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)| = 从l=1到n的C(n,l )*|E(n-l)| 其中 |E(0)| = 1

和 Java 中的代码用于此函数，使用 BigInteger class:

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/cachedE(n)[=162的数组=] 值，因为需要重复计算某些 E(n) 值。

这个递归关系背后的逻辑是l代表我们有多少个"first"点。对于每个 l，二项式系数 C(n,l) 表示我们可以选择多少种方式 l 在 n 个竞争对手中排名第一。一旦我们选择了它们，我们需要弄清楚我们可以用多少种方式来安排我们剩下的 n-l 个竞争者，也就是 |E(n-l)| 。我得到以下信息：

|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)..我是一头雾水。我完全不知道如何计算它，因此我无法 post 任何有意义的数据点。也许是 P(n,k) = n!/(n-k)!. 谁能找出 M(n,k) 的公式？

我不知道哪个函数更难计算，E(n) 或 M(n,k)，但帮助我解决其中任何一个问题都非常值得感激。

我希望解决方案具有通用性，即使对于大型 n 也能高效工作。不幸的是，详尽的搜索不是我要找的。我正在寻找的是完全基于组合方法和高效公式的解决方案。

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

非常感谢，

马坦.

Answer 1

E(n)就是Fubini numbers. M(n, k) = S(n, k) * k!, where S(n, k) is a Stirling number of the second kind，因为S(n,k)是不同放置分区的个数，k！是对它们进行排名的方式的数量。

n 人比赛中 k 组位置的安排

Arrangements of sets of k positions in a n-competitors race

java

algorithm

math

function

set

问题到此为止