Finding binomial coefficient for large n and k modulo m

binomial coefficient table in c
binomial coefficient recursive formula
ncr mod m where m is not prime
binomial coefficient leetcode
python binomial coefficient
lucas theorem
n choose k modm
binomial theorem mod p

I want to compute nCk mod m with following constraints:

n<=10^18

k<=10^5

m=10^9+7

I have read this article:

Calculating Binomial Coefficient (nCk) for large n & k

But here value of m is 1009. Hence using Lucas theorem, we need only to calculate 1009*1009 different values of aCb where a,b<=1009

How to do it with above constraints. I cannot make a array of O(m*k) space complexity with given constraints.

Help!

Just use the fact that

(n, k) = n! / k! / (n - k)! = n*(n-1)*...*(n-k+1)/[k*(k-1)*...*1]

so you actually have just 2*k=2*10^5 factors. For the inverse of a number you can use suggestion of kfx since your m is prime.

Computing Large Binomial Coefficients Modulo Prime / Non-Prime, Binomial coefficient for large n and small modulo be used to calculate all values of (nk)modm for reasonably small n, since it requires time complexity O(n2​). n<=10^18. k<=10^5. m=10^9+7. I have read this article: Calculating Binomial Coefficient (nCk) for large n & k. But here value of m is 1009. Hence using Lucas theorem, we need only to calculate 1009*1009 different values of aCb where a,b<=1009. How to do it with above constraints. I cannot make a array of O(m*k) space complexity with given constraints. Help!

First, you don't need to pre-compute and store all the possible aCb values! they can be computed per case.

Second, for the special case when (k < m) and (n < m^2), the Lucas theorem easily reduces to the following result:

(n choose k) mod m = ((n mod m) choose k) mod m

then since (n mod m) < 10^9+7 you can simply use the code proposed by @kfx.

Binomial Coefficients, Given three numbers n, r and p, compute value of nCr mod p. So we can find modular inverse as p-2. the formula for nCr nCr = fact(n) / (fact(r) x fact(n-r)) Here fact() means factorial. nCr % p first_page Multiply large integers under large modulo Find the String having each substring with exactly K distinct characters  Not rarely, in combinatoric problems it comes down to calculating the binomial coefficient \(n \choose k\) for very large \(n\) and/or \(k\) modulo a number \(m\). In general, the binomial coefficient can be formulated with factorials as \({n \choose k} = \frac{n!}{k!(n-k)!}, 0 \leq k \leq n\). The problem here is that factorials grow extremely

The binominal coefficient of (n, k) is calculated by the formula:

(n, k) = n! / k! / (n - k)!

To make this work for large numbers n and k modulo m observe that:

  1. Factorial of a number modulo m can be calculated step-by-step, in each step taking the result % m. However, this will be far too slow with n up to 10^18. So there are faster methods where the complexity is bounded by the modulo, and you can use some of those.

  2. The division (a / b) mod m is equal to (a * b^-1) mod m, where b^-1 is the inverse of b modulo m (that is, (b * b^-1 = 1) mod m).

This means that:

(n, k) mod m = (n! * (k!)^-1 * ((n - k)!)^-1) mod m

The inverse of a number can be efficiently found using the Extended Euclidean algorithm. Assuming you have the factorial calculation sorted out, the rest of the algorithm is straightforward, just watch out for integer overflows on multiplication. Here's reference code that works up to n=10^9. To handle for larger numbers the factorial computation should be replaced with a more efficient algorithm and the code should be slightly adapted to avoid integer overflows, but the main idea will remain the same:

#define MOD 1000000007

// Extended Euclidean algorithm
int xGCD(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    int x1, y1, gcd = xGCD(b, a % b, x1, y1);
    x = y1;
    y = x1 - (long long)(a / b) * y1;
    return gcd;
}

// factorial of n modulo MOD
int modfact(int n) {
    int result = 1;
    while (n > 1) {
        result = (long long)result * n % MOD;
        n -= 1;
    }
    return result;
}

// multiply a and b modulo MOD
int modmult(int a, int b) {
    return (long long)a * b % MOD;
}

// inverse of a modulo MOD
int inverse(int a) {
    int x, y;
    xGCD(a, MOD, x, y);
    return x;
}

// binomial coefficient nCk modulo MOD
int bc(int n, int k)
{
    return modmult(modmult(modfact(n), inverse(modfact(k))), inverse(modfact(n - k)));
}

Compute nCr % p, , if you wanted to make a 2-person committee from a group of four people, the number of ways to do this is C(4, 2). Binomial coefficients (n k) are the number of ways to select a set of k elements from n different elements without taking into account the order of arrangement of these elements (i.e., the number of unordered sets). Binomial coefficients are also the coefficients in the expansion of (a + b)n

We want to compute nCk (mod p). I'll handle when 0 <= k <= p-2, because Lucas's theorem handles the rest.

Wilson's theorem states that for prime p, (p-1)! = -1 (mod p), or equivalently (p-2)! = 1 (mod p) (by division).

By division: (k!)^(-1) = (p-2)!/(k!) = (p-2)(p-3)...(k+1) (mod p)

Thus, the binomial coefficient is n!/(k!(n-k)!) = n(n-1)...(n-k+1)/(k!) = n(n-1)...(n-k+1)(p-2)(p-3)...(k+1) (mod p)

Voila. You don't have to do any inverse computations or anything like that. It's also fairly easy to code. A couple optimizations to consider: (1) you can replace (p-2)(p-3)... with (-2)(-3)...; (2) nCk is symmetric in the sense that nCk = nC(n-k) so choose the half that requires you to do less computations.

Binomial Coefficient: Formula & Examples, Count of numbers in range which are divisible by M and have digit D at odd places A binomial coefficient C(n, k) can be defined as the coefficient of X^k in the expansion of (1 + X)^n. For large values of n, there will be many common subproblems. C(5, 2) Calculate value of Binomial Coefficient in bottom up manner. It will become apparent what binomial coefficients have to do with it later.] In general, a binomial coefficient looks like this: . You pronounce that as “n choose k“, since the simplest way to understand this binomial coefficient is that it tells you how many ways there are to choose k things out of n possible choices.

Binomial Coefficient, In number theory, Lucas's theorem expresses the remainder of division of the binomial coefficient ( m n ) {\displaystyle {\tbinom {m}{n}}} {\tbinom {m}{n}} by a prime number p in terms of the base p expansions of the integers m and n. Kummer's theorem asserts that the largest integer k such that pk divides the binomial  Binomial Coefficient Calculator. This calculator will compute the value of a binomial coefficient , given values of the first nonnegative integer n, and the second nonnegative integer k. Please enter the necessary parameter values, and then click 'Calculate'.

Lucas's theorem, Using Fermat's little theorem to calculate nCk mod m, for k < m and m is prime. Two versions: 1. Pre-Compute factorials and multiplicative inverses in O(n*logn)​  To find the binomial coefficients for (a + b) n , use the nth row and always start with the beginning. For instance, the binomial coefficients for (a + b) 5 are 1, 5, 10, 10, 5, and 1 — in that order. If you need to find the coefficients of binomials algebraically, there is a formula for that as well.

Calculating large binomial coefficients modulo prime / non-prime , Andrew Granville's paper Binomial coefficients modulo a prime power (you can find a copy here) has the following generalization of Lucas' Theorem: Theorem. In mathematics, the binomial coefficients are the positive integers that occur as coefficients in the binomial theorem. Commonly, a binomial coefficient is indexed by a pair of integers n ≥ k ≥ 0 and is written ( n k ) .

Comments
  • Right, for the OP's small k this will work, but will not generalize for larger values.
  • @kfx Can you please explain, why this will not work for larger values?
  • modfact will "never" halt for n = 10^18
  • @iggy the code is a simple sketch that works for up to 10^9 as mentioned, not a complete implementation of what the OP needs.