Stack Overflow
Stack Overflow

Questions tagged [binomial-coefficients]

It is the coefficient of the `x^k` term in the polynomial expansion of the binomial power `(1 + x)^n` which is `(n!)/((n-k)!*k!)`.

It is the coefficient of the x^k term in the polynomial expansion of the binomial power (1 + x)^n which is (n!)/((n-k)!*k!).

This family of numbers also arises in many areas of mathematics other than algebra, notably in combinatorics. For any set containing n elements, the number of distinct k-element subsets of it that can be formed (the k-combinations of its elements) is given by the binomial coefficient C(n, k). Therefore C(n, k) is often read as "n choose k".

213 questions
50
votes
5 answers

Which is better way to calculate nCr

Approach 1: C(n,r) = n!/(n-r)!r! Approach 2: In the book Combinatorial Algorithms by wilf, i have found this: C(n,r) can be written as C(n-1,r) + C(n-1,r-1). e.g. C(7,4) = C(6,4) + C(6,3) = C(5,4) + C(5,3) + C(5,3) + C(5,2) . …
Green goblin
  • 9,898
  • 13
  • 71
  • 100
49
votes
14 answers

How to efficiently calculate a row in pascal's triangle?

I'm interested in finding the nth row of pascal triangle (not a specific element but the whole row itself). What would be the most efficient way to do it? I thought about the conventional way to construct the triangle by summing up the corresponding…
none
  • 11,793
  • 9
  • 51
  • 87
49
votes
3 answers

Fast n choose k mod p for large n?

What I mean by "large n" is something in the millions. p is prime. I've tried http://apps.topcoder.com/wiki/display/tc/SRM+467 But the function seems to be incorrect (I tested it with 144 choose 6 mod 5 and it gives me 0 when it should give me…
John Smith
  • 11,678
  • 17
  • 46
  • 51
24
votes
8 answers

Number of combinations (N choose R) in C++

Here I try to write a program in C++ to find NCR. But I've got a problem in the result. It is not correct. Can you help me find what the mistake is in the program? #include using namespace std; int fact(int n){ if(n==0) return 1; …
Hams
  • 255
  • 1
  • 2
  • 3
11
votes
1 answer

Is the growth of the binomial coefficient function factorial or polynomial

I have written an algorithm that given a list of words, must check each unique combination of four words in that list of words (regardless of order). The number of combinations to be checked, x, can be calculated using the binomial coefficient i.e.…
Tyler Bevan
  • 113
  • 1
  • 5
11
votes
3 answers

Binomial coefficient modulo 142857

How to calculate binomial coefficient modulo 142857 for large n and r. Is there anything special about the 142857? If the question is modulo p where p is prime then we can use Lucas theorem but what should be done for 142857.
user1505986
  • 257
  • 4
  • 10
10
votes
4 answers

Efficient algorithm to get the combinations of all items in object

Given an array or object with n keys, I need to find all combinations with length x. Given X is variable. binomial_coefficient(n,x). Currently I'm using this: function combine(items) { var result = []; var f = function(prefix, items) { …
Panos Kalatzantonakis
  • 12,525
  • 8
  • 64
  • 85
9
votes
6 answers

Binomial test in Python for very large numbers

I need to do a binomial test in Python that allows calculation for 'n' numbers of the order of 10000. I have implemented a quick binomial_test function using scipy.misc.comb, however, it is pretty much limited around n = 1000, I guess because it…
Morlock
  • 6,880
  • 16
  • 43
  • 50
8
votes
4 answers

Computing a binomial probability for huge numbers

I want to compute binomial probabilities on python. I tried to apply the formula: probability = scipy.misc.comb(n,k)*(p**k)*((1-p)**(n-k)) Some of the probabilities I get are infinite. I checked some values for which p=inf. For one of them,…
bigTree
  • 2,103
  • 6
  • 29
  • 45
8
votes
2 answers

Calculating nCr mod p efficiently when n is very large

I need to calculate nCr mod p efficiently. Right now, I have written this piece of code, but it exceeds the time limit. Please suggest a more optimal solution. For my case, p = 10^9 + 7 and 1 ≤ n ≤ 100000000 I have to also make sure that there is no…
OneMoreError
  • 7,518
  • 20
  • 73
  • 112
7
votes
1 answer

Confint() with glm {stats} very, very slow

I have a problem with calculating OR confidence intervals from a glm in the latest version of R, but I have not had this issue before. With any glm where family="binomial", no matter how simple the model is, it will easily allow me to extract the…
user4575913
  • 507
  • 1
  • 7
  • 16
7
votes
2 answers

Binomial test in Java

I'm looking for an efficient Java library (or even a function) to perform the infamous Exact Binomial Test. Something similar to the R function "binom.test" described here. Can you help me? Thanks a lot! :-)
Federico Giorgi
  • 10,495
  • 9
  • 42
  • 56
6
votes
4 answers

Finding binomial coefficient for large n and k modulo m

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…
habaddu arya
  • 119
  • 1
  • 1
  • 8
6
votes
1 answer

Simplifying the Big-O Complexity of this Exponential Algorithm

I have a counting algorithm for which I am trying to get a general big-o description. It is horribly nested and horribly exponential. Here it is: 1. For each T_i in T 2. For k = 1 to max_k 3. For each of 2^k*(n choose k) items 4. For each t in…
Mike V
  • 63
  • 5
5
votes
2 answers

Calculating an *integer* binomial coefficient in R

The number of ways of choosing k objects from n, i.e. the binomial coefficient n!/(k!(n-k)!), is an integer when n and k are integers. How can I calculate this guaranteeing that the result is both correct and of integer type? The choose function…
ChrisW
  • 1,265
  • 12
  • 12
1
2 3
…
14 15