I need to reduce the following equation to reduce computation complexity.
$$C(n, 0) + C(n-1, 1) + C(n-2, 2) ... + C(n/2, n/2)$$
here $C(n,r)$ is $n!\over r!(n-r)!$ and $n$ is positive
I am trying to code an algorithm for an online problem.
The problem lead to this equation as one possible answer which upon implementation causes integer overflow, even with unsigned long long.
To solve the overflow problem I want to transform this equation in such a way that eliminates the calculation of $n!$,
My attempt was half successful, I converted $C(n, r)$ into $P(n, r)\over n!$ and I can calculate $P(n,r)$ by multiplying from $n$ till $r+1$.
EDIT: contraint: $n\over 2$ simplifies to integral part, just like integer division works in int
Each term in your sum is of the form $\left(n-1\atop k+1\right)$ with respect to the term on its left (writing $\left(n\atop k\right)=\frac{n!}{k!(n-k)!}$ for binomial coefficients). And then, just writing it out, you can easily show that $$\left(n-1\atop k+1\right)=\frac{n!/n}{(k+1)k!\ \ (n-k)!/((n-k)(n-k-1))}=\frac{(n-k)(n-k-1)}{n(k+1)}\left(n\atop k\right).$$ So start with your leftmost term $\left(n\atop 0\right)=1$ and then just successively multiply by that factor $\frac{(n-k)(n-k-1)}{n(k+1)}$ for each subsequent term in your loop.
P.S. Make sure to perform the $\left(n-1\atop k+1\right)=\frac{(n-k)(n-k-1)}{n(k+1)}\left(n\atop k\right)$ calculation as $\frac{(n-k)(n-k-1)\left(n\atop k\right)}{n(k+1)}$, i.e., first multiply the numerator by the previous $\left(n\atop k\right)$ result, and only then divide that entire product by the denominator, because the $\frac{(n-k)(n-k-1)}{n(k+1)}$ factor may or may not be an integer by itself.