We have given an empty array of size n , we need to fill it with natural numbers (we are allowed to repeat). The condition that must follow is the mex of the array must be greater than all the elements we fill in the array . Can someone pls help me with the number of ways to do so ? (Different arrangements of same set of numbers are also considered distinct)
PS:- by mex of a sequence I mean the smallest non negative number that doesn't occur in the sequence
Number of such arrays is equivalent to the number of ordered distributions of values 1..N into buckets (so [A],[B,C] and [B,C][A] are distinct ones). And number of such distributions is described by ordered Bell numbers 1,3,13,75....
Example for 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 for reference. Note that for N values every value might fall into part 1..K, where K is in range 1..N, so numbers of parts corresponding to all values form continuous sequence without holes (cf. your mex)
To calculate number of such distributions, we can use recurrence from Wiki, Python code:
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