Permutation of integers

Question

Let $n$ be a positive integer and let $(a_1,...,a_n)$ be a permutation of $\{1,2,...,n\}$. Define $$A_k = \{ a_i | a_i < a_k, i >k\} \\ B_k = \{a_i | a_i > a_k, i < k\}$$ for $1 \leq k \leq n$. Prove that $\sum^{n}_{k=1} |A_k| = \sum^{n}_{k=1} |B_k|$.

The problem confuses me a bit. It asks to prove that both sets will have the same cardinality, but for example, if I choose $n = 10$ and $k = 4$, for the $A_k$ part I will have $i > k$, which means $5...10$, so I have $6$ elements, while in the set $B_k$, I have $i < k$, so I will have $1...3$, meaning $4$ elements. Am I interpreting the problem correctly, if not, can someone improve and help?

Answer 1

Consider the permutation $\pi=(a_1,\ldots,a_n)$. For each $k$, $A_k$ is the set of terms of $\pi$ that are listed after $a_k$ and are smaller than $a_k$. If $\pi=(4,6,3,1,2,5)$, for instance, $A_3=\{1,2\}$: the terms $a_4=1$ and $a_5=2$ come after $a_3=3$ and are smaller than $a_3$. $A_2=\{1,2,3,5\}$: the terms $a_3=3,a_4=1,a_5=2$, and $a_6=5$ are all smaller than $a_2=6$. $B_k$, on the other hand, is the set of terms that are listed before $a_k$ and are larger than $a_k$, so $B_3=\{4,6\}$, and $B_2=\varnothing$: both of the terms before $a_3$ are larger than $a_3$, and none of the terms before $a_2$ is larger than $a_2$.

What we’re looking at here are inversions: if $1\le k<\ell\le n$, the pair $\langle k,\ell\rangle$ is an inversion of the permutation $\pi$ if $a_k>a_\ell$. In other words, each times an integer is listed before a smaller integer, we have an inversion.

HINT: Show that $\sum_{k=1}^n|A_k|$ and $\sum_{k=1}^n|B_k|$ both count the inversions.

Answer 2

For $n = 3$, we have the permutations $(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)$. Using a simple Java program I wrote, I've enumerated the sets $A_k$ and $B_k$ for $ 1 \le k \le n$ for each permutation, as well as the value of $\sum^{n}_{k=1} |A_k|$ and $\sum^{n}_{k=1} |B_k|$ for each permutation below

(1, 2, 3)
A1 = {}
A2 = {}
A3 = {}
B1 = {}
B2 = {}
B3 = {}
sum |Ak| = 0
sum |Bk| = 0

(1, 3, 2)
A1 = {}
A2 = {2}
A3 = {}
B1 = {}
B2 = {}
B3 = {3}
sum |Ak| = 1
sum |Bk| = 1

(2, 1, 3)
A1 = {1}
A2 = {}
A3 = {}
B1 = {}
B2 = {2}
B3 = {}
sum |Ak| = 1
sum |Bk| = 1

(2, 3, 1)
A1 = {1}
A2 = {1}
A3 = {}
B1 = {}
B2 = {}
B3 = {2, 3}
sum |Ak| = 2
sum |Bk| = 2

(3, 1, 2)
A1 = {1, 2}
A2 = {}
A3 = {}
B1 = {}
B2 = {3}
B3 = {3}
sum |Ak| = 2
sum |Bk| = 2

(3, 2, 1)
A1 = {2, 1}
A2 = {1}
A3 = {}
B1 = {}
B2 = {3}
B3 = {3, 2}
sum |Ak| = 3
sum |Bk| = 3

I'm still working on a formal proof to answer this question, which I'll try to add to this answer later.

For now, does this clarify what the problem is asking?

Answer 3

Let us change the notation a bit (simply by renaming the variables). We have $$ \begin{align*} A_k &= \{a_i; a_i<a_k, i>k\}\\ B_i &= \{a_k; a_k>a_i, k<i\} \end{align*} $$ Now the relation between these two sets is more obvious.

We can also rewrite the above equalities as $$ \begin{align*} |A_k| &= |\{(a_i,a_k); a_i<a_k, i>k\}|\\ |B_i|&=|\{(a_i,a_k); a_i<a_k, i>k\}| \end{align*} $$

Now we can see that both sums express the same thing - namely the number of pairs $(a_i,a_k)$ such that $a_i<a_k$ and $i>k$. That is, the number of inversion of the given permutation (see Wikipedia, MathWorld or elsewhere.)

---

In your post you find an example for which $|A_k|\ne|B_k|$. That is possible, but this is not the claim you are trying to prove. You are trying to show that $\sum\limits_{k=1}^n|A_k|=\sum\limits_{k=1}^n|B_k|$. In order to have the same sume, the summands need not necessarily be the same.