今天来更新一下我万年不更得博客
求 \(n\) 维平面内从 \((0,0,0,...,0)\) 到 \((x_1,x_2,x_3,...,x_n)\) 的路径方案数
首先我们可以考虑二维平面内的情况,显然是
\[{x_1 + x_2 \choose x_1}
\]
表示从总共走 \(x_1+x_2\) 个格子里面选 \(x_1\) 个格子是向下走的格子方案。
那么我们也也可以从而推到 \(n\) 维的情况。
\[{\sum^{n}_{i=1}x_i \choose x_1} \cdot {\sum^{n}_{i=1}x_i - x_1 \choose x_2} \cdot {\sum^{n}_{i=3}x_i - x_1 - x_2 \choose x_3} \cdot ........ \cdot {\sum^{n}_{i=n}x_i \choose x_n}
\]
表示将:从 \(\sum^{n}_{i=1}x_i\) 中选 \(x_1\) 个地方在第 \(1\) 维的方向上面走的方案数乘上在除了第 \(1\) 维走的地方即剩下的 \(\sum^{n}_{i=2}x_i\) 里选 \(x_2\) 个地方在第 \(2\) 维方向上面走的方案数再乘上.......
可以化简:
\[\frac{(\sum^{n}_{i=1}x_i)!}{x_1! \cdot (\sum^{n}_{i=1}x_i - x_1)!} \cdot \frac{(\sum^{n}_{i=1}x_i - x_1)!}{x_2! \cdot (\sum^{n}_{i=1}x_i - x_1 - x_2)!} \cdot \frac{(\sum^{n}_{i=1}x_i - x_1 - x_2)!}{x_3! \cdot (\sum^{n}_{i=1}x_i - x_1 - x_2 - x_3)!} \cdot .... \cdot \frac{x_n!}{x_n!}
\]
消消乐之后就成了如下式子:
\[\frac{(\sum^{n}_{i=1}x_i)!}{x_1! \cdot x_2! \cdot x_3! \cdot ...... \cdot x_n!}
\]
即为:
\[\frac{(\sum^{n}_{i=1}x_i)!}{\prod^{n}_{i=1}x_i!}
\]