专题地图 › 经典的计数模型
在六元素集合S上,有多少个函数 f:S→S 满足对每个x都成立 f(f(x))=x?
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
把函数写成不动点与互换数对。
条件先保证f为双射,其置换循环只能长1或2。设互换对有k个,则 k=0,1,2,3,方案数为 6!/[2kk!(6−2k)!]。四项为1、15、45、15,和为76。 所求为 76。
二元循环的内部交换不产生新循环,循环之间也不计次序,所以要除 2kk!。
核心工具:排列的循环结构与递推
专题卡:先分清匹配、独立选择和着色,再按图结构计数
反馈先保存在这台设备上,在「我的学习」页可以一起复制给老师。
已记下,谢谢!