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

Let $n,k$ be positive integers. Is there a closed form of the sum

$$\sum_{s=0}^{k} \binom{n}{s} \binom{s}{k-s}\text{?}$$

By that I mean a representation which is free of sums and hypergeometric functions or alike.

Combinatoric interpretation: This is the number of possibilities to distribute $k$ balls in $n$ urns, where each urn has at most $2$ balls.

share|cite|improve this question
how do you interpret a term like $\binom{0}{k}$? You get terms like that in the expansion. – svenkatr Mar 26 '11 at 21:33
By definition $\binom{0}{k}=1$ if $k=0$, else $0$. – Martin Brandenburg Mar 26 '11 at 21:45
I don't have a complete response, but you can already throw away half of the terms in your expansion, since for all $s < k/2,$ the rightmost binomial coefficient vanishes. – Gerben Mar 26 '11 at 22:21 other words, you could present this question in a couple of different cases, i.e. k even/odd and $n \gtrless k$, and only sum over non-zero terms. – Gerben Mar 26 '11 at 22:28
Try giving sum(binomial(n,d)*binomial(n-d,k-2*d), d=0..k) to Wolfram alpha. I'm not sure you'll like the result... – Yuval Filmus Mar 26 '11 at 22:41
up vote 6 down vote accepted

Your sum is equal to the coefficient of $x^{k}$ in the expansion of $(1+x+x^2)^n$. According to mathworld, this is the trinomial coefficient ${n \choose n-k}_2$.

On the linked page, there is a table of formulas for ${n \choose n-k}_2$ for fixed $k$ and variable $n$. There are no general formulas listed there that do not use either sums or hypergeometric functions, so I would wager that there is no known simpler representation of that sum.

share|cite|improve this answer

maxima's implementation of Gosper-Zeilberger's algorithm (see for example "A = B") says it has no closed form.

share|cite|improve this answer

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.