(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在新排列中的位置只能是最后三个位置.
解 (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.
热点一 与计数原理有关的问题 【例1】 (2011·江苏卷)设整数n≥4，P(a，b)是平面直角坐标系xOy中的点，其中a，
b∈{1，2，3，…，n}，a＞b. (1)记 An 为满足 a－b＝3 的点 P 的个数，求 An； (2)记 Bn 为满足13(a－b)是整数的点 P 的个数，求 Bn.
右边＝(m＋1)Cmk＋＋32.
而(m＋1)Cmk＋＋32－(m＋1)Cmk＋＋22＝(m＋1)（m＋2）（！k＋（3k）－！m＋1）！－（m＋（ 2）k＋！2（）k！－m）！
＝(m＋1)×（m＋2）（！k＋（2k）－！m＋1）！[(k＋3)－(k－m＋1)]＝(k＋2)m！（（kk＋－1m）＋！1）！ ＝(k＋2)Ckm＋1， ∴(m＋1)Cmk＋＋22＋(k＋2)Ckm＋1＝(m＋1)Cmk＋＋32，∴左边＝右边.
2.(2016·江苏卷)(1)求 7C36－4C47的值； (2)设 m，n∈N*，n≥m，求证： (m＋1)Cmm＋(m＋2)Cmm＋1＋(m＋3)Cmm＋2＋…＋nCmn－1＋(n＋1)Cnm＝(m＋1)Cmn＋＋22. (1)解 7C36－4C47＝7×20－4×35＝0. (2)证明 对任意的 m，n∈N*，n≥m， ①当 n＝m 时，左边＝(m＋1)Cmm＝m＋1，右边＝(m＋1)Cmm＋ ＋22＝m＋1，原等式成立. ②假设 n＝k(k≥m)时命题成立.即(m＋1)Cmm＋(m＋2)Cmm＋1＋(m＋3)Cmm＋2＋…＋kCkm－1＋(k ＋1)Cmk ＝(m＋1)Cmk＋＋22， 当 n＝k＋1 时，左边＝(m＋1)Cmm＋(m＋2)Cmm＋1＋(m＋3)Cmm＋2＋…＋kCmk－1＋(k＋1)Ckm＋(k ＋2)Cmk＋1＝(m＋1)Cmk＋＋22＋(k＋2)Cmk＋1，
4.数学归纳法 运用数学归纳法证明命题要分两步，第一步是归纳奠基(或递推基础)，证明当 n 取第一 个值 n0(n0∈N*)时命题成立，第二步是归纳递推(或归纳假设)，假设 n＝k(k≥n0，k∈N*) 时命题成立，证明当 n＝k＋1 时命题也成立，只要完成这两步，就可以断定命题对从 n0 开始的所有的正整数都成立，两步缺一不可.
解 (1)点P的坐标满足条件1≤b＝a－3≤n－3，所以An＝n－3. (2)设 k 为正整数，记 fn(k)为满足条件以及 a－b＝3k 的点 P 的个数，只要讨论 fn(k)≥1
的情形. 由 1≤b＝a－3k≤n－3k 知 fn(k)＝n－3k，且 k≤n－3 1， 设 n－1＝3m＋r，其中 m∈N*，r∈{0，1，2}， 则 k≤m，所以 Bn＝k∑＝m1fn(k)＝k∑＝m1 (n－3k)＝mn－3m（m2＋1）＝m（2n－23m－3）， 将 m＝n－31－r代入上式，化简得 Bn＝（n－1）6（n－2）－r（r－6 1）， 所以 Bn＝n（（nn－－ 613））6（，nn3－是2整 ）数 ，， n3不是整数.
第3讲 计数原理及二项式定理、数学归纳法
高考定位 高考对本内容的考查主要有：(1)分类加法计数原理、分步乘法计数原 理，B级要求；(2)排列与组合，B级要求；(3)二项式定理，B级要求；(4)数学归纳 法的简单应用，B级要求.
真题感悟
1.(2018·江苏卷)设n∈N*，对1，2，…，n的一个排列i1i2…in，如果当s<t时，有is>it，则 称(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表示).
即 m＝k＋1 时命题也成立. 综合①②可得原命题对任意 m，n∈N*，n≥m 均成立.
考点整合
1.两种计数原理 分类加法计数原理和分步乘法计数原理.
2.排列与组合 (1)排列的定义： 排列数公式：Anm＝n(n－1)(n－2)…(n－m＋1)＝（n－n！m）！(m≤n，m，n∈N*).(2)组合的定义：组合数
公式：C
m n
＝
n（n－1）（n－2）…（n－m＋1） m！
＝
n！ m！（n－m）！
(m≤n
，
m，
n∈N*)；
组合数性质：Cnm＝Cnn－m；Cnm＋Cmn －1＝Cnm＋1.
3.(1)二项式定理：(a＋b)n＝C0nan＋C1nan－1b＋…＋Cnn－1abn－1＋Cnnbn，其中 C0n，C1n，…， Cnn称为二项式系数； (2)C0n＋C1n＋…＋Cnn＝2n； (3)通项：Tr＋1＝Crnan－rbr，r≤n，n，r∈N*.
因此，fn＋1(2)＝fn(2)＋fn(1)＋fn(0)＝fn(2)＋n. 当 n≥5 时，fn(2)＝[fn(2)－fn－1(2)]＋[fn－1(2)－fn－2(2)]＋…＋[f5(2)－f4(2)]＋f4(2)＝(n－1) ＋(n－2)＋…＋4＋f4(2)＝n2－2n－2.
因此，当 n≥5 时，fn(2)＝n2－2n－2.