如果的某个非空子集中所有元素之和是3的倍数,则称该子集为“忐忑子集”,那么,“忐忑子集”的个数是。
分数写 a/b,根号写 √ 或 sqrt,π 写 pi 也可以。
先按模3的余数把数字分成三类,把和值是否整除转成所选各类的个数条件。
余数为零的元素可以最后任取;对另外两类逐个数目分类,再统一去掉空集,能避免列举全部子集。
余数0、1、2三类各有三个数。设从余数1类选了 个、余数2类选了 个,则和值为0模3当且仅当 。在 中,这等价于 或 。
因此这六个数的合法选法有
余数0的三个数各自可取可不取,再乘 。其中只有全不取的一种是空集,故所求为 。
母集全部元素之和45可被3整除,所以取补集把和值余1与余2的子集互相对应。含空集的余0子集为176个,另外两类各168个,总数 ,与全部九元子集数相符。删空集时只删一种,不应把所有只由3的倍数组成的非空子集也删掉。
子集和的同余问题可先压缩成各余数类的选择个数,再用组合数保留同一类内的不同选择。可以自由加入的零余数元素带来独立乘子;非空性通常最后单独处理,而不是破坏前面的乘法结构。
需以子集和母函数提取模三余零项
已记下,谢谢!