社区讨论

求助,一个关于折线计数的问题

学术版参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@lochl5da
此快照首次捕获于
2023/10/30 13:55
2 年前
此快照最后确认于
2023/11/05 01:22
2 年前
查看原帖
现在考虑从 (0,0)(0,0) 每次往上或往右走到 (W,H)(W,H) 的所有路径。
选定直线 y=Ax+By=Ax+B,其中 A,BA,B 皆是整数且必须有 AW+BHAW+B\le H。称一条路径的权值是它触碰直线 y=Ax+By=Ax+B 的次数。
求用组合方法证明:所有路径的权值和与 BB 无关。更准确地说,所有路径的权值和等于
i=0W(W+H+1i)AWi\sum_{i=0}^W{W+H+1\choose i}A^{W-i}
这里有一份使用了一些代数推导的证明以供参考。

回复

2 条回复,欢迎继续交流。

正在加载回复...