All Questions
7
questions
1
vote
2
answers
301
views
Can a binominal (or multinomial) coefficient be computed efficiently?
It would seem that a preceding query would be on point, but not really for me. One of the answers comes close, but it isn't complete as is. Since the answer is going to be an integer, all the ...
- 201
0
votes
1
answer
102
views
is the right approach to use the binary entropy function to get a $O(c^n)$ approximation?
I just finished the implementation of an algorithm and wanted to report its approximate run-time in a O*($c^n$) format, the time analysis results is O*$n/2 \choose n/4$. I'm using the binary entropy ...
3
votes
1
answer
438
views
Fast Evaluation of Multiple Binomial Coefficients
Suppose we have a sequence of binomial coefficients.
$$
S = \left\langle \binom{5}{2}, \binom{5}{3}, \binom{6}{3}, \binom{17}{14}, \binom{19}{15} \right\rangle
$$
How can we efficiently evaluate all ...
- 330
2
votes
2
answers
114
views
How to check if $k$ divides $\binom {n - 1} {k - 1}$ cheaply?
I'm writing a computer algorithm to do binomial expansion in C#. You can view the code here; I am using the following identity to do the computation:
$$
\dbinom n k = \frac n k \dbinom {n - 1} {k - 1}...
- 353
3
votes
1
answer
65
views
How many ways to choose K guests out of N such that M pairs are familiar?
Suppose we have N people sitting in a long one sided table.
Every person not on the edge of the table, is talking with the person to his right and to the left and getting acquainted with him.
The ...
- 1,753
24
votes
8
answers
42k
views
How do I compute binomial coefficients efficiently?
I'm trying to reproduce Excel's COMBIN function in C#. The number of combinations is as follows, where number = n and number_chosen = k:
$${n \choose k} = \frac{n!}{k! (n-k)!}.$$
I can't use this ...
- 495
2
votes
3
answers
1k
views
Counting subsets containing three consecutive elements (previously Summation over large values of nCr)
Problem: In how many ways can you select at least $3$ items consecutively out of a set of $n ( 3\leqslant n \leqslant10^{15}$) items. Since the answer could be very large, output it modulo $10^{9}+7$.
...
- 242