2020-2021:teams:legal_string:jxm2001:other:结论_1
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:other:结论_1 [2020/08/02 17:02] jxm2001 |
2020-2021:teams:legal_string:jxm2001:other:结论_1 [2021/03/06 10:58] (当前版本) jxm2001 [1、树上最远距离] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 结论 ====== | + | ====== 结论 1 ====== |
| ===== 1、树上最远距离 ===== | ===== 1、树上最远距离 ===== | ||
| 行 17: | 行 17: | ||
| int dp[MAXN][3],hson[MAXN],dis[MAXN]; | int dp[MAXN][3],hson[MAXN],dis[MAXN]; | ||
| void dfs1(int u,int fa){ | void dfs1(int u,int fa){ | ||
| - | dp[u][0]=dp[u][1]=dp[u][2]; | + | dp[u][0]=dp[u][1]=dp[u][2]=hson[u]=0; |
| for(int i=head[u];i;i=edge[i].next){ | for(int i=head[u];i;i=edge[i].next){ | ||
| int v=edge[i].to; | int v=edge[i].to; | ||
| 行 99: | 行 99: | ||
| $(n-i)！$ 表示满足该元素处于长度为 $i$ 的循环的条件后其他元素的排列可能，$n!$ 表示全部可能性。 | $(n-i)！$ 表示满足该元素处于长度为 $i$ 的循环的条件后其他元素的排列可能，$n!$ 表示全部可能性。 | ||
| + | |||
| + | ===== 6、 组合数 ===== | ||
| + | |||
| + | $${n \choose m-1}+{n \choose m}={n+1 \choose m}\tag{1}$$ | ||
| + | |||
| + | 证明 | ||
| + | |||
| + | $$ | ||
| + | \begin{equation}\begin{split} | ||
| + | {n \choose m-1}+{n \choose m}&=\frac {n!}{(m-1)!(n-m+1)!}+\frac {n!}{m!(n-m)!}\\ | ||
| + | &=\frac {n!}{(m-1)!(n-m+1)!}+\frac {n!}{m!(n-m)!}\\ | ||
| + | &=\frac {(n+1)!}{m!(n-m+1)!}(\frac m{n+1}+\frac{n-m+1}{n+1})\\ | ||
| + | &=\frac {(n+1)!}{m!(n-m+1)!}={n+1 \choose m} | ||
| + | \end{split}\end{equation} | ||
| + | $$ | ||
| + | |||
| + | $$\sum_{i=0}^n {m+i-1 \choose i}={m+n \choose n}\tag{2}$$ | ||
| + | |||
| + | 证明 | ||
| + | |||
| + | $$ | ||
| + | \begin{equation}\begin{split} | ||
| + | \sum_{i=0}^n {m+i-1 \choose i}&={m-1 \choose 0}+{m \choose 1}+{m+1 \choose 2}+\cdots {m+n-1 \choose n}\\ | ||
| + | &={m \choose 0}+{m \choose 1}+{m+1 \choose 2}+\cdots {m+n-1 \choose n}\\ | ||
| + | &={m+1 \choose 1}+{m+1 \choose 2}+\cdots {m+n-1 \choose n}\\ | ||
| + | &={m+2 \choose 2}+\cdots {m+n-1 \choose n}\\ | ||
| + | &\cdots\\ | ||
| + | &={m+n \choose n} | ||
| + | \end{split}\end{equation} | ||
| + | $$ | ||
| + | |||
| + | $$F(x)=\sum_{n=0}^{\infty}{m+n \choose n}x^n=\frac 1{(1-x)^{m+1}}\tag{3}$$ | ||
| + | |||
| + | 考虑数学归纳法证明。 | ||
| + | |||
| + | $m=0$ 时 $F(x)=\sum_{n=0}^{\infty}{n \choose n}x^n=\sum_{n=0}^{\infty}x^n=\frac 1{(1-x)}$，证毕。 | ||
| + | |||
| + | $m\gt 0$ 时，有 | ||
| + | |||
| + | $$ | ||
| + | \begin{equation}\begin{split} | ||
| + | \frac 1{(1-x)^{m+1}}&=\frac 1{(1-x)^m}\frac 1{(1-x)}\\ | ||
| + | &=\left(\sum_{n=0}^{\infty}{m+n-1 \choose n}x^n\right)\left(\sum_{n=0}^{\infty}x^n\right)\\ | ||
| + | &=\sum_{n=0}^{\infty}x^n\sum_{i=0}^n{m+i-1 \choose i}\\ | ||
| + | &=\sum_{n=0}^{\infty}{m+n \choose n}x^n | ||
| + | \end{split}\end{equation} | ||
| + | $$ | ||
| + | |||
| + | |||
2020-2021/teams/legal_string/jxm2001/other/结论_1.1596358971.txt.gz · 最后更改: 2020/08/02 17:02 由 jxm2001
