双射法

还是有点震撼的。

对于正整数 $n$ ，我们称⼀个正整数列 $a_{[1,k]}$ 是 $n$ 的有序划分，当且仅当 $\sum a_i=n$ 。

给定 $n\ge 2$ ，求满⾜ $\sum_{i=1}^k[2\mid a_i]$ 是偶数的有序划分个数（即偶数的个数为偶数）。

$2^{n-2}$ 。

若 $a_1=1$ 则将其与下一个合并，改变了偶数的奇偶性。

否则将 $a_1$ 变为 $1$ 和 $(a_1-1)$ ，改变了偶数的奇偶性。

我们就构造了一个对合（ $f(f(x))=x$ ）。

这是⼀⼤类双射问题的通⽤做法：构造⼀个不会映射到⾃⼰的对合，这样就可以把所有组合对象分为数量相等的两类。

求解：

$\sum_{k=0}^m\binom{m+k}{k}2^{-k}$

$2^m$ 。

生成函数上的理解就是一个卷积。

考虑组合意义证明，我们两边乘以 $2^m$ ，想要证明 $\sum_{k=0}^m\binom{m+k}k2^{m-k}=2^{2m}$ 。

我们考虑组合意义，右边描述的是长为 $2m$ 的 $01$ 序列，那我们看左边是什么。