Question

数学问题，关于排列组合或是图论的。

有1,2,3,4,5....n;一组数，问这n个数的排列中满足任意两个相邻的自然数不相邻的排列的个数。即排列中不允许出现1,2；2,3或是2,1等这样的元素排列方式。

Answer 1

应用容斥原理，得
n!-2(n-1)*(n-1)!+2(n-2)*(n-2)!-2(n-3)*(n-3)!+...+(-1)^(i) *2(n-i)*(n-i)!+...+(-1)^(n-1) *2
不知道能不能化简，你可以自己试试化简。

解释：
n个元素的排列数为n!
将相邻的，如(1,2)看成一个整体，则是n-1个元素的排列(n-1)!
(1,2),(2,3),(3,4)一共有(n-1)个这样的，(2,1),(3,2),(4,3)...再乘2
然后将(1,2,3)看成一个整体。。。

Answer 2

第一步、从n个数中任取两个数，共有C(2,n)种
第二步、所取出的两个数的排列共有P(2,2)种
第三步、从n个数中任取两个相邻的数，共有（n-1）种

所以从n个数中任取两个不相邻的数组成的全排列共有[C(2,n)-(n-1)]*P(2,2)

当n大于等于10时，以上计算不包含单个元素的个十(百千万.....)位的位置互换。如18和23,的组合只有1823和2318两种

追问

谢谢，可能我说的不大明白，我要问的不是任取两个不相邻的数字组成的全排列的个数，而是满足没有相邻数字相邻的n个数的全排列。

追答

（n个数的全排列）—（两个数两邻的全排列）—（三个数相邻的全排列）—（四个数相邻的全排列）—（……）—（n个数相邻的全排列列）=你想要的结果
这个问题很难，以上只能说是一个思路，实际操作起来都是要讨论才能算出的。比如1、2、3、4、5、6、7、8、9共九个数相邻的全排列只有1个，8个或者7个或者6个或者5个数相邻的也很好算，但四个相邻的就有两种情况，比如只有一组四个相邻数的是一种情况，有两组四个相邻数的又是一种情况，因为是9个数，两组四个相邻数也才8个数，实际中完全会出现这种情况。再比如三个数相邻的有三个情况需要讨论，两个数相邻的有四种情况需要讨论。所以以上问题不可能在这上面几句话就能表达的清楚，再加上你给的题目是不确定的“n个数”。

追问

是的，我也知道这个问题很难，但这个问题也仅仅是我要解决的一个更大的问题的一个小分支，如果这个问题解决了，大问题也可能被解决，这个问题已经是我经过思考提炼过的了，仍然很复杂，但是很关键。

Answer 3

n-2*n-3*n-4...........就是(n-2)!

Answer 4

n-2