Math Visualization List

Permutations and Inversions: Complete Demonstration from Inversion Pairs to Determinant Signs

This page not only shows "what is the inversion count", but demonstrates the entire judgment process step by step: first scan position pairs $(i,j)$ one by one, then draw confirmed inversion pairs as arcs, then use adjacent swaps to restore the permutation to natural order step by step, and finally count the distribution of inversion counts among all permutations. This helps you truly understand the connection between inversion count, parity, sign factor, and determinant definition.

Permutation Order n Animation Speed1.0x

Shortcuts: Ctrl+R Random | Ctrl+E Reverse | Ctrl+Space Analyze | Ctrl+Enter Full Demo | Esc Stop

Permutation Main Stage

Position numbers are marked above, permutation values are filled below. In the animation, orange and blue indicate positions being compared, and red arcs indicate confirmed inversion pairs.

Position Contribution Distribution

Core Results Panel

Total Inversion Count $\tau(\sigma)$

Pending Analysis

Permutation Type

Pending Analysis

Sign Factor $\operatorname{sgn}(\sigma)$

Position Pair Scan Progress

0 / 0

Confirmed Inversion Pairs

Adjacent Swap Count

Current Inversion Count

Pending Swap Phase

Theoretical Max Inversions

Current Demo Progress0 / 0

Sign Factor Explanation

When the inversion count is not yet determined, the parity and sign factor of the permutation are also undetermined.

Swap Invariant Explanation

After completing the inversion analysis, it will explain here how "inversion count = minimum number of adjacent swaps" is verified in the animation.

Current Comparison Focus

Comparison Not Started

Left Position

Position: -
Value: -

Right Position

Position: -
Value: -

A position pair $(i,j)$ is an inversion pair if and only if $i \sigma_j$.

The diagonal represents positions themselves; each cell in the upper triangle corresponds to a position pair $(i,j)$. Light cyan indicates scanned and not inverted, light red indicates confirmed inversion, blue border indicates current focus.

Inversion Pair Detailed Statistics

Here we record the comparison result, cumulative inversion count, and whether each pair $(i,j)$ forms an inversion in fixed scan order. You can think of this as an "animated definition expansion".

Index	Position Pair	Value Pair	Comparison	Inversion?	Cumulative Inversions

相邻交换还原舞台

第二阶段只允许交换相邻两个位置。每发生一次“相邻逆序交换”，当前排列的逆序数就恰好减少 1，因此最终总交换次数会等于原排列的逆序数。

等待开始

尚未进入扫描

当前符号：?

Operations Process and Logical Explanation

Inversion Count Distribution Across All Permutations

When $n \le 6$, we can enumerate all $n!$ permutations and count how many times each inversion count $k$ appears. This reveals the distribution symmetry and the law that the number of even and odd permutations are equal.

Inversion Count k	Number of Permutations	Example Permutations

Theoretical Overview of Permutations and Inversions: A Complete Guide from Scratch

The inversion count is not an isolated technique, but the core source of the sign in the permutation definition of determinants. Once you truly understand "which position pairs form inversions" and "why adjacent swaps change parity", the $(-1)^{\tau(\sigma)}$ in the determinant formula will become very natural.

Prerequisite: What is a Permutation?

Before learning about inversions, we need to understand what a permutation is. Simply put, a permutation is a rearrangement of the numbers 1, 2, 3, ..., n into a sequence.

Examples:
• For n=3, all possible permutations are: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)
• There are 3! = 6 different permutations in total
• Each permutation contains each number from 1 to n exactly once

We denote a permutation as $\sigma = (\sigma_1, \sigma_2, \ldots, \sigma_n)$, where $\sigma_i$ represents the number at position $i$.

I. Inversion Pairs and Inversion Count: Core Concepts

Now let's understand what an "inversion" is. Imagine you have a sequence of numbers. If the number on the left is greater than the number on the right, then these two positions form an "inversion pair".

1.1 Intuitive Understanding of Inversion Pairs

Example: Permutation (3, 1, 2)
• Position 1 and Position 2: 3 > 1, this is an inversion pair ✓
• Position 1 and Position 3: 3 > 2, this is an inversion pair ✓
• Position 2 and Position 3: 1 < 2, this is not an inversion pair ✗
So the permutation (3, 1, 2) has 2 inversion pairs

1.2 数学定义

对排列 $\sigma=(\sigma_1,\sigma_2,\dots,\sigma_n)$，若存在 $i < j$ 且 $\sigma_i> \sigma_j$，则位置对 $(i,j)$ 为逆序对。所有逆序对的个数就是逆序数 $\tau(\sigma)$。

$$\tau(\sigma)=\#\{(i,j)\mid i < j,\ \sigma_i> \sigma_j\}$$

1.3 为什么叫"逆序"？

因为如果所有数字都按从小到大排列（即自然顺序 1, 2, 3, ...），就不会有任何逆序对。每当有数字"违反"了这个自然顺序，就产生逆序。

二、位置贡献视角：分而治之的思想

计算逆序数有一个巧妙的方法：看每个位置对总逆序数的"贡献"。

2.1 位置贡献的含义

对于位置 $i$，我们只需要数一数：在它右边有多少个数字比 $\sigma_i$ 小？这个数量就是位置 $i$ 的贡献 $c_i$。

Example: Permutation (4, 2, 3, 1)
• Position 1 (value 4): Values smaller than 4 on the right are 2, 3, 1, total 3 → $c_1 = 3$
• Position 2 (value 2): Values smaller than 2 on the right is 1, total 1 → $c_2 = 1$
• Position 3 (value 3): Values smaller than 3 on the right is 1, total 1 → $c_3 = 1$
• Position 4 (value 1): No values on the right → $c_4 = 0$
Total inversion count: $\tau(\sigma) = 3 + 1 + 1 + 0 = 5$

2.2 Mathematical Expression

Fix position $i$ and count only elements to its right that are smaller than $\sigma_i$, denoted as $c_i$. Then the total inversion count can be expressed as the sum of contributions from each position:

$$c_i=\#\{j > i\mid \sigma_i > \sigma_j\},\qquad \tau(\sigma)=\sum_{i=1}^{n}c_i$$

III. Odd Permutations, Even Permutations, and Sign Factor

The inversion count is not just a number; it also determines the "parity" of the permutation, which is crucial in determinant calculation.

3.1 Definition of Parity

Based on the parity of the inversion count, we classify permutations into two types:

• Even permutation: Permutation with even inversion count
• Odd permutation: Permutation with odd inversion count

3.2 Sign Factor

The sign of a permutation is defined as $\operatorname{sgn}(\sigma)=(-1)^{\tau(\sigma)}$. This means:

• The sign of an even permutation is +1
• The sign of an odd permutation is -1

$$\operatorname{sgn}(\sigma)=(-1)^{\tau(\sigma)} = \begin{cases} +1 & \text{如果 } \tau(\sigma) \text{ 是偶数} \\ -1 & \text{如果 } \tau(\sigma) \text{ 是奇数} \end{cases}$$

3.3 Why Define the Sign?

This sign factor is exactly the source of the plus/minus signs in the determinant expansion! Each permutation corresponds to a term in the determinant expansion, and the sign of that term is determined by the permutation's parity.

IV. Magical Properties of Adjacent Swaps

Now let's understand an important question: Why is the minimum number of adjacent swaps equal to the inversion count?

4.1 What is an Adjacent Swap?

An adjacent swap is exchanging numbers at two consecutive positions. For example, in permutation (3, 1, 2), we can swap positions 1 and 2 to get (1, 3, 2).

4.2 Effect of Adjacent Swaps

What happens when we swap a pair of adjacent inverted elements (i.e., adjacent numbers where the left is greater than the right)?

Key Observations:
• The inversion count of the current permutation decreases by exactly 1
• The parity of the permutation changes (odd to even, even to odd)
• The sign factor becomes its opposite

4.3 Why Does the Inversion Count Decrease by 1?

Suppose we swap adjacent positions $i$ and $i+1$, and before the swap $\sigma_i > \sigma_{i+1}$:

• Position pair $(i, i+1)$ was an inversion pair, but no longer is after the swap → inversion count -1
• The inversion relationships of all other position pairs remain unchanged → inversion count unchanged
• Total effect: inversion count decreases by exactly 1

4.4 Minimum Swap Count Theorem

By continuously performing adjacent inversion swaps, after exactly $\tau(\sigma)$ swaps, we will definitely return to the natural order (1, 2, ..., n), and this is the minimum number of swaps.

$$\text{Minimum number of adjacent swaps}=\tau(\sigma)$$

V. The Mathematical Essence of Bubble Sort

You may have learned the bubble sort algorithm; its essence is performing continuous adjacent swaps!

5.1 Bubble Sort = Inversion Elimination

Each effective swap in bubble sort eliminates one inversion pair. When all inversion pairs are eliminated, the array becomes sorted.

5.2 Significance of Swap Count

This explains why the number of swaps in bubble sort equals the inversion count of the original array — because each swap eliminates exactly one inversion!

VI. Role in Determinant Definition

Now we can finally understand the mysterious $(-1)^{\tau(\sigma)}$ in the determinant definition!

6.1 Permutation Definition of Determinant

For an $n \times n$ matrix $A$, the determinant is defined as:

$$\det(A)=\sum_{\sigma\in S_n}(-1)^{\tau(\sigma)}a_{1\sigma_1}a_{2\sigma_2}\cdots a_{n\sigma_n}$$

Here $S_n$ denotes the set of all $n$-element permutations.

6.2 Geometric Meaning of the Sign

Each permutation $\sigma$ corresponds to a term $a_{1\sigma_1}a_{2\sigma_2}\cdots a_{n\sigma_n}$, and the sign $(-1)^{\tau(\sigma)}$ in front of this term reflects:

• If the permutation is even, this term is positive
• If the permutation is odd, this term is negative

6.3 Why Do We Need This Sign?

This sign ensures that the determinant has an important property: swapping two rows of a matrix changes the sign of the determinant. This is because swapping two rows is equivalent to performing an adjacent swap on all permutations, changing the parity of each permutation!

VII. Practical Applications and Extensions

7.1 In Computer Science

• Sorting Algorithm Analysis: Inversion count measures the "disorder degree" of an array
• Algorithm Complexity: Time complexity of some sorting algorithms relates to inversion count
• Data Structures: Inversion count is used for balance analysis in certain tree structures

7.2 In Mathematics

• Linear Algebra: Determinant calculation, matrix theory
• Combinatorics: Permutation statistics, generating functions
• Algebraic Geometry: Applications of signs in polynomial theory

VIII. Learning Advice and Practice Directions

8.1 Step-by-Step Learning Path

1. Basic Practice: Manually calculate inversion counts for small permutations
2. Algorithm Implementation: Implement inversion count calculation and bubble sort programmatically
3. Theoretical Understanding: Prove that adjacent swap count equals inversion count
4. Application Expansion: Learn the permutation definition of determinants
5. In-Depth Study: Understand permutation groups and sign homomorphisms

8.2 Common Misconceptions and Precautions

• Don't confuse "position" with "value": Inversion pairs compare positional relationships
• Understand the restriction of "adjacent swap": Only adjacent positions can be swapped
• Sign factor calculation: Remember it's $(-1)^{\text{inversion count}}$, not the inversion count itself

总结

逆序数是一个看似简单但内涵丰富的概念。它连接了组合数学、线性代数、算法分析等多个领域。通过理解逆序数，我们不仅能更好地掌握行列式的计算，还能深入理解排序算法的本质，以及置换群的代数结构。

记住核心思想：逆序数衡量的是排列偏离自然顺序的程度，而每一次相邻交换都在减少这种偏离。这个简单而优美的性质，正是数学中"局部操作产生全局效果"的典型例子。