错位排列+圆排列

Answer 1

错位排列是什么

有n个有序的元素，应有n!个不同的排列。如果一个排列使得所有的元素不在原来的位置上，则称这个排列为错排。

贺卡问题

同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送的贺年卡。四张不同的贺年卡不同的分配方式有：A、6种 B、9种 C、11种 D、23种。

人数用n表示，当n=1时，取法为0， 当n=2时，取法为1种（1取2，2取1）， 当n=3时，取法为2种（1取2，2取3，3取2，或者1取3，2取1，3取2）， 当n=4，四个同学的编号分别为1，2，3，4；对应各自的贺卡编号为1，2，3，4。1号同学只能取2，3，4号贺卡，有三种取法，即(n-1)种。

假设1号同学取2号贺卡时，剩下2，3，4号同学和1，3，4号贺卡，考虑2号同学：若不取1号贺卡，相当于转化为3个人的错排；若取1号贺卡，问题转化为3、4号同学的错排取法，因此，1号同学取2时的取法是：(n-1)的错排数＋(n-2)的错排数。这样得到递推公式：F(1)=0; F(2)=1; F(n)=(n-1) * [f(n-1)＋f(n-2)] (n>2)

循环排列（circular permutation）亦称圆排列、环排列等，是排列的一种，指从n个不同元素中取出m（1≤m≤n）个不同的元素排列成一个环形，既无头也无尾。

两个循环排列相同当且仅当所取元素的个数相同并且元素取法一致，在环上的排列顺序一致。

环排列没有首末之分，这五个元素随便从哪一个元素开始，绕一个方向转过去，都不改变它们的相对顺序；直线排列则首末分明，原来排末位，调换排首位，已改变它们的相对顺序。

将a,b,c,d,e五个元素排列在圆周上，确定其中的一种，然后将各元素依顺时针（或逆时针）方向绕圆周转动一个位置，连续转动四次（转动五次就恢复到原来的位置），连同开始的一种共得五种，在这五种排列里，元素所占的位置虽然有所改变，但元素之间的相对顺序依旧未变。在循环排列里，这五种排列只能算作一种排列。

五个元素的循环全排列中的一种，变成直线排列则有5种，设循环排列有x种，则直线排列有5x种，但五个元素的直线全排列有5!种，所以得到 5x = 5! 得： x =（ 5！） / 5 = 4!