回复352的一道集合计数

(44.71 KB)

2013-4-2 14:04

题目：设集合 $S_n=\{1,2,3,\ldots,n\}$，若 $X \subseteq S_n$，把 $X$ 的所有元素的乘积称为 $X$ 的容量（若 $X$ 中只有一个元素，则该元素的数值即为它的容量，规定空集的容量为 $0$）。若 $X$ 的容量为奇（偶）数，则称 $X$ 为 $S_n$ 的奇（偶）子集。则 $S_{2n}$（$n\in\mbb N^+$）的所有奇子集的容量之和为______。

不难发现 $(x+1)(x+3)(x+5)\cdots(x+2n-1)$ 的展开式中，除去最高次项 $x^n$ 外，各项的系数……与那些各类容量的和……实在不知怎么说，请自行理解……
反正所求的结果就是 $(x+1)(x+3)(x+5)\cdots(x+2n-1)-x^n$ 的系数之和，所以令 $x=1$，得到答案便是 $2^nn!-1$。

如果不理解上面的，也可以用递推去解。
记 $S_{2n}$ 时所求的和为 $f(n)$，那么当 $S_{2(n+1)}$ 时，多了一个元素 $2n+1$ 的选择，多出来的和就是 $2n+1$ 与前面那些奇数的容量和的积，以及它自己（仍然不知怎么表达得更清楚），所以有递推式
\[f(n+1)=f(n)+(2n+1)f(n)+2n+1,\]
变形为
\[f(n+1)+1=(2n+2)(f(n)+1),\]
这样也可以求出楼上的答案。

2# kuing
递推计数又一成功范例！
并且，母函数也派上用场，了不起！

(5.49 KB)

2013-4-2 17:51

还是2#容易理解

4# 李斌斌755
1楼在哪？

5# yes94
1#仍是kuing

5# yes94

可能刚才你看的时候卡掉了1#吧……

我发现夜深就不卡了，可能是服务器不太行，支持不住白天的浏览量……

集合 相关


mark

刚在人教论坛看到一道类似的：
http://bbs.pep.com.cn/forum.php?mod=viewthread&tid=2758890
方法应该一样

9# kuing


好巧好巧，偶笨得紧啦。

只能验证k是对的（似懂非懂，这个表达式就是题目的意思，数学真是精练之极）

$$f(x)=(x+1)(x+2^2-1)(x+2^3-1)\cdots(x+2^n-1)-x^n,\\f(1)=2\cdot 2^2 \cdots 2^n-1\\=2^{\frac{n(n+1)}2}-1$$

$$f(x)=(x+1)(x+2^2-1)(x+2^3-1)\cdots(x+2^n-1)-x^n,\\f(1)=2\cdot 2^2 \cdots 2^n-1\\=2^{\dfrac{n(n+1)}2-1}$$
isea 发表于 2013-5-13 17:06

不要滥用 \dfrac

不鸟你

你不觉得上下标用 \dfrac 后根本不像上下标？$2^{\frac12}\ne2^{\dfrac1{2}}$

13# kuing




改改

其实 a/b 这样的形式也不差啊，如果是我就会写成 $2^{n(n+1)/2}$

$2^{\dfrac12}+2^{\frac12}+2^{1/2}$

呵呵，不扯输入了，想想怎么给人教那边的解释吧，我是不会表达的了。

根据n个括号相乘，括号里元素的选取就知道意义啦！

感觉展开式很诡异。明明是一堆数相乘，却变成一堆数相加。类似“积化和差”！

……

19# kuing
我的水平只能这样理解