无锡市2015年春学期普通高中期末考试高二理科数学压轴题:
将\(1\)到\(n\)的\(n\)个正整数按下面的方法排成一个排列,要求:除左边的第一个数外,每个数都与它左边(未必相邻)的某个数相差\(1\),将此种排列称为“\(n\)排列”.比如“\(2\)排列”为当\(n=2\)时,有\(1,2\);\(2,1\);共\(2\)种排列.“\(3\)排列”为当\(n=3\)时,有 \(1,2,3\);\(2,1,3\);\(2,3,1\);\(3,2,1\);共\(4\)种排列.
(1)请写出“\(4\)排列”的排列数;
(2)问所有“\(n\)排列”的结尾数只能是什么数?请加以证明;
(3)证明:“\(n\)排列”共有\(2^{n-1}\)个.
(1)解 \(1,2,3,4\),\(2,1,3,4\),\(2,3,1,4\),\(3,2,1,4\),\(2,3,4,1\),\(3,2,4,1\),\(3,4,2,1\),\(4,3,2,1\).
(2)解及证明 “\(n\)排列”的结尾数只能是\(1\)和\(n\).
首先证明以下引理:
引理 任何“\(n+1\)排列”中去掉数\(n+1\)后的\(n\)个数一定组成“\(n\)排列”.
若“\(n+1\)排列”中\(n+1\)排在\(n\)的右边,那么去掉这个数对其他所有数都没有影响,因此组成“\(n\)排列”;
若“\(n+1\)排列”中\(n+1\)排在\(n\)的左边,那么\(n+1\)只可能排在左边第一位,此时去掉这个数对其他所有数都没有影响,因此组成“\(n\)排列”.
根据引理,任何一个“\(n+1\)排列”都必然由某个“\(n\)排列”通过在适当的位置添加\(n+1\)得到.接下来用数学归纳法证明命题.
归纳基础显然成立.
假设“任何\(n\)排列”的结尾是\(1\)或\(n\),那么对于“\(n+1\)”排列,只有两种可能:
方式一 当“\(n\)排列”以\(n\)结尾时,直接在结尾添加\(n+1\),此时符合题意;
方式二 当“\(n\)排列”以\(1\)结尾时,或者直接在结尾添加\(n+1\),或者将\(n+1\)添加在非结尾的位置,此时“\(n+1\)排列”以\(1\)结尾,符合题意.
因此命题得证.
(3)证明 用数学归纳法证明.
归纳基础显然成立.
假设“\(n\)排列”共有\(2^{n-1}\)个,那么考虑“\(n+1\)排列”可以通过两种方法得到:
方式一 直接在“\(n\)排列”结尾添加\(n+1\),因此以\(n+1\)结尾的“\(n+1\)排列”有\(2^{n-1}\)个;
方式二 “\(n\)排列”的每个数都增加\(1\),然后在结尾添加\(1\),因此以\(1\)结尾的“\(n+1\)排列”有\(2^{n-1}\)个.
因此命题得证.
注 引理的证明非常重要,这是数学归纳法得以递推的关键步骤.
第三问不太严谨,没有说明这种构造无漏网之鱼
请结合引理仔细思考,\(2\)到\(n+1\)的符合题意的排列和“\(n\)排列”是一一对应的.