求助组合数

回复帖子

@Acfboy 2021-05-31 14:09 回复

$n$ 个球排成一列,选择 $p$ 个,且不能有连续的 $k$ 个被选中的方案数是多少?

其实又双叒叕是求助昨天 cf 的 E

@wxy_  2021-05-31 15:56 回复 举报

令 $p_i$ 为恰好第 $i$ 次放完停止的概率。

$$ E=\sum_{i=1}^np_i\times i=\sum_{i=1}^np_i\sum_{1\le j\le i} 1=\sum_{i=1}^n\sum_{1\le j\le i}p_i =\sum_{i=1}^n \sum_{j=i}^n p_j $$

$$ P[i]=\sum_{j=i+1}^n p_j $$

那么

$$ E=\sum_{i=0}^{n-1} P[i] $$

考虑一下 $P[i]$ 的组合意义。

那其实就是恰好选 $i+1$ 个后不合法,恰好选 $i+2$ 个不合法...的概率的和。

并且任意两个事件是不交的,因此代表的一定是一个不交并。

那么其组合意义即:选 $i$ 个合法的概率。

对这个概率求个和 $ok$ 了。

@cmll02  2021-06-01 11:26 回复 举报

原 来 不 止 我 一 个

(虽然我发现了还是不会/kk)

@Acfboy 2021-06-01 18:31 回复 举报

其实这个推导就相当于把每一次加入分开来考虑,因为加入的对答案的贡献一定是 $1$, 而当前的合法方案除以总方案数就是概率,所以对这个概率求和就是期望了。

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。