Question

急求组合数学题目答案 用网格路径方法证明组合公式

Answer 1

这个...你只要明白一件事我认为你就知道怎么证明了.
C(m+n,m)在网格路径里等价于:
从一个m*n的网格的左下角顶点(0,0)出发走到右上角顶点(m,n),只能向前或向上前进的不同路径个数.(这个你必须知道....)
那么:从(0.0)出发到(m,n)必定经过点(m-1,n),(m,n-1).
而从(m-1,n)或者(m,n-1)到(m,n)的路径数都是1(当为前者时，只能向左到(m,n),而后者只能向上).
你认为通过(m-1,n)的路径是否可以也通过(m,n-1)?这显然不可能.
因此我们可以认为从(0.0)到(m,n)的路径等于到(m-1,n)和(m,n-1)的路径之和.
于是就有:
C(m+n,m)
=C(m-1+n,m-1)+C(m+n-1,m)
=C(m+n-1,m)+C(m+n-1,m-1).