求下列排列的逆序数：(1) 13...(2n-1) mid 24...(2n);(2) 13...(2n-1) mid (2n)(2n-2)...2.

我们来逐题分析这两个排列的逆序数。所谓逆序数，是指在一个排列中，前面的数比后面的数大，这样的数对的个数。

第(1)题

排列为：
$1,\ 3,\ 5,\ \cdots,\ (2n-1),\ |\ 2,\ 4,\ 6,\ \cdots,\ 2n$
即：前半部分是前 $ n $ 个正奇数按升序排列，后半部分是前 $ n $ 个正偶数按升序排列。

我们要求这个排列的逆序数。

解题思路：

逆序数的定义是：所有满足 $ i < j $ 但 $ a_i > a_j $ 的数对 $ (a_i, a_j) $ 的个数。

我们将整个排列分为两部分：

• A部分（前n个）： $ 1, 3, 5, \dots, 2n-1 $ —— 所有奇数，升序
• B部分（后n个）： $ 2, 4, 6, \dots, 2n $ —— 所有偶数，升序

注意：A部分和B部分内部都是升序排列，因此：

• A部分内部没有逆序
• B部分内部没有逆序

所以，所有逆序只能出现在“前面的A中的某个数 > 后面的B中的某个数”，即 A 中的某个奇数大于 B 中的某个偶数，且该奇数在排列中出现在该偶数前面。

分析：

我们来计算有多少个这样的逆序对：
对于每一个偶数 $ 2k $（位于B部分），我们统计在A部分中有多少个奇数大于 $ 2k $，这些奇数都在 $ 2k $ 前面，因此每个这样的奇数都会与 $ 2k $ 构成一个逆序对。

我们逐个分析每个偶数 $ 2k $，其中 $ k = 1, 2, \dots, n $

我们要找：在奇数集合 $ \{1,3,5,\dots,2n-1\} $ 中，有多少个奇数 $ > 2k $

奇数序列是：$ 1, 3, 5, \dots, 2n-1 $，共 $ n $ 个奇数。

我们来找出大于 $ 2k $ 的奇数的个数。

最小的奇数大于 $ 2k $ 是：

• 若 $ 2k $ 是偶数，则下一个整数是 $ 2k+1 $，它是奇数。
• 所以大于 $ 2k $ 的最小奇数是 $ 2k+1 $

那么大于 $ 2k $ 的奇数是：
$2k+1,\ 2k+3,\ \dots,\ 2n-1$

这是一个等差数列，首项 $ a = 2k+1 $，末项 $ l = 2n-1 $，公差 2。

项数为：
$\frac{(2n-1) - (2k+1)}{2} + 1 = \frac{2n - 2k - 2}{2} + 1 = (n - k - 1) + 1 = n - k$

所以，对于每个偶数 $ 2k $，有 $ n - k $ 个奇数大于它，且在它前面，因此贡献 $ n - k $ 个逆序。

现在我们对 $ k = 1 $ 到 $ n $ 求和：

$\sum_{k=1}^n (n - k) = \sum_{j=0}^{n-1} j = \frac{(n-1)n}{2}$

第(1)题答案：

$\boxed{\frac{n(n-1)}{2}}$

第(2)题

排列为：
$1,\ 3,\ 5,\ \cdots,\ (2n-1),\ |\ 2n,\ 2n-2,\ \cdots,\ 4,\ 2$
即：前半部分仍是前 $ n $ 个奇数升序排列，后半部分是前 $ n $ 个偶数降序排列。

同样分析逆序数：

仍然分为 A 部分（奇数升序）和 B 部分（偶数降序）。

• A 部分内部：升序 → 无逆序
• B 部分内部：降序 → 有逆序
• A 与 B 之间：A 中的奇数在 B 中的偶数前面，若奇数 > 偶数，则构成逆序

所以，总逆序数 = A与B之间的逆序数 + B部分内部的逆序数

我们分别计算。

第一部分：B部分内部的逆序数

B部分是：$ 2n,\ 2n-2,\ \dots,\ 4,\ 2 $，即从 $ 2n $ 到 $ 2 $ 的偶数降序排列。

这是一个长度为 $ n $ 的严格递减序列。

在递减序列中，任意两个元素都构成逆序（因为前面的比后面的大）。

所以，B部分内部的逆序数 = 从 $ n $ 个元素中任取两个的组合数：

$\binom{n}{2} = \frac{n(n-1)}{2}$

第二部分：A与B之间的逆序数

即：A中的奇数 $ a_i $，B中的偶数 $ b_j $，且 $ a_i > b_j $，由于所有A在B前面，所以每个这样的数对都是逆序。

我们再次对每个偶数 $ b \in B $，统计A中有多少个奇数大于 $ b $

但注意：B中的偶数顺序变了，但集合仍然是 $ \{2,4,6,\dots,2n\} $，所以我们可以仍然对每个偶数 $ 2k $（$ k=1 $ 到 $ n $）统计有多少奇数 $ > 2k $

这和第(1)题中完全一样！

因为在第(1)题中，我们对每个 $ 2k $ 计算了大于它的奇数个数为 $ n - k $，然后总和为 $ \sum_{k=1}^n (n-k) = \frac{n(n-1)}{2} $

虽然B部分顺序变了，但A和B之间的逆序只关心“前面的奇数是否大于后面的偶数”，与B内部顺序无关，只与数的大小有关。

所以，A与B之间的逆序数仍然是：
$\sum_{k=1}^n (n - k) = \frac{n(n-1)}{2}$

总逆序数 = A-B间 + B内部

$\frac{n(n-1)}{2} + \frac{n(n-1)}{2} = n(n-1)$

第(2)题答案：

$\boxed{n(n-1)}$

最终答案：

(1) 逆序数为：$\boxed{\dfrac{n(n-1)}{2}}$

(2) 逆序数为：$\boxed{n(n-1)}$