I have come across the following alternating sum, as part of a larger calculation, that I would like to be able to compute efficiently. Can anyone help me simplify this: $$p(n,k,m)=\frac{\sum_{i=1}^{\lfloor\frac{n}{m}\rfloor}(-1)^i\binom{n-im}{k}\binom{k+1}{i}}{\binom{n}{k}}$$ I need to be able to calculate this accurately for small values (about 1-1000) of all the parameters. If an exact simplification is not possible, a good approximation will also helpful. The following constraints apply: $$k
Alternating sum of products of binomial coefficients
3
$\begingroup$
combinatorics
-
0What do you mean by small parameters? If $m=1$ this should simplyfy things and if $m>1$ and $n\sim m$ then the sum should have very few summands. – 2012-05-18
-
0Good question. Think of "small" as all parameter values being distributed equally between 1 and 1000, or so. I wrote small to avoid having people come up with asymptotic approximations needlessly. – 2012-05-18
-
0Any CAS software will easily compute it. Do you need to do it using floating point numbers? Or am I missing the question? – 2012-05-18
-
0@Sasha I need to calculate these in great numbers within a C program, so I am looking for a formula, that is computationally more affordable. Unfortunately, precomputation is not an option. – 2012-05-18