一道计数小题的分析

2021年北京大学优秀中学生暑假学堂数学测试的第一题如下：

求集合{1,2,⋯,2021}的非空子集中元素和为3的倍数的集合个数．

这是一道很陈的题了，例如2013年的一道天津高联预赛题就几乎一样：

如果集合{1,2,⋯,9}的某个非空子集中所有元素之和是3的倍数，则称该子集为忐忑子集，那么，忐忑子集的个数是_____．

这类问题一般能够使用生成函数进行求解．

考虑多项式

公式：f(x)=(1+x)(1+x^2)\cdots(1+x^{2021})

我们来研究𝑓(𝑥)展开式的组合意义．

事实上，𝑓(𝑥)展开式中每一项的次数均是由若干个不同的𝑥^(𝑖)相乘产生的，从而𝑥^(𝑛)的系数就是和为𝑛的子集个数．

于是在本题中，我们只需求𝑓(𝑥)的展开式中，次数为3的倍数的所有项的系数之和．容易联想到一类初中的多项式题目(以下题为例)：

已知(3𝑥−1)^(5)=∑_(𝑖=0)^(5)𝑎_(𝑖)𝑥^(𝑖)，求𝑎_(4)+𝑎_(2)+𝑎_(0)的值．

本题求解关键在于将次数按奇偶分成两组分别求和，于是可以赋值𝑥=1和𝑥=−1．

那么回到原题，怎样的赋值能将次数为3的倍数的项选取出来呢？容易想到赋值为1，𝜔，𝜔^(2)(𝜔为三次单位根)，解答如下：

设𝑓(𝑥)=∑_(𝑖=0)^(𝑛)𝑎_(𝑖)𝑥^(𝑖)．则

公式：\begin{align*} f(\omega)=&\sum\limits_{3\mid i}a_i+\omega\sum\limits_{3\mid i-1}a_i+\omega^2\sum\limits_{3\mid i-2}a_i\\ =&2^{673}(1+\omega)^{674}(1+\omega^2)^{674}\\ =&2^{673} \end{align*}

公式：\begin{align*} f(\omega^2)=&\sum\limits_{3\mid i}a_i+\omega\sum\limits_{3\mid i-2}a_i+\omega^2\sum\limits_{3\mid i-1}a_i\\ =&2^{673}(1+\omega)^{674}(1+\omega^2)^{674}\\ =&2^{673} \end{align*}

三式相加，结合1+𝜔+𝜔^(2)=0得：

公式：3\sum\limits_{3\mid i}a_i=2^{2021}+2^{673}+2^{673}

即

注意到本题要求的为非空子集个数，故答案为：