3
$\begingroup$

Lately when I was estimating complexity of some algorithm I came across this sum:

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

Is it possible to find a closed-form expression for this sum, or at least estimate this with some more known functions? I know that it is somewhere between $2^n$ and $3^n$ but I wonder if maybe some better estimation is possible.

$\endgroup$
  • $\begingroup$ @bof: aah, you're right. Apologies. But what is $C^{1}_{n-1}$ supposed to mean (second term when $k=n-1$) ? $\endgroup$ – Alexandre Halm Oct 1 '14 at 7:55
  • $\begingroup$ @AlexH. I guess it's zero. $\binom xk=x(x-1)(x-2)\cdots(x-k+1)/k!$ is zero for $x=0,1,2,\dots,k-1$. $\endgroup$ – bof Oct 1 '14 at 8:03
  • $\begingroup$ I suppose what the OP wants is the total number of ways to pick 2k objects from n objects by first picking k objects from n and then picking k objects from the remaining. $\endgroup$ – Gautam Shenoy Oct 1 '14 at 8:05
  • $\begingroup$ Looks like you got a couple of pretty good answers to your question. What don't you like about them? $\endgroup$ – bof Oct 7 '14 at 2:57
1
$\begingroup$

I calculated the sums for $n\le6$ and plugged the sequence of values into The On-Line Encyclopedia of Integer Sequences (OEIS) It turns out to be sequence A002426, titled "Central trinomial coefficients: largest coefficient of (1+x+x^2)^n". Many interpretations, formulas, and references at the link.

$\endgroup$
0
$\begingroup$

A closed form is given by W/A as $$ \sum_{k=0}^n \binom {n}{k}\!\! \binom {n-k}{k}={}_2F_1 \left(-\frac{n-1}{2} ,-\frac{n}{2} ;1;4 \right) $$ Maybe this can help for some estimation.

$\endgroup$
0
$\begingroup$

For every positive integer $n$, $$\sum_{k=0}^n \binom {n}{k} \binom {n-k}{k} = \biggl\lfloor\Bigl(1+3^n+\frac{1}{3^n}\Bigl)^n \biggr\rfloor - 3^n \biggl\lfloor\Bigl(\frac{1}{3}+3^{n-1}+\frac{1}{3^{n+1}}\Bigl)^n \biggr\rfloor$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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