Question

n*m格的矩阵,从左上顶点到右下顶点,最短路径有C(m+n,n)/C(m+n,m)种,为什麼?

Answer 1

从左上到右下的最短路径,必然包括m次向右的移动和n次向下的移动.

把m次向右的移动记为a1,a2,……am；n次向下的移动记为b1,b2,……,bn.

将上述(m+n)个不相同的元素,按从小到大的顺序混合排列起来,共有多少种排列,就正是本题的答案.

注意,由于排列时要求从小到大,所以,上述排列数并非(m+n)个元素的全排列.但是,将m个a再任意排列,同时,再将n个b任意排列一下,就成了全排列.

设所求的排列数为p　,由以上分析,则有　p×m!n!=(m+n)!

所以,答案就是(m+n)!/(m)!(n)!