题目
9.(填空题,4.0分)排列2176354的逆序数为_。
9.(填空题,4.0分)
排列2176354的逆序数为_。
题目解答
答案
计算排列 $2176354$ 的逆序数,即每个元素右侧小于该元素的元素个数之和:
- $2$ 右侧有 $1$(1个逆序对)
- $1$ 右侧无(0个逆序对)
- $7$ 右侧有 $6, 3, 5, 4$(4个逆序对)
- $6$ 右侧有 $3, 5, 4$(3个逆序对)
- $3$ 右侧无(0个逆序对)
- $5$ 右侧有 $4$(1个逆序对)
- $4$ 右侧无(0个逆序对)
总逆序数:$1 + 0 + 4 + 3 + 0 + 1 + 0 = 9$
答案:$\boxed{9}$
解析
逆序数是排列中的重要概念,指排列中每个元素右侧比它小的元素个数之和。解题核心在于逐个元素检查右侧较小元素的数量,最后求和。关键在于:
- 明确逆序数定义:每个元素右侧比它小的元素个数;
- 逐个元素计算:从左到右依次处理每个元素;
- 累加结果:将所有元素的逆序数部分相加。
排列为 $2176354$,逐个元素分析:
- 元素 $2$:右侧有 $1$(1个逆序对);
- 元素 $1$:右侧无更小元素(0个逆序对);
- 元素 $7$:右侧有 $6, 3, 5, 4$(4个逆序对);
- 元素 $6$:右侧有 $3, 5, 4$(3个逆序对);
- 元素 $3$:右侧无更小元素(0个逆序对);
- 元素 $5$:右侧有 $4$(1个逆序对);
- 元素 $4$:右侧无更小元素(0个逆序对)。
总逆序数为 $1 + 0 + 4 + 3 + 0 + 1 + 0 = 9$。