0
$\begingroup$

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:

enter image description here

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.

$\endgroup$
2
  • $\begingroup$ It's useful to use MathJax (essentially LaTeX) in your postings. $\endgroup$ Apr 19, 2017 at 8:52
  • $\begingroup$ ${n \choose 2}=n(n-1)/2$ $\endgroup$
    – G Cab
    Apr 19, 2017 at 9:03

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .