2020-2021:teams:intrepidsword:zhongzihao:conclusion
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:zhongzihao:conclusion [2021/02/10 18:03] toxel [划分数] |
2020-2021:teams:intrepidsword:zhongzihao:conclusion [2021/03/26 11:41] (当前版本) toxel Irwin–Hall distribution |
||
|---|---|---|---|
| 行 293: | 行 293: | ||
| 设有一串 $S$，从一个空串开始，每次等概率随机往后面加一个字符，包含 $S$ 时停止。期望长度为 $\sum_{i=1}^{|S|}[1..i\text{ is border}]|\Sigma|^{i}$。[[random_string|证明]] | 设有一串 $S$，从一个空串开始，每次等概率随机往后面加一个字符，包含 $S$ 时停止。期望长度为 $\sum_{i=1}^{|S|}[1..i\text{ is border}]|\Sigma|^{i}$。[[random_string|证明]] | ||
| + | ===== 二项式反演 ===== | ||
| + | |||
| + | $$ | ||
| + | f_{n}=\sum_{i=0}^{n}(-1)^{i}{n\choose i}g_{i}\Leftrightarrow g_{n}=\sum_{i=0}^{n}(-1)^{i}{n\choose i}f_{i}\\ | ||
| + | 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} | ||
| + | $$ | ||
| + | |||
| + | ===== 广义二项式定理 ===== | ||
| + | |||
| + | $(x+y)^{\alpha}=\sum_{k=0}^{+\infty}{\alpha\choose k}x^{\alpha-k}y^{k}$，其中 ${\alpha\choose k}=\frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!}=\frac{(\alpha)_{k}}{k!}$。 | ||
| ===== 其它 ===== | ===== 其它 ===== | ||
| 行 395: | 行 405: | ||
| [[similar_euclid|证明]] | [[similar_euclid|证明]] | ||
| + | |||
| + | ===== 莫比乌斯反演 ===== | ||
| + | |||
| + | $$ | ||
| + | f_{n}=\sum_{d\mid n}g_{d}\Leftrightarrow g_{n}=\sum_{d\mid n}\mu(\frac{n}{d})f_{d}\\ | ||
| + | f_{n}=\sum_{n\mid d}g_{d}\Leftrightarrow g_{n}=\sum_{n\mid d}\mu(\frac{d}{n})f_{d} | ||
| + | $$ | ||
| + | |||
| + | 若 $t$ 为完全积性函数，且 $t(1)=1$，那么 | ||
| + | |||
| + | $$ | ||
| + | f_{n}=\sum_{i=1}^{n}t(i)g_{\lfloor\frac{n}{i}\rfloor}\Leftrightarrow g_{n}=\sum_{i=1}^{n}\mu(i)t(i)f_{\lfloor\frac{n}{i}\rfloor} | ||
| + | $$ | ||
| ===== 其他 ===== | ===== 其他 ===== | ||
| 行 452: | 行 475: | ||
| 一个森林内部节点的度数平方和等于 2*(长度为 2 的路径数+长度为 3 的路径数)。 | 一个森林内部节点的度数平方和等于 2*(长度为 2 的路径数+长度为 3 的路径数)。 | ||
| + | 一个 $n\times m$ 的四连通网格图的生成树数量为 $\prod_{i=1}^{m-1}\prod_{j=1}^{n-1}(4\sin^2(\pi i/2m)+4\sin^2(\pi j/2n))$ | ||
| ====== 概率论 ====== | ====== 概率论 ====== | ||
| 行 458: | 行 482: | ||
| 在 $[0,n]$ 上随机游走，从 $x$ 出发，每次等概率移动 $\pm 1$，走到 $0$ 的期望步数是 $x(2n-x)$。 | 在 $[0,n]$ 上随机游走，从 $x$ 出发，每次等概率移动 $\pm 1$，走到 $0$ 的期望步数是 $x(2n-x)$。 | ||
| + | ===== Irwin–Hall distribution ===== | ||
| + | |||
| + | 设有 $n$ 个独立同分布的变量 $X_{i}\sim U[0,1]$，那么 $\sum_{i=1}^{n}X_{i}$ 的累积分布函数是 $\frac{1}{n!}\sum_{k=0}^{\lfloor x\rfloor}(-1)^{k}{n\choose k}(x-k)^{n}$，概率密度函数是 $\frac{1}{(n-1)!}\sum_{k=0}^{\lfloor x\rfloor}(-1)^{k}{n\choose k}(x-k)^{n-1}$ | ||
| ====== 其它 ====== | ====== 其它 ====== | ||
2020-2021/teams/intrepidsword/zhongzihao/conclusion.1612951409.txt.gz · 最后更改: 2021/02/10 18:03 由 toxel
