盒子和球,具体如下编号1到5五个球,分别放入编号1到5的五个盒子里(每个盒子只放一球),要求全部球不能对号入座(即1号球不能放入1号盒子...),有多少种放法?推广到编号n个球和编号N个盒子呢?

问题描述:

盒子和球,具体如下
编号1到5五个球,分别放入编号1到5的五个盒子里(每个盒子只放一球),要求全部球不能对号入座(即1号球不能放入1号盒子...),有多少种放法?推广到编号n个球和编号N个盒子呢?

一号盒子不能放1,只有4种放法,二号盒子不能放2,有3种放法(即一号盒子没有放2)或4种放法(一号盒子放的是2),。。。所以有44种放法.
f(5)=5!(1-1/1!+1/2!-1/3!+1/4!-1/5!)=44
推广到编号n个球和编号N个盒子
f(n)=n!(1-1/1!+1/2!-1/3!+。。。(-1)^n/n! )

第一个盒子有5种放法,第二个盒子有4种放法,。。。第二个盒子有2种放法,第一个盒子有1种放法,总共有5*4*3*2*1=5!=120种放法,全部球对号入座只有一种放法,所以不能全部球对号入座的放法有120-1=119种。
推广就是n!-1种。

这是错排问题.
d[1]=0
d[2]=1
d[3]=2
d[4]=9
d[5]=44
…………
d[n]=(n-1)*(d[n-1]+d[n-2])

这个就是简单的排列问题。
第一个盒子有5种放法,第二个盒子有4种放法,。。。第二个盒子有2种放法,第一个盒子有1种放法,总共有5*4*3*2*1=5!=120种放法,全部球对号入座只有一种放法,所以全部球不能对号入座的放法有120-1=119种。
推广就是n!-1种。