Question

排列组合一个问题

偶然看到一个题目: 10块相同的糖分给4个小朋友，允许有人分不到，请问有多少种分法。答案是286 有什么简便易懂的方法解答吗？

Answer 1

首先转化问题，我们设第i个小朋友分到ai个糖，则a1+a2+a3+a4=10,ai>=0，即求不定方程的解个数。然后我们令bi=ai+1,则方程化为b1+b2+b3+b4=14,bi>=1。

我们把14块糖依次排好，然后用3根筷子去分离这14块糖，使得糖成为四份，第i份就是bi。那么有多少种筷子插入14块糖的方法就有多少个解。由于每一份至少一个，所以筷子不能放在同一个空挡中。所以一共14块糖，有13个空挡，从中取出3个空挡插入筷子。一共C(3,13)=286种分法

（图中没有14块糖，只是模拟一下，更加好看）

Answer 2

这个问题叫做“错排问题”。

错排问题递推公式的推导：
当n个编号元素放在n个编号位置，元素编号与位置编号各不对应的方法数用M(n）表示，那么M(n-1）就表示n-1个编号元素放在n-1个编号位置，各不对应的方法数，其它类推.
第一步，把第n个元素放在一个位置，比如位置k，一共有n-1种方法；
第二步，放编号为k的元素，这时有两种情况⑴把它放到位置n，那么，对于剩下的n-1个元素，由于第k个元素放到了位置n，剩下n-2个元素就有M(n-2）种方法；⑵第k个元素不把它放到位置n，这时，对于这n-1个元素，有M(n-1）种方法；
综上得到
M(n)=(n-1）[M(n-2）+M(n-1）]
特殊地，M⑴=0,M⑵=1
下面通过这个递推关系推导通项公式：
为方便起见，设M(k)=k!N(k),(k=1,2，…，n)
则N⑴=0,N⑵=1/2
n>=3时，n!N(n)=(n-1）（n-1）！N(n-1）+(n-1）！N(n-2）
即 nN(n)=(n-1）N(n-1）+N(n-2）
于是有N(n)-N(n-1）=-[N(n-1）-N(n-2）]/n=(-1/n)[-1/(n-1）][-1/(n-2）]…（-1/3）[N⑵-N⑴]=(-1）^n/n!
因此
N(n-1）-N(n-2）=(-1）^(n-1）/(n-1）！
N⑵-N⑴=(-1）^2/2!
相加，可得
N(n)=(-1）^2/2!+…+(-1）^(n-1）/(n-1）！+(-1）^n/n!
因此
M(n)=n![(-1）^2/2!+…+(-1）^(n-1）/(n-1）！+(-1）^n/n!]
可以得到
错排公式为M(n)=n！（1/2!-1/3!+…..+(-1）^n/n!)

Answer 3