Question

数学问题，6个教室分给3个老师，每个老师至少教一个班，一个班由一个老师教，求方案数？

6个教室分给3个老师，每个老师至少教一个班，一个班由一个老师教，求方案数？
还有7个教室3个老师的情况？

Answer 1

6个教室先分3组再分配给3个教师，共有三种分组方法：2+2+2.1+1+4.1+2+3.
所以答案是（c62*c42*c22/a33+c61*c51*c44/a22+c61*c52*c33）*a33

追问

这个大概就是最常规的方法了吧。。
请问有什么高效一点的方法来解决教室和老师比较多的问题吗？

Answer 2

6个教室3∧6-3*2∧6
7个教室3∧7-3*2∧7

追问

不懂你的算法？而且貌似算错了。。。
我算出来的结果是540和1806，和你的537,1083分别差个3

追答

每个教室有3个老师3种选择，6个教室就是有3的6次方种方案，扣除只有2个老师的方案3（2的6次方-2），再扣除只有1个老师的方案3，呃，是错了，少加了3
6个教室3∧6-3*2∧6+3
7个教室3∧7-3*2∧7+3

追问

容斥？用这种方法教室数多的时候挺好算的对吧？是不是老师数大了就很麻烦？

追答

还可以这么算
6个教室6*5*4*3∧3/P（3,3）=20*3∧3
7个教室7*6*5*3∧4/P（3,3）=35*3∧4
也即m个教室n个老师就是m！÷（m-n）！ ×n∧（m-n） ÷ P（n，n）

追问

假如有6个教室4个老师用容斥该怎么列式呢？我列的式子好长qwq
这个新的算法又不懂了。。
我之前用的是递推
dp[i][j]表示，把个i不同的教室分给j个老师
于是dp[i][j]=j*(dp[i-1][j]+dp[i-1][j-1])

追答

=m！÷（m-n）！ ×n∧（m-n） ÷ P（n，n）=m！÷（m-n）！ ×n∧（m-n） ÷ n！
=C（m，n）×n∧（m-n）
这算法就是先排老师，第1个老师有教室数m种选择，最后剩下的m-n间教室每间有n个选择，n个教师排列有n！种重复，先保证每个老师都有1个教室。

追问

我举个例子吧，10个教室10个老师，用这个算出来答案岂不是为1？
而且35*3^4=2835也不对吧，第一个应该是数据特殊了www

追答

是哦。。。第二种算法有问题。。。
第一种算法多了列式太麻烦，第二种有疏漏