Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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<n,\space m<n$$ In case you are interested: If my derivation is correct, the above formula is the exact probability that an ordered partition of $n$ elements into $k+1$ pieces does not contain a summand $\geq m$. The formula was derived in two different ways. By simply counting intervals and by counting points on a truncated $n$-simplex.

share|cite|improve this question
What 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. – Simon Markett May 18 '12 at 12:00
Good 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. – mbundgaard May 18 '12 at 13:07
Any CAS software will easily compute it. Do you need to do it using floating point numbers? Or am I missing the question? – Sasha May 18 '12 at 13:36
@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. – mbundgaard May 18 '12 at 13:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.