搜索结果
查询Tags标签： 二项式，共有 8条记录-
二项式反演
二项式反演 定理 \(1\)：\(F(n)=\sum_{i=0}^{n}{{n\choose i}G(i)}\Leftrightarrow G(n)=\sum_{i=0}^{n}{(-1)^{n-i}{n\choose i}F(i)}\) 证明： 提取系数有 \(F[n]=\sum_{i=0}^{n}{{n\choose i}G[n]}\) \(\displaystyle \to \frac{F[n]}{n!}=\sum_{i=0}^{n}{\frac{1}{(n-…
2022/7/24 6:25:17 人评论 次浏览 -
重修 二项式反演
我只知道容斥不知道二项式反演。 反演，顾名思义就是有两个函数 \(f,g\)，知道 \(f\) 用 \(g\) 表示后反过来 \(g\) 用 \(f\) 表示。 二项式反演有一个无敌对称的柿子： \[f(n)=\sum_{i=1}^n(-1)^i\binom{n}{i}g(i)\iff g(n)=\sum_{i=1}^n(-1)^i\binom{n}{i}f(i) \]这个柿…
2022/6/21 23:19:45 人评论 次浏览 -
「 学习笔记 」二项式定理与组合恒等式
二项式定理与组合恒等式 前置知识 \[\dbinom {n} {k} = \mathrm{C} _ n ^ k = \dfrac {n!} {(n - k)! \times k!} \]二项式定理 二项式定理：设 \(n\) 是正整数，对于一切 \(x\) 和 \(y\) \[{(x + y)} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n - k}…
2021/11/17 23:13:59 人评论 次浏览 -
「 学习笔记 」二项式定理与组合恒等式
二项式定理与组合恒等式 前置知识 \[\dbinom {n} {k} = \mathrm{C} _ n ^ k = \dfrac {n!} {(n - k)! \times k!} \]二项式定理 二项式定理：设 \(n\) 是正整数，对于一切 \(x\) 和 \(y\) \[{(x + y)} ^ n = \sum \limits _ {k = 0} ^ n \dbinom {n} {k} x ^ k y ^{n - k}…
2021/11/17 23:13:59 人评论 次浏览 -
省内联考 10.17 随机过程（process）
简要题意： 在长度为 \(l\) 的数轴上均匀随机 \(n\) 个区间，求被至少 \(k\) 个区间覆盖的长度期望。 这个描述已经足够形式化了，下面直接开始推导。 设 P_x 为每个点合法的概率，二项式反演有：$$P_x=\sum_{i=k}^n\binom{n}{i}(2x(1-x))^i(1-2x(1-x))^{n-i}$$ 枚举 \(k…
2021/10/18 6:10:45 人评论 次浏览 -
省内联考 10.17 随机过程（process）
简要题意： 在长度为 \(l\) 的数轴上均匀随机 \(n\) 个区间，求被至少 \(k\) 个区间覆盖的长度期望。 这个描述已经足够形式化了，下面直接开始推导。 设 P_x 为每个点合法的概率，二项式反演有：$$P_x=\sum_{i=k}^n\binom{n}{i}(2x(1-x))^i(1-2x(1-x))^{n-i}$$ 枚举 \(k…
2021/10/18 6:10:45 人评论 次浏览 -
二项式反演入门
对于序列 \(\{f_n\}\) 和 \(\{g_n\}\)，通过 \(f\) 计算出 \(g\) 叫做正演，通过 \(g\) 计算出 \(f\) 叫做反演。 形式 二项式反演讲的是： \[g_n=\sum_{i=0}^n\binom{n}{i}f_i \Leftrightarrow f_n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}g_i \]证明 将组合数展开得到： \[\…
2021/8/8 23:39:06 人评论 次浏览 -
二项式反演入门
对于序列 \(\{f_n\}\) 和 \(\{g_n\}\)，通过 \(f\) 计算出 \(g\) 叫做正演，通过 \(g\) 计算出 \(f\) 叫做反演。 形式 二项式反演讲的是： \[g_n=\sum_{i=0}^n\binom{n}{i}f_i \Leftrightarrow f_n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}g_i \]证明 将组合数展开得到： \[\…
2021/8/8 23:39:06 人评论 次浏览
