Sigma of Permutations

Question

Given a permutation p of numbers 1, 2, ..., n. Let's define $f(p)$ as the following sum: $$\large f(p)=\sum_{i=1}^n\sum_{j=i}^n\min({\rm p}_i,{\rm p}_{i+1},...,{\rm p}_j)$$ What is the exact job of this sigma I can't understand it, what is the result of it. Would you please explain it by sample example.
Sorry if my question is silly but would you please help me to figure it out.

Answer 1

$$\large f(p)=\sum_{i=1}^n\sum_{j=i}^n\min({\rm p}_i,{\rm p}_{i+1},...,{\rm p}_j)\\\begin{array}{lllllc}=&\min(p_1)&+\min(p_1,p_2)&+\min(p_1,p_2,p_3)&+&...&+\min(p_1,p_2,p_3,...,p_n)\\ &&+\min(p_2)&+\min(p_2,p_3)&+&...&+\min(p_2,p_3,p_4,...,p_n)\\ &&&+\min(p_3)&+&...&+\min(p_3,p_4,p_5,...,p_n)\\ &&&&&\cdots&\vdots\\ &&&&&&+\min(p_n)\\ \end{array}$$

Answer 2

Take a small example: say $p_1 = 1, p_2 = 3, p_3 = 2$, so $n=3$.

We sum over different $i$.

$i=1$: we are left with the inner sum $\sum_{j=1}^{3} \min(p_1,\ldots, p_j)$.

So for $j=1$, $\min(p_1) = p_1 = 1$, for $j=2$, $\min(p_1, p_2) = \min(1,3) = 1$, for $j=3$, $\min(p_1,p_2,p_3) = 1$. So we sum 1 three times, so for $i=1$ we get 3 as the contribution.

$i=2$: we get the inner sum $\sum_{j=2}^3 \min(p_2,\ldots,p_j)$.

So for $j=2$, $\min(p_2) = p_2 = 3$ and $\min(p_2,p_3) = \min(3,2) = 2$. So we sum 2 and 3, so in total 5.

$i=3$: we get the inner sum $\sum_{j=3}^3 \min(p_3,\ldots,p_j)$ which is just the sum of one single $\min(p_3) = p_3 = 2$, so this contributes 2.

So the total sum, for all $i$, we get $3 + 5 + 2 = 10$.

Answer 3

The sum is equal to $$\sum_{k=1}^{n}kW_k$$ where $W_n$ is the width of the interval around $n$ in the permutation that contains only numbers larger than or equal to $k$.

For example:

For the permutation $(1,4,3,2)$ we have

$$\begin{align}W_1=4\qquad\text{ because }\qquad(\overline{1,4,3,2})\\W_2=3\qquad\text{ because }\qquad(1,\overline{4,3,2})\\W_3=2\qquad\text{ because }\qquad(1,\overline{4,3},2)\\W_4=1\qquad\text{ because }\qquad(1,\overline{4},3,2)\end{align}$$

So, the sum is equal to $$4\cdot1+3\cdot2+2\cdot3+1\cdot4=20$$

For the permutation $(132)$ we have

$$\begin{align}W_1=3\qquad\text{ because }\qquad(\overline{1,3,2})\\W_2=2\qquad\text{ because }\qquad(1,\overline{3,2})\\W_2=1\qquad\text{ because }\qquad(1,\overline{3},2)\end{align}$$

So, the sum is equal to $$3\cdot1+2\cdot2+1\cdot3=10$$