Question

一个数学排列组合的问题

n个人每个人有一个座位，问他们全部没有坐在自己座位上的情况有多少种。

另外一个拓展问题，有n个小朋友和n个玩具，每个小朋友都有一个自己最讨厌的，小明有m（m<=n-1）个已经玩过的玩具（不包括他不喜欢的），他想玩没玩过的玩具，问有多少种分法使得所有小朋友都满意。

请给出公式及简要解析谢谢。

Answer 1

我想想啊...

第一个问题:
设F[n]表示有n个人 每个人都没坐在自己位置上的情况数
F[1]=0
F[2]=1
F[n]=(n-1)*(F[n-1]+F[n-2])

当然如果求通项公式 我们用容斥原理
F[n]=n!-C(n,1)*(n-1)!+C(n,2)*(n-2)!-C(n,3)*(n-3)!+C(n,4)*(n-4)!......
=n! * (1/2!-1/3!+1/4!-1/5!+1/6!-...)

这样F[n]就搞定了我把F[n]前7项给你看 就是n个人 每个人都不坐自己位置上的方法数
F[1]=0
F[2]=1

F[3]=2

F[4]=9

F[5]=44

F[6]=265

F[7]=1854

第二个问题:
根据第一问 我想题意是每个人讨厌的玩具应该是互不相同的

然后问题转化为n个小朋友和n个玩具 每个人都拿到自己喜欢的玩具，并且小明拿到的是他没玩过的玩具的情况数

小明玩过m个玩具,所以还剩下n-m-1个玩具可以玩(因为其中有个是他讨厌的)
然后这个问题具有对称性，可以好好想想，也就是说小明拿到他喜欢的n-1个中每个玩具，然后其它人拿到自己喜欢的玩具情况数是相等的 当然等于F[n]/(n-1) 这个肯定能整除的啦!

所以问题就解决了 小明拿n-m-1个其中一个，其它人拿喜欢的 方案数是 F[n]/(n-1)*(n-m-1)

不知道对不对 这个问题还是想了很久的 希望楼主满意 不懂的可以问我 ^-^

Answer 2

1. (n-1)*(n-1)!

2. (n-m-1)(n-1)!