How to improve the binomial algorithm?
The answer for your question How to improve with an implementation that would be based on saving computed values in an array? is to use memoization (sometimes known as dynamic programming), which incidentally is the same as saving computed values. But this is a somewhat odd solution to the problem. A better solution is computing the binomial coefficient according to the formula and recursion in vonbrand's comment, and use exponentiation to complete the calculation.

For completeness, here are the formula and the recursion:
$$
\binom{n}{k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k \cdot (k-1) \cdots (1)}, \qquad \binom{n}{k+1} = \frac{n-k}{k+1} \binom{n}{k}.
$$



There are many ways to use memoization here. One natural way is to loop on n, and compute all values of binomial1 in sequence. This only requires knowing the values of binomial1 on n-1, which you save in an array. (Similarly you store the new values in a second array.) As an optimization, you only need to compute these values up to the given k.

I'll let you come up with matching code and runtime analysis.