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
    how do you interpret a term like $\binom{0}{k}$? You get terms like that in the expansion.2011-03-26
  • 1
    By definition $\binom{0}{k}=1$ if $k=0$, else $0$.2011-03-26
  • 0
    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.2011-03-26
  • 0
    ...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.2011-03-26
  • 0
    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...2011-03-26
  • 0
    Are you using distinguishable urns and indistinguishable balls?2011-03-26
  • 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.