0

Let's say I have a permutation of $n$ integers defined like this $(a_1, a_2,\ldots,a_n)$. I have also two sets defined like this $A_k = \{ a_i | a_i < a_k, i > k\}$ and $B_i = \{a_k | a_k > a_i, i > k\}$. Clearly, we are talking about inversions, but I read an argument somewhere, that the above sets can be rewritten as:

$$|A_k| = |\{(a_i, a_k) | a_i < a_k, i > k \}| = |B_i|$$

I see that it talks about inversions, and that one element comes from the set $A_k$, and one from $B_i$. And the sets count the number of inversions. But, how did I get to the above equality from my two initial sets? Is there any intermediate step that I'm missing? I need to explain this to someone highly mathematical, and although I do get the general idea of inversions and what the sets tell us, I still kind of lack the explanation. Any more elaborate explanation?

1 Answers1

0

I suspect that what you're after is that if we let $S=\{(i,k)\mid a_i<a_k, i>k\}$, then $$ |S|=\sum_k |A_k| = \sum_i |B_i|.$$

To see this, count the elements of $S$ in two ways. First, the number of pairs $(i,k)$ in $S$ for any fixed $k$ is $|A_k|$, so $|S|=\sum_k |A_k| $. Similarly, grouping the elements of $S$ according to $i$ gives $|S|=\sum_i |B_i|$.

Tad
  • 6,679
  • Yes. And as I said I see that both talk about inversions but I can`t explain mathematically. –  Nov 12 '15 at 06:49
  • Can i do it somehow with double counting technique? If yes, how? –  Nov 12 '15 at 09:06
  • @terett Yes, that's exactly what's going on. I've edited the answer to make that clearer. – Tad Nov 12 '15 at 11:47