专题地图 › 并排比较
这两道题哪里一样?想好再点
P005944 · 经典的计数模型
有 名小朋友排成一圈,现在要将小朋友们两两配对,一共配成 对,并要求任意两名配对的小朋友之间恰好隔了 名小朋友。则共有种配对的方法。
P006925 · 经典的计数模型
设 ,映射 满足
其中 为 上的恒等映射,并且
求映射 的数目。
两题都先把允许的两两配对画成图,再数匹配。圆周配对要求每个顶点恰被覆盖,可分解成互不相交的环;对合映射还允许不动点,因此需要把未匹配顶点纳入递推,不能只保留完美匹配。
前题各分量都须完全配对;后题按端点是否固定及其匹配对象分类,允许部分匹配。