排列组合问题

Question

有12345个人，做12345个位置，要求不能有任何一个人对号入座，有几种坐法？我晓得答案是44，怎么推导的？如果问题换成n个人，有没有推导公式？
满意追加100分

Answer 1

设 an 是n个人的坐法.

我们考虑 a(n+1), 即 n+1 个人的坐法。看最后一个人。他可以坐在 1，。。。，n 这n个位置。
设其坐在i位置, 1<=i<=n. 只有两种情形：
1. 第i 个人坐在 n+1 位置。于是，去掉 i， n+1 这两个人后，正好是 n-1个人的a(n-1)种坐法中的一种。
2. 第i 个人不坐在 n+1 位置。这时，如果把坐在第n+1位置的人安排坐在第i位置，则，正好是 n个人的a(n)种坐法中的一种。
同时，
1‘。 任给n-1个人的a(n-1)种坐法中的一种，任给1<=i<=n, 都可以按1那样插入第i， n+1 两个人，得到一种（n+1)个人的坐法。
2‘。 任给n个人的a(n)种坐法中的一种，任给1<=i<=n, 都可以按2那样插入第 n+1 个人，得到一种（n+1)个人的坐法。

综上，有：
a(n+1)= n(an + a(n-1))

a1=0, (这个算规定的)
a2=1
a3= 2
a4=3(3)=9
a5=4(2+9)=44

一般的 an 应该可以通过生成函数解出来。

Answer 2

接 zhaoyi_628 的回答。
设 an 是n个人的坐法
显然 a2=1
假设 已知 a2,a3,...,a(n-1)
那么 n个人中n-1人对号入座等于n人对号入座，是1种坐法。
k人对号入座有 a(n-k)*C(n,k) 种坐法 ，k=1,2,...,n-2
故 an=n!-1-[a(n-1)*C(n,1)+a(n-2)*C(n,2)+...+a3*C(n,n-3)+a2*C(n,n-2)]

Answer 3

这题应该用减法P(5,5)=120
4个人对号入座1
3个人对号入座C(5,3)=10

2个人对号入座C(5,2)*2=20

1个人对号入座C(5,1)*9=45

一共120-1-10-20-45=44

Answer 4

这种题目没有很好的方法算 只能找特列
2开头的有11个
21453 21534
23154 23451 23514
24513 24531 24153
25134 25431 25413
根据排列组合的对称性原理 3,4,5开头的也有11个
一起有 11x4=44个。

Answer 5

此乃欧拉错装信封问题，百度一下吧。
思路就是用容斥原理，最后表示成一个求和
n!(1-1/1!+1/2!-1/3!+...+(-1)^n*1/n!) 渐进~n!/e
http://baike.baidu.com/view/1926671.htm