一道数学题，据说只有智商超过150的人才能做出来8个老师分别教8个班，考试时，8个老师不能再自己教的班监考。问：有多少种分配方法N个老师分别教N个班，考试时，N个老师不能再自己教

Question

一道数学题，据说只有智商超过150的人才能做出来
8个老师分别教8个班，考试时，8个老师不能再自己教的班监考。问：有多少种分配方法
N个老师分别教N个班，考试时，N个老师不能再自己教的班监考。求：通项公式
公式我知道，求证明

Answer 1

设N的通项是P(N)
那么P(N)=(N-1)[(N-1)P(N-2)+(N-2)P(N-3)], N≥4
其中：
①N=1时： 0种
②N=2时： 1种
③N=3时： 2种
计算得到：P(8)=14833
递推式证明如下：
假设有N个老师，以其中一个老师a开始，他要教不同的班级，那么有N-1种选择
在这之后，不妨假设他选了一个老师b,那么接下来分成两种可能讨论：
①假如b选择a教的班级，那么余下的N-2个老师有P(N-2)种监考方式
②假如b没有选择a教的班级，那么余下的N-2个老师可能选择a教的班级，假设为c
b和剩余的N-3个老师进行监考调配，又分为两种情况：
1. b选择c，那么有P(N-3)
2. b不选择c，那么有P(N-2)
综合以上，可以得到递推式：P(N)={P(N-2)+(N-2)[P(N-2)+P(N-3)]}
化简得到：P(N)=(N-1)[(N-1)P(N-2)+(N-2)P(N-3)], N≥4