[组合] 5人7项目

本帖最后由 realnumber 于 2012-6-18 08:57 编辑

5个人报名参加7项运动项目，必须满足条件P“每个项目至少1人且每人至少报名1项”，则有几种不同情况？
方法一如下：
设$f(m,n)$表示满足条件P的m人，n个项目的数目,显然$f(1,n)=f(m,1)=1$,$f(m,n)=f(n,m)$.
$(2^{m}-1)C^{m}_{m}f(m,n-1)+2^{m-1}C^{m-1}_{m}f(m-1,n-1)+...+2C^{1}_{m}f(1,n-1)=f(m,n)$-----（1）
穷举法得到一般有$f(n,2)=f(2,n)=3^n-2$,
利用上述递推公式和穷举法验证了$f(2,2)=7$,$f(2,3)=f(3,2)=25$,$f(3,3)=265$,
以下都是递推公式得到，但愿没算错，
$f(4,2)=79,f(4,3)=2161,f(4,4)=41503$,
$f(5,2)=241$,$f(5,3)=16081$,$f(5,4)=693691$,
$f(6,2)=727$,$f(6,3)=115465$,$f(6,4)=10924399$,
$f(7,2)=2185$.$f(7,3)=816985$,$f(7,4)=167578321$
$f(7,5)=(2^{7}-1)C^{7}_{7}f(7,4)+2^{6}C^{6}_{7}f(6,4)+2^{5}C^{5}_{7}f(5,4)+...+2^{2}C^{2}_{7}f(2,4)+2C^{1}_{7}f(1,4)=26666591281$
方法二：（逐步淘汰原理）
$f(m,n)=f(n,m)=(2^n-1)^m-C^{n-1}_n(2^{n-1}-1)^m+C^{n-2}_n(2^{n-2}-1)^m-C^{n-3}_n(2^{n-3}-1)^m+....$---（2）
那么$f(7,5)=(2^5-1)^7-C^{4}_5(2^{4}-1)^7+C^{3}_5(2^{3}-1)^7-C^{2}_5(2^{2}-1)^7+C^1_5(2-1)^7=26666530801$
计算错了？还是方法问题？
解释：
（1）左边第一项意思是n-1个项目，添一项，这项人数可以为1，2，...，或m；第二项的意思是，添一项，这一项必须有参加0项的1人，再可以添加人数为0，1，2，...或m-1;第三项意思，添一项必须有参加0项的2人，再可以加0，1，2，...,或m-2人；...
（2）右边第一项意思是每项目至少1人（但不满足每人至少1项目），这就需要减去其中仅n-1人参加m个项目，（每项目至少1人）,继续需要....

本主题由 kuing 于 2013-1-19 18:41 分类