Positive integer sequence with sum $m$ can have at most $\left\lfloor\dfrac{m^2}{8}\right\rfloor$ increasing pairs

Question

Let $a_1,\cdots,a_n$ be a sequence of positive integers such that

$\bullet$ $a_1+\cdots+a_n=m$;

$\bullet$ The number of pairs $(i,j)$ such that $i<j$ and $a_i<a_j$ is $k$.

Must we have $$ k\le \dfrac{m^2}{8}? $$

The relation $k\le \dfrac{m^2}{8}$ is based on the following two observations:

Observation 1. If $a_1,\cdots,a_n$ consists of only $1$'s and $2$'s, then we have $k\le \dfrac{m^2}{8}$, and the result is optimal.

Proof. WLOG we can suppose that the last term in the sequence is $2$. Suppose that there are $t$ $2$'s, and the number of $1$'s to the left of each $2$ is $b_1,\cdots,b_t$, then $$ b_1\le \cdots\le b_t,\quad m=b_t+2t,\quad k=b_1+\cdots+b_t. $$ We then have $k\le tb_t\le\dfrac{(b_t+2t)^2}{8}=\dfrac{m^2}{8}$. Moreover, it is possible that $k=\left\lfloor\dfrac{m^2}{8}\right\rfloor$: Let $t$ be the integer closest to $\dfrac{m}{4}$ (choose either one in case of a tie), and $$ b_1=\cdots=b_t = m-2t, $$ which means that we pick the sequence consisting of $m-2t$ $1$'s followed by $t$ $2$'s. Then we have $k=t(m-2t)$, and we see that \begin{align*} m\equiv 0\,(\operatorname{mod}\,4)&\Rightarrow t=\dfrac{m}{4}\Rightarrow k=\dfrac{m^2}{8};\\ m\equiv 1\,(\operatorname{mod}\,4)&\Rightarrow t=\dfrac{m-1}{4}\Rightarrow k=\dfrac{m^2-1}{8};\\ m\equiv 2\,(\operatorname{mod}\,4)&\Rightarrow t=\dfrac{m-2}{4}\text{ or }\dfrac{m+2}{4}\Rightarrow k=\dfrac{m^2-4}{8};\\ m\equiv 3\,(\operatorname{mod}\,4)&\Rightarrow t=\dfrac{m+1}{4}\Rightarrow k=\dfrac{m^2-1}{8}, \end{align*} so $k=\left\lfloor\dfrac{m^2}{8}\right\rfloor$ in this case.

Note 1.1. We can see that $k=0,\cdots,\left\lfloor\dfrac{m^2}{8}\right\rfloor$ are all possible because a nonincreasing sequence corresponds to $k=0$, and swapping two adjacent entries in a sequence would leave $m$ unchanged, but $k$ changed by $0$ or $\pm 1$.

Note 1.2. The construction above gives the only optimal solutions. Indeed, if $k=\left\lfloor\dfrac{m^2}{8}\right\rfloor$, then $$ t(m-2t)=tb_t\ge k=\left\lfloor\dfrac{m^2}{8}\right\rfloor\Rightarrow \left|t-\dfrac{m}{4}\right|\le\dfrac{1}{2}, k=tb_t\text{ (hence }b_1=\cdots=b_t). $$

Observation 2. If $a_1,\cdots,a_n$ is nondecreasing, then $k\le\dfrac{m^2}{8}$, and the result is also optimal.

Proof. Suppose that each of $1,2,\cdots$ occurs $c_1,c_2,\cdots$ times in the sequence, where $c_i\neq 0$ for finitely many $i$, then $$ m=c_1+2c_2+\cdots,\quad k=\sum_{i<j}c_ic_j=\dfrac{1}{2}\sum_{i\neq j}c_ic_j, $$ so we have $$ m^2 - 8k = (c_1 - 2c_2 - c_3)^2 + 8c_3^2 + \sum^{\infty}_{i=4}i^2c_i^2+\sum_{\max\{i,j\}\ge 4,i\neq j}(ij-4)c_ic_j\ge 0. $$ The result $k\le\dfrac{m^2}{8}$ for nondecreasing sequences is also optimal as shown by the $1-2$ sequences above.

Note 2.1. If the equality holds, then we must have $c_3=c_4=\cdots=0$, otherwise we would have $m^2-8k\ge 8c_i^2\ge 8$.

I don't have any idea for the general case. I guess that if $k$ attains its maximum with $m$ fixed, then $a_1,\cdots,a_n$ must consist of only $1$'s and $2$'s, but I don't know how to prove it. Any help appreciated.

Edit. This question turns out to be trivial. For a general sequence, we apply the process of bubble sort. At each step either we do nothing, either we create a new increasing pair, so $k$ reaches its maximum when and only when the sequence is nondecreasing, and the result $k\le\dfrac{m^2}{8}$ follows from Observation 2 above.

Answer 1

As I pointed out in the comments,

• the order of the sequence $a_i$ doesn't matter. Any rearrangement of them will lead to the same number of (unordered) pairs $(a_i, a_j)$
• I believe that OP has all of the elements required for the proof. As such, this solution can be considered a restatement/refinement of what they presented.

Let's rephrase the question slightly (which OP did in observation 2), which will make this much easier to approach:

Given $a_i$ a squence of positive integers that sum to $m$, let there be $b_1$ 1's, $b_2$ 2's, etc up to $b_n $ n's (the max of the positive integers), so $ \sum i b_i = m$.
Show that $ \sum_{i\neq j} b_i b_ j \leq \frac{m^2 }{ 8}$.

Consider a sequence of $b_i$ that maximizes $ \sum b_i b_j$.
Show that it must have the following properties.

1. There are at least 2 non-zero values.
2. $b_i$ is a non-increasing sequence.
3. $b_3 = b_4 = \ldots = b_n = 0 $.

In particular, if $b_3 \neq 0$, show that $b_1^* = b_1 + b_3, b_2^* = b_2 + b_3, b_3^* = 0, b_i ^* = b_i$ would increase the summation.

4. $b_1 b_2 \leq \frac{m^2}{8}$.

Hence the desired result is true.