Question

这样的排列组合题怎么做？

一个方格状街道！横纵街道数未知！人从左下开始走！走到右上结束！最近走法有几种？本来有个棋盘状的图！不能够给出！很无奈！耐烦高手想像下！

Answer 1

我给你一个正确的回答，你得把分给俺呢，本来要吃饭去了，看这个题目很有意思。其实一点都不难。你的问题我见过，有个前提，不能向左和下走，因为如果可以的话，那答案是无穷个走法（想象一下，如果可以走回头路，那么我在没走到右上角之前总是在一个走过的路上徘徊，是不是有无穷个走法）。好了，根据这个前提，你的问题可以这样：

比如有N行M列的街道。相互交叉形成类似围棋盘的网状。街道交叉点我们记为1个点，这个点很重要。每2个点就会把一条路分成2段，由于不能走回头路，所以每条路走一次，走到右上角就必须走N-1+M-1个被分段的路（想象一下有3行3列的田字格，是不是需要走3-1+3-1个被分的段才能到达右上角）。

好了，知道了要走N+M-2个路段后，我们要把这些段分下类，不多，就分成横排与竖排，也就是说需要横着走的路段有多少（M-1)，需要竖着走的路段有多少(N-1)。那么不同的走法就是横着的路段如何被分配到竖着的交叉点中去，或者竖着的路段如何被分配到横着的交叉点中去。

这就是一个分箱子问题，在本例中，就是把N-1个竖着的路段分到M个箱子（交叉点）中，每个箱子最少分到0个路段，或者把M-1个横着的路段分到N个箱子（交叉点）中，每个箱子最少分0个路段。

问题到这，你应该知道用分箱子法来解这个问题。篇幅有限，只做提示，用插板法与求整数向量个数法来解这道题。（如果你多给分我乐意效劳 ^_^ )

在这里我不阐述如何分箱子了，你应该会所以问题的答案是：
若把N-1个路段分到M个点中有
(N-1+M-1)!/(N-1+M-1-M+1)!*(M-1)!=(N+M-2)!/(N-1)!*(M-1)!
若把M-1个路段分到N个点中有
(N-1+M-1)!/(N-1+M-1-N+1)!*(N-1)!=(N+M-2)!/(M-1)!*(N-1)!

Answer 2

对角线走上去可以走得通的话.就只有1种可能.
因为两点之间.线段就短.

Answer 3

小学 数奥问题