用网格路径方法证明组合公式

来源:学生作业帮助网 编辑:作业帮 时间:2024/10/05 02:46:39
用网格路径方法证明组合公式
xSkOP+&JK}pc ۀκ,'T8ND͔-Fcsz;eD49&yok0O^̽ykWf2 ^KxWKDYQS_D:4%}4-9~Q|SڲNqTZMVr& i&2TZr %j#\K/e4+IH )/QNQDZxJ!YeN%S % ) RY^$hZdDNEQ'e,8 \,4G0|g(Ir-`k9Zk!pck O:v ox& GCXo-I} +~dhv_[Ψ~EX؋DQݑ2jh#.6G&{هP;_ Jef 갛:_4tkE4WEJN mXoZ<&y^~{uUk#i_Wgh¸9yP={] <(_FAAչ16Ͼ o\pe=  7\S'T'Xr

用网格路径方法证明组合公式
用网格路径方法证明组合公式
    

用网格路径方法证明组合公式
这个...你只要明白一件事我认为你就知道怎么证明了.
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).