第 3 讲计数原理及二项式定理、数学归纳法高考定位 高考对本内容的考查主要有：(1)分类加法计数原理、分步乘法计数原理，B 级要求；(2)排列与组合，B 级要求；(3)二项式定理，B 级要求；(4)数学归纳法的简单应用，B 级要求
真 题 感 悟1
(2018·江苏卷)设 n∈N*，对 1，2，…，n 的一个排列 i1i2…in，如果当 sit，则称(is，it)是排列 i1i2…in的一个逆序，排列 i1i2…in的所有逆序的总个数称为其逆序数
例如：对 1，2，3 的一个排列 231，只有两个逆序(2，1)，(3，1)，则排列 231 的逆序数为 2
记 fn(k)为 1，2，…，n 的所有排列中逆序数为 k 的全部排列的个数
(1)求 f3(2)，f4(2)的值；(2)求 fn(2)(n≥5)的表达式(用 n 表示)
解 (1) 记 τ(abc) 为 排 列 abc 的 逆 序 数 ， 对 1 ， 2 ， 3 的 所 有 排 列 ， 有 τ(123) ＝0，τ(132)＝1，τ(213)＝1，τ(231)＝2，τ(312)＝2，τ(321)＝3，所以 f3(0)＝1，f3(1)＝f3(2)＝2
对 1，2，3，4 的排列，利用已有的 1，2，3 的排列，将数字 4 添加进去，4 在新排列中的位置只能是最后三个位置
因此，f4(2)＝f3(2)＋f3(1)＋f3(0)＝5
(2)对一般的 n(n≥4)的情形，逆序数为 0 的排列只有一个：12…n，所以 fn(0)＝1
逆序数为 1 的排列只能是将排列 12…n 中的任意相邻两个数字调换位置得到的排列，所以fn(1)＝n－1
为计算 fn＋1(2)，当 1，2，…，n 的排列及其逆序数确定后，将 n＋1 添加进原排列，n＋1 在新排列中的位置只能是最后三个位置
因此，fn＋1(2)＝fn(2)＋fn(1)＋fn(0)＝f
