12
$\begingroup$

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.

  • 0
    @Yuval: I've already done that, it's useless. @Henry: I think so. @Gerben: Is it really easier in one of these cases?2011-03-26

2 Answers 2

6

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.

1

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