代数推导天地灭,组合意义保平安。其实啥也不会
将题目转化为,有 \(k\) 个带标号的奶龙,要分给 \(i\) 个带标号的树气,其中这 \(i\) 个树气是从 \(n\) 个树气中选出来的,求总方案数。
首先你考虑到会有很多树气选不到奶龙,所以我们只考虑那些选到奶龙的树气,设 \(f_{i, j}\) 为 \(i\) 个奶龙分给 \(j\) 个树气的方案数(每个树气都得有奶龙),那么答案如下:
\[\sum_{i = 1}^k f_{k, i} 2^{n - i}
\]
\(2^{n - i}\) 是因为要枚举还有哪些奶龙被选了,然后此时 \(f_{i, j}\) 是一个经典问题,用第二类斯特林数拆开即可。