Given a string $ab$ and string length $n$, how can I prove that $|\{ (x,y) : x\text{ is index of } a, y\text{ is index of } b , x < y \}| \le n^2/4 $ This is a coding question that I ran into, basically you have a string:
"ababa", you need to find:
$$S = \{(x,y): x\text{ is index of }a,\ y\text{ is index of }b, x < y\}$$
$$S = \{(0,1) (0,3) (2,3)\}\text{ in this case, } |S| = 3$$
the question is that if you are given the length of the string: $n$, what is the maximum size of $S$
I think the answer is $n^2/4$ : 
if n = 6, I start by putting $n/2$ b on the left and $n/2$ a on the right: $bbbaaa$
every time I move a $b$ towards right, $|S|$ increment by $1$
"bbbaaa" $|S| = 0$  -> "bbabaa" $|S| = 1$ (this is obvious since for each $a$, $(x,y)$ is not changed except the $a$ that is switch with $b$, he gets an extra $(x,y)$)
"bbaaba" $|S| = 2$ -> ... "aaabbb" $|S| = 9$
But I am having a hard time to prove that this covers all the cases of |S| which I think is from 0 to $n^2/4$
the question is a bit long, please let me know if you need more detail
 A: You have $k$ 'a's and $n-k$ 'b's, and the highest count arises if all the 'b's are to the right of all the 'a's, namely $k(n-k)$. Setting the derivative with respect to $k$ to $0$ yields $n-2k=0$ and thus $k=\frac n2$, so the maximal count is $\frac n2(n-\frac n2)=\frac n2\cdot\frac n2=\frac{n^2}4$.
A: Ok, so the set $\{1,2,3\dots n\}$ is split into two groups, the group of numbers which have $a$ in that place and the group that has $b$ in that place. We call these subsets of $\{1,2,3\dots n\}$  $A$ and $B$ respectively.
You want to maximize the size of $A\times B$, the set of ordered pairs $(x,y)$ where we have a letter $a$ in position $x$ and a letter $y$ in position $B$.
Notice that $|A\times B|=|A|\times|B|$.
So what you want to maximize is really $a\times b$ , where $a$ and $b$ are two integers that add $n$, and we can assume $a\leq b$.
To do this notice the following:
if $c=b-a$ then $a=\frac{n-c}{2}$ and $b=\frac{n+c}{2}$. from here $a\times b=\frac{n-c}{2}\times\frac{n+c}{2}=\frac{n^2}{4}-\frac{c^2}{4}$
So $a\times b$ is minimized when $c=b-a$ is minimized.
When $n$ is even this clearly happens when $a=b$, which makes $c$ zero and the maximum $\frac{n^2}{4}$.
When $n$ is odd this happens when $b=\lfloor\frac{n}{2}\rfloor+1$ and $a=\lfloor\frac{n}{2}\rfloor$ which makes $c=1$ and makes the maximum $\frac{n^2}{4}-\frac{1}{4}=\frac{n^2-1}{4}$
