2018-江苏卷-23 解-排列组合

本题导读

本题考查排列与逆序数定义。核心在于结论递推法、累加法的灵活运用。

📌【题干】

Question

（2018年江苏卷）设置$n\in {\mathbb{N}}^{\ast }$，对$1,2,\dots ,n$的一个排列$i_1{i}_2\dots i_n$，如果当$s<t$时，有$i_s>i_t$，则称$(i_s,i_t)$是排列$i_1{i}_2\dots i_n$的一个逆序，排列$i_1{i}_2\dots i_n$的所有逆序的总个数称为其逆序数. 记$f_n(k)$为$1,2,\dots ,n$的所有排列中逆序数为$k$全部排列的个数. (1) 求$f_3(2),f_4(2)$的值；(2) 求$f_n(2)(n\ge 5)$的表达（用$n$表示）.

🔍【思路分析】

破题导航

1. 理解逆序数：逆序数简化了一个排列相对于自然顺序（$123\dots n$）的“混乱程度”。

   • $f_n(0)$：只有一个排列，即$123\dots n$，故$f_n(0)=1$。

   • $f_n(1)$：只能是连续两个数据交换位置（如$132\dots n$），共有$n-1$种可能，故$f_n(1)=n-1$。

2. 第一问：穷举与观察：

   • $f_3(2)$：对$1,2,3$的全排列进行穷举，数出逆序数为2的个数。

   • $f_4(2)$：可以利用插入法。在$1,2,3$的排列中插入数字$4$。

3. 第二个问题：建立递推关系（核心）：考虑将数字$n+1$到插入$1,2,\dots ,n$的一个排列中。

   • 若插入到最后位，逆序数不变（增加0）。

   • 若插入到倒数第二位，逆序数增加1。

   • 若插入到倒数第三位，逆序数增加2。以此类推。由于我们要找逆序数为2的新排列，所以：

   • 原排列逆序数为2，则$n+1$必须放最后位（1种放法）。

   • 原排列逆序数为1，则$n+1$必须放倒数第二位（1种放法）。

   • 原排列逆序数为0，则$n+1$必须放倒数第三位（1种放法）。由此得到递推式：$f_{n+1}(2)=f_n(2)+f_n(1)+f_n(0)$。

4. 直观通项： 代入$f_n(1)=n-1$和$f_n(0)=1$，得到$f_{n+1}(2)=f_n(2)+n$. 利用疲劳的加法活动。

✅【答案】

点击查看答案

(1) $f_3(2)=2$，$f_4(2)=5$

(2) $f_n(2)=\frac{n^2-n-2}{2}$（$n\ge 5$）

✍【详细解析】

Abstract

解：(1) 对于$1,2,3$的所有排列，逆序情况如下：

• $123$：逆序数为0

• $132$：逆序$(3,2)$，数为1

• $213$：逆序$(2,1)$，数为1

• $231$：逆序$(2,1),(3,1)$，数为2

• $312$：逆序$(3,1),(3,2)$，数为2

• $321$：逆序$(3,2),(3,1),(2,1)$，数为3故**$f_3(2)=2$**。

对于$1,2,3,4$的排列中逆序数为2的个数：将数字$4$插入$1,2,3$的排列中：

• 若原排列逆序数为2（共$f_3(2)=2$个），$4$插在最后，新逆序数仍为2。

• 若原排列逆序数为1（共$f_3(1)=2$个），$4$插在倒数第二位，新逆序数增加 1 等于 2。

• 若原排列逆序数为0（共$f_3(0)=1$个），$4$插在倒数第三位，新逆序数增加 2 等于 2。 故**$f_4(2)=f_3(2)+f_3(1)+f_3(0)=2+2+1=5$**。

(2) 一般的$n\ge 3$，如前所述，逆序数为0的排列只有$12\dots n$，故$f_n(0)=1$。 逆序数为1的排列只能是交换相邻的两个数$(k,k+1)\to (k+1,k)$，共有$n-1$种对，故$f_n(1)=n-1$。

根据插入法原理，将$n+1$到插入$1,\dots ,n$的排列中产生逆序数为2的排列，递推关系为：

$f_{n+1}(2)=f_n(2)+f_n(1)+f_n(0)$

代入已知：

$f_{n+1}(2)=f_n(2)+(n-1)+1=f_n(2)+n$

由此得推式：$f_{n+1}(2)-f_n(2)=n$。 当$n\ge 4$时，利用累加法：

$f_n(2)=(f_n(2)-f_{n-1}(2))+(f_{n-1}(2)-f_{n-2}(2))+\cdots +(f_5(2)-f_4(2))+f_4(2)$

$f_n(2)=(n-1)+(n-2)+\cdots +4+5$

注意这是一个等差数列，首项为5，末项为$n-1$，项数为$(n-1)-4+1=n-4$。

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

（此计算稍繁琐，可改用从一开始的求和）更不用的写法：

$f_n(2)=f_4(2)+{\sum }_{k=4}^{n-1}k=5+[4+5+\cdots +(n-1)]$

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

$f_n(2)=\frac{n(n-1)}{2}-6+5=\frac{n^2-n-2}{2}$

验证：当$n=5$时，$f_5(2)=\frac{25-5-2}{2}=9$。按照递推式$f_5(2)=f_4(2)+4=5+4=9$，符合。

所以，当$n\ge 5$时，$f_n(2)=\frac{n^2-n-2}{2}$。

💡【考点总结与回顾】

1. “插入法”思维：这是解决排列组合动态变化问题的核心工具。理解“新加入的最大数放在倒数第一”$m$位置会产生$m-1$一个新逆序”是本题的破题点。

2. 特殊数列的预判：

   • $f_n(0)=1$

   • $f_n(1)=n-1$

   • $f_n(2)=\frac{n^2-n-2}{2}=\left(\genfrac{}{}{0ex}{}{n}{2}\right)-1$

3. 累加法的规范书写：在使用中$a_n=a_1+\sum (a_k-a_{k-1})$时，一定要契约$n$的取值范围，并最后进行代入验证。

💡【考点归纳与避坑指南】

Danger

1. 核心考点：待补

2. 核心方法：待补

3. 避坑指南：待补

📖【试题探源与推广】

Tip

在更高级的数学中，逆序数的分配可以用生成函数表示：

$F_n(x)={\sum }_{k=0}^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}{f}_n(k)x^k={\prod }_{j=1}^n\frac{1-x^j}{1-x}$

展开此演示式，前几项系数即为$f_n(0),f_n(1),f_n(2)\dots$。本题其实就是在求$x^2$项的系数。通过该公式可以发现，逆序数分布具有高度的精确性，即$f_n(k)=f_n((\genfrac{}{}{0ex}{}{n}{2})-k)$。

🔗【关联脉络】

Multi column

知识锚点 (Nodes)

• 22.01 计数原理、排列与组合
• 19.03 数列通项公式求法全攻略

类题演练 (Links)

• 2004-全国卷I理-22 解-数列的递推关系
• 2008-天津卷理-15
• 2010-新课标卷理-17