arrays - 填充大小为 n 的数组的方法数，使得 mexium 大于数组的每个元素？

Question

我们给出了一个大小为 n 的空数组，我们需要用自然数填充它(我们可以重复)。
必须遵循的条件是 墨西哥 数组的元素必须大于我们填充数组的所有元素。
有人可以帮助我了解这样做的方法吗？
(同一组数字的不同排列也被认为是不同的)
PS:- 通过序列的 mex 我的意思是序列中没有出现的最小的非负数

Answer 1

此类数组的数量等于值的有序分布数量1..N放入桶中(所以 [A],[B,C] 和 [B,C][A] 是不同的)。此类分布的数量由 ordered Bell numbers 1,3,13,75... 描述.
N=3 的示例

1 1 1    //1 permutation
1 1 2    //3 permutations
1 2 2    //3 permutations
1 2 3    //6 permutations
        //13 variants

Generation of distributions themselves以供引用。请注意，对于 N值每个值可能属于部分 1..K ，其中 K在范围内 1..N ，因此与所有值对应的部分数量形成无孔的连续序列(参见您的 mex )
要计算此类分布的数量，我们可以使用 recurrence from Wiki ，Python代码:

def cnk(n, k):
    k = min(k, n - k)
    if k <= 0:
        return 1 if k == 0 else 0
    res = 1
    for i in range(k):
        res = res * (n - i) // (i + 1)
    return res

def orderedbell(n):
    a = [0]*(n+1)
    a[0] = 1
    for m in range(1, n+1):
        for i in range(1, m+1):
            a[m] += cnk(m, i) * a[m - i]
    return a[n]

for i in range(1,10):
    print(orderedbell(i))

1
3
13
75
541
4683
47293
545835
7087261