# Closed form for a sum involving binomial coefficients

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.

-
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
...in 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

## 2 Answers

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.

-

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

-