Creating sorted arrays

Computer Science Level 4

Let A[1..n] be an array of integers with $n$ elements from $\{ 1, 2, 3, \ldots, m \}$ such that A[1..n] is strictly increasing.

For numbers: $n = 567$ and $m = 1933$ . If $S$ is that actual number of different arrays, provide $S \pmod {10^{9} + 7}$ .

Example:

$n = 2, m = 3$ : The format of required array is $A[a_1, a_2]$ ; possible values for elements of array are from set $\{1, 2, 3\}$ . For this example, answer is $\boxed{3}$ . Arrays that suffice given conditions are:

$A_1 = 1, 2$
$A_2 = 2, 3$
$A_3 = 1, 3$

The answer is 505534904.

2 solutions

Hasmik Garyaka
Oct 24, 2017

def C(n,m):
    if m==0: return 1
    if m==1:return n
    r=1
    for i in range(m):
        r*=n-i
        r//=i+1
    return r

Levent B
Jan 25, 2017

We have 1933 potential numbers to choose from, and we want to choose 567 of them. This is just a simple combination problem. I used python because of the large numbers that we are working with:

def combination(n, c):
    return (factorial(n) // factorial(n - c)) // factorial(c) % 1000000007  

def factorial(n): 
    answer = 1
    for i in range(1, n + 1):
        answer *= i
    return answer

print(combination(1933, 567) % 1000000007)

we have factorial in math library
But it is inefficient, we can calculate combination in cycle without big numbers.

Hasmik Garyaka - 3 years, 7 months ago

Creating sorted arrays

The answer is 505534904.

2 solutions

0 pending reports