每日一题[3693]递推与构造

2024年12月广东省广州市高三调研数学试卷 #19

在正整数 $1,2, \cdots, n$（$n \geqslant 2$）的任意一个排列 $A: a_1, a_2, \cdots, a_n$ 中，对于任意 $i, j \in \mathbb{N}^{\ast}$，$i<j$，若 $a_i<a_j$，则称 $(a_i,a_j)$ 为一个顺序对，若 $a_i>a_j$，则称 $(a_i,a_j)$ 是一个逆序对．记排列 $A$ 中顺序对的个数为 $S(A)$，逆序对的个数为 $N(A)$．例如对于排列 $A: 2,1,3$，有 $S(A)=2$，$N(A)=1$．

1、设排列 $B: 2,4,1,3$ 和 $C: 5,3,1,4,2$，试写出 $S(B), N(B), S(C),N(C)$ 的值．

2、对于正整数 $1,2, \cdots, n$（$n \geqslant 2$）的所有排列 $A$，求满足 $S(A)=2$ 的排列个数；

3、如果把排列 $A: a_1, a_2, \cdots, a_n$ 中两项 $a_i, a_j$（$i<j$）交换位置，而其余项的位置保持不变，那么就得到了一个新的排列 $A^{\prime}$，求证：$\left(S(A)-S\left(A^{\prime}\right)\right) \cdot\left(N(A)-N\left(A^{\prime}\right)\right)$ 为奇数．

解析

1、根据定义，对正整数 $1,2, \cdots, n$（$n \geqslant 2$）的任意一个排列 $A: a_1, a_2, \cdots, a_n$，均有 $$S(A)+N(A)=\dbinom n2=\dfrac{n(n-1)}2,$$ 因此只需要统计顺序对的个数． 对于排列 $B:2,4,1,3$，顺序对有 $(2,4),(2,3),(1,3)$，共 $3$ 个，因此 $S(B)=3$，$N(B)=\dbinom 42-S(B)=3$； 对于排列 $C:5,3,1,4,2$，顺序对有 $(3,4),(1,4),(1,2)$，共 $3$ 个，因此 $S(C)=3$，$N(C)=\dbinom 52-S(C)=7$． 综上所述，$S(B)=3$，$N(B)=3$，$S(C)=3$，$N(C)=7$．

2、设对正整数 $1,2, \cdots, n$（$n \geqslant 2$）的排列 $A$ 中满足 $S(A)=m$ 的排列个数为 $f(n,m)$，则 对于 $m=0$，有 $f(n,0)=1$； 对于 $m=1$，考虑 $n\to n+1$ 时，$n+1$ 只可能放在第 $1,2$ 位，于是 $$f(n+1,1)=f(n,1)+f(n,0)=f(n,1)+1,$$ 而 $f(2,1)=1$，于是 $f(n,1)=n-1$； 对于 $m=2$，考虑 $n\to n+1$ 时，$n+1$ 只可能放在第 $1,2,3$ 位，于是 $$f(n+1,2)=f(n,2)+f(n,1)+f(n,0)=f(n,2)+(n-1)+1=f(n,2)+n,$$ 而 $f(2,2)=0$，于是 $f(n,2)=\dfrac{n^2-n-2}2$．

3、由于 $$\left(S(A)-S\left(A^{\prime}\right)\right)+\left(N(A)-N\left(A^{\prime}\right)\right)=\big(S(A)+N(A)\big)-\big(S(A')+N(A')\big)=0,$$ 因此只需要证明 $S(A)-S(A')$ 是奇数． 考虑到对排列 $A$ 中的 $\dbinom n2$ 个数对：

① 位置处于 $a_i$ 之前以及 $a_j$ 之后的数形成的顺序对或者逆序对不受交换位置操作的影响；

② 数值比 $a_i,a_j$ 均大或者比 $a_i,a_j$ 均小的数形成的顺序对或者逆序对不受交换位置操作的影响； 因此只需要考虑位置处于 $a_i,a_j$ 之间以及数值也处于 $a_i,a_j$ 之间的数受交换位置操作的影响，这些数每个都会使得 $A$ 的顺序对数增加 $2$ 或者减少 $2$，再加上 $a_i,a_j$ 交换使得顺序对数增加 $1$ 或者减少 $1$，因此 $S(A)-S(A')$ 为奇数，命题得证．