逆序對是什麼意思

在數學中，特別是在組合數學和排列組合中，逆序對（Inversion）是一個與排列相關的概念。給定一個排列（permutation），也就是一個數字序列，其中每個數字都不相同，我們說一對數字 i 和 j 形成了一個逆序對，當且僅當 i 比 j 小，但排列中 j 出現在 i 之前。

舉個例子，考慮排列 "3124"。在這個排列中，數字 1 和 2 形成了一對逆序對，因為 1 < 2 但 2 出現在 1 之前。同樣地，數字 1 和 4 也形成了一對逆序對。因此，這個排列 "3124" 總共有兩對逆序對。

逆序對的數目可以用來定義兩個排列之間的距離，這個距離稱為逆序對距離（inversion distance）。給定兩個排列 p 和 q，逆序對距離是將排列 p 重新排列為排列 q 所需的逆序對的最小數目。逆序對距離可以用貪心算法或動態規劃來計算。

逆序對在邏輯學、組合數學和計算機科學中都有應用，尤其是在排序算法的分析、卡特蘭數的計算以及邏輯推演等方面。逆序對的數目也被用來定義一些特殊的排列，例如反轉多項式（inversion polynomial）和反轉序列（inversion sequence）。