NOIP 普及 2015 第一轮 第 21 题：1234 的错位排列数量

题目

重新排列 $1234$ 使得每一个数字都不在原来的位置上，一共有种排法。

答案

9

题解

考点定位

本题考「错位排列」,对应大纲 2.1.5 组合（难度【3】）。

解题过程

4 个数的错位排列 D₄ = 9：

$$D_n=(n-1)(D_{n-1}+D_{n-2}),\;D_1=0,D_2=1\;\Rightarrow\;D_3=2,D_4=9$$

答案：9。

易错提醒

① 错位排列数列：0,1,2,9,44,…；② 枚举法验证：1 不在位 1 的全排列逐一筛。