本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-13 08:22:32

设 $g(i)$ 表示选出恰好 $i$ 个元素进行组合的方案数，$f(i)$ 表示选出至少 $i$ 各元素组合的方案数，那么有

$$f(n) = \sum\limits_{i=0}^n {n\choose i}g(i)$$

有些时候 $f(i)$ 好计算，而 $g(i)$ 由于恰好的那个限制，不好计算，我们考虑怎么反推。

事实上，有

$$g(n) = \sum\limits_{i=0}^n {n \choose i}(-1)^{n-i}$$

这个用组合数的性质是好证的。

于是我们就可以将 $f(i)$ 转化为 $g(i)$，例题，也是我接触这玩意儿的第一道题是 P10596 集合计数。

$k$ 个元素已经确定了为交，这里有 $n \choose k$ 种方案，那么还剩下 $n - k$ 个数状态仍待确定。我们要把这 $n - k$ 个数划分为