题目 将 $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$ 排列”的排列数； 答案1 $ 8 $ 解析1 $1,2,3,4$，$2,1,3,4$，$2,3,1,4$，$2,3,4,1$，$3,2,1,4$，$3,2,4,1$，$3,4,2,1$，$4,3,2,1$，共 $8$ 个． 备注1 问题2 问所有“$n$ 排列”的结尾数只能是什么数？请加以证明； 答案2 “$n$ 排列”的结尾数只能是 $1$ 和 $n$ 解析2 “$n$ 排列”的结尾数只能是 $1$ 和 $n$．首先证明以下引理：<br/><case>引理</case>任何“$n+1$ 排列”中去掉数 $n+1$ 后的 $n$ 个数一定组成“$n$ 排列”．<br/>若“$n+1$ 排列”中 $n+1$ 排在 $n$ 的右边，那么去掉这个数对其他所有数都没有影响，因此组成“$n$ 排列”；<br/>若“$n+1$ 排列”中 $n+1$ 排在 $n$ 的左边，那么 $n+1$ 只可能排在左边第一位，此时去掉这个数对其他所有数都没有影响，因此组成“$n$ 排列”．<br/>根据引理，任何一个“$n+1$ 排列”都必然由某个“$n$ 排列”通过在适当的位置添加 $n+1$ 得到．接下来用数学归纳法证明命题．<br/>归纳基础显然成立．<br/>假设任何“$n$ 排列”的结尾是 $1$ 或 $n$，那么对于“$n+1$”排列，只有两种可能：<br/><case>方式一</case>当“$n$ 排列”以 $n$ 结尾时，直接在结尾添加 $n+1$，此时符合题意；<br/><case>方式二</case>当“$n$ 排列”以 $1$ 结尾时，或者直接在结尾添加 $n+1$，或者将 $n+1$ 添加在非结尾的位置，此时“$n+1$ 排列”以 $1$ 结尾，符合题意．<br/>因此命题得证． 备注2 问题3 证明：“$n$ 排列”共有 $2^{n-1}$ 个． 答案3 略 解析3 用数学归纳法证明．<br/>归纳基础显然成立．<br/>假设" $n$ 排列"共有 $2^{n-1}$ 个，那么考虑" $n+1$ 排列"可以通过两种方法得到：<br/><case>方式一</case>直接在" $n$ 排列"结尾添加 $n+1$，因此以 $n+1$ 结尾的" $n+1$ 排列"有 $2^{n-1}$ 个；<br/><case>方式二</case>" $n$ 排列"的每个数都增加 $1$，然后在结尾添加 $1$，因此以 $n+1$ 结尾的" $1$ 排列"有 $2^{n-1}$ 个．<br/>因此命题得证． 备注3 每日一题[173]数学归纳法．