集合A(1≤∣A∣≤100)上不同的等价关系┅共多少个
一行,一个整数n(1≤n≤100)表示集合A的元素个数。
集合A上不同等价关系的个数模109+7即输出其个数模。(因为当∣A∣比较大时A上的等价关系数是个巨大的数字,比如∣A∣=100时其上等价关系的个数是个116位的数字。)
首先说说什么是等价关系如果关系R是集合A上的關系,并且关系R满足自反对称,传递那么关系R就是A上的等价关系。
然后再说说什么是等价类如果[x]R={y|y∈A
那么这个等价类和等价关系有什麼关系呢,听着有点拗口嗷
举的例子可能不够好,我是想说明有的[x]可能是相等的集合,也就是说等价关系的个数就小于等于集合元素嘚个数多个等价类是一个集合能想到什么呢?像是编号的小球放在不编号的盒子里并且盒子不空呢这样一说是不是有那么一点点模糊嘚思路啦。
那么我们来想一下都有哪几种可能性呢。
那么分析一下小球放在盒子里有什么规律吧如果只有一个盒子的话,只可能有一種放法;如果盒子和小球的个数相等那也是只有一种放法;如果小球数量比盒子还少呢,那就没有意义了对吧