Question

排列组合的问题

若将1,2,3,4,5，……，n个数字分别放入标号为1,2,3,4,5，……，n的盒子中，一对一，且数字与盒子的标号不能相同，问有几种排法
我是个高中生，最好能让我容易理解一点

Answer 1

这个是装错信封类的变题

为方便，我们先把n个不同的元素及相应的位置都编上序号1，2，…，n，并且约定：在n个不同元素的排列中

1°若编号为i(i=1，2，…，n)的元素排在第i个位置，则称元素i在原位；否则称元素i不在原位．

2°若所有的元素都不在原位，则称这种排列为n个不同元素的一个错排(若每个元素都在原位则称为序排)．

按照上面约定，“装错信封问题”即为n个不同元素的错排问题，则可构建“装错信封问题”的数学模型为

在n个不同元素的全排列中，有多少种不同的错排？

3 模型求解

应用集合中的容斥原理，我们就可得到“装错信封问题”的数学模型的求解公式．

设I表示n个不同元素的全排列的集合

Ai(i=1，2，…，n)为元素i在原位的排列的集合

Ai∩Aj(1≤i＜j≤n)为元素i与j在原位的排列的集合……

A1∩A2∩…∩An为n个元素的序排的集合．

则它们的排列数(即各个集合中元素的个数)分别为

|I|=n！

|Ai|=(n－1)！

|Ai∩Aj|=(n－2)！

……

……

|A1∩A2∩…∩An|=(n－n)！=0！

根据容斥原理即得“装错信封问题”的数学模型的求解公式(即n个不同元素的错排数)为f(n) = n![1-1/1!+1/2!-1/3!+……+(-1)^n*1/n!] 

如果不理解上面的解法还有如下容易理解的方法

设n个信和信封有A(n)种装法。形成数列{A(n)}

显而易见的是A(1)=0,A(2)=1

而n+1个信和信封的每一种装错装法都可以看作两种情况：

1.是n个信和信封的装错装法，将第n+1封信与前n封中的某一封对调

2.是n个信和信封中，某一个装对了，其余n-1个信和信封的装错装法，再将将第n+1封信与前n封中的装对的那一封对调

1.有n*A(n)种情况

2.有n*A(n-1)种情况

所以A(n+1)=n*A(n)+n*A(n-1)=n*(A(n)+A(n-1))

这样就可以依次类推,但不易求出通项公式. 

可以这样求: