I am dealing with the following problem:
The stock has a known specific price in each day, we want to buy the stock in one day and sell it in another day in a way that we maximize the profit.
The number of days is $n$.
The boring way to solve it is to check all possible pairs of date. For example, buy in day $1$ and sell in day $2$, buy in day $1$ and sell in day $3$, buy in day $1$ and sell in day $6$ ...
I want to count all possible pairs:
My Solution : The first day has $n-1$ pairs because we can buy in the first day and then we can sell in another other day. In the same way we find that day two has $n-2$ pairs, the third day has $n-3$ pairs, the day $n-1$ has $1$ pair, and the last day has $0$ pair
So number of possible pairs is:
$$(n-1) + (n-2) + (n-3)+ ... + 1 + 0$$
Which is a famous Triangular Number, and is equal to: $\dfrac{n(n-1)}{2}$
My Question : The books states that it is $2^n$ as you can see:
What am I missing please?
P.S.
Though I know that this is a Maximum Subarray Problem, I am trying to use the brute-force solution for learning purposes.
What you are missing is that the notation ${n\choose 2}$ does not mean $2^n$. Instead, $n\choose k$ is generally defined as the number of $k$-elements subsets of an $n$-elements sets, or the number of ways you can choose $k$ objects among $n$ objects if the order doesn't matter (it's also sometimes denoted $C^n_k$ or $C^k_n$). It can be shown that $${n\choose k}=\frac{n!}{k!(n-k)!},$$and thus in particular for $k=2$ : $${n\choose 2}=\frac{n(n-1)}{2},$$so your solution is perfectly fine.
The numbers $n\choose k$ are also called binomial coefficients.