[组合] 一道排列组合题

本帖最后由 nash 于 2012-8-23 23:26 编辑

RT
求前100个正整数构成的集合中，元素和为5的倍数的子集个数

本主题由 kuing 于 2013-1-19 18:19 分类

海盗船长

金牌会员

UID: 12
帖子: 292

2^#

发表于 2012-8-24 11:15

令 $$f(x)=2^{20} (1+x)^{40}(1+x^2)^{40}$$
则有$$N=\frac{1}{5}(f(1)+f(\alpha)+f(\alpha^2)+f(\alpha^3)+f(\alpha^4))-1=253530120045645880299341479935$$个非空子集满足要求。
其中$\alpha=\exp\left(\frac{2\pi i}{5}\right)$

kuing

管理员

UID: 1
帖子: 3992

3^#

发表于 2012-8-24 11:23

2# 海盗船长

这么大

基本信息：kuing，GG，19880618~?，地道广州人，高中毕业，无业游民，不等式爱好者，论坛混混；
现状：冇钱又冇样、冇型又冇款、冇身材又冇文采、冇学历又冇能力、冇高度冇速度冇力度兼夹冇野做！（粤语）

海盗船长

金牌会员

UID: 12
帖子: 292

4^#

发表于 2012-8-24 11:45

3# kuing

嗯，和$\frac{2^{100}-1}{5}=253530120045645880299340641075$很接近

isea

论坛元老

UID: 5
帖子: 753

5^#

发表于 2012-8-24 14:05

2# 海盗船长

能“初始化”一下么？

kuing

管理员

UID: 1
帖子: 3992

6^#

发表于 2012-8-24 14:10

5# isea

我也看不懂

海盗船长

金牌会员

UID: 12
帖子: 292

7^#

发表于 2012-8-24 17:41

本帖最后由海盗船长于 2012-8-24 17:42 编辑

其实就是用的母函数，先把$1$到$100$按模$5$分成$5$类：$-2,-1,0,1,2\pmod 5$，每一类含有$20$个数后考虑$$g(x)=\left(1+\frac{1}{x^2}\right)^{20}\left(1+\frac{1}{x}\right)^{20}(1+1)^{20}(1+x)^{20}(1+x^2)^{20}$$中$x^{5k}\;(k \in \mathbb{Z})$项系数之和，再用$5$次单位根把这些项分离出来即可。

kuing

管理员

UID: 1
帖子: 3992

8^#

发表于 2012-8-24 18:06

好像大概基本上差不多应该算是可以说看懂了吧……niubility solution

返回列表