网格(1,1)到(x,y) 加法、乘法、排列组合原理

前言： 因为一个小问题卡壳，发现自己对加法、乘法、排列组合的混淆。当然，如果像在学校中做的数学题一样，即已经抽象成了数学语言，我相信大部分人都不会犯错误。而在算法竞赛的过程当中，需要我们自己建模也好抽象也好，在这个过程当中容易出现混淆，所以下面通过解决问题来重新理解一遍这几种原理的内容和区别。

问题：给定一张网格图，你在(1,1),走到(x,y)有多少走法？

思路： 见下图。

首先上图是一种比较原始的做法。而本身这个题目可以这样抽象，即从(1,1)到 (x,y)共需要 (y-1) + (x-1) 步，并且必须向右走 x-1 步，向下走 y-1 步。而只要确定了哪几步向右走，则剩余的几步则都是向下走，即确定了整体怎么走。所以这种做法就抽象成了组合问题，例如上图中到(4,3)点的走法有10种，即等于 $C_5^3$ ，其中5 = 4-1 + 3-1，3 = 4-1。

我的错误在于想当然的将最后的结果用 (y-1)*(x-1) 计算所得，而这就是乘法原理和组合原理的混淆，所以计算不是问题，关键在于分析问题及建立模型。下面给出几种原理的内容，以找出区别。

加法原理： 如果完成事件A有n种方法，完成事件B有m种方法，那么完成两者之一有n+m种方法。
乘法原理： 如果完成事件A有n种方法，完成事件B有m种方法，那么先完成A再完成B有n*m种方法。
排列：
- 从n个数中有序地选出m个数的方案数是多少？
- 第一个数有n种取法，第二个数有n-1种取法……第m个数有n-m+1种取法。
- $\prod_{i=0}^{m-1}{(n-i)}=\frac{n!}{(n-m)!}$
- 记为 $A_{n}^m$
组合：
- 从n个数中无序地选出m个数的方案数是多少？
- 先有序地取m个数。
- 那么无序的m个数会被取到m!次。
- $\frac{A_{n}^m}{m!} = \frac{n!}{m!(n-m)!}$
- 记为 $C_{n}^{m}$ --> $C_{n}^{m} = C_{n-1}^{m} + C_{n-1}^{m-1}$
  
  ( PS：从 n 个里面选 m 个，所以对于第 n 个来说其有选与不选两种：
  1. 选择它，则意味着要从 n-1 个当中选择 m-1 个，即 $C_{n-1}^{m-1}$
  2. 不选择它，则意味着要从 n-1 个当中选择 m 个，即 $C_{n-1}^{m}$ ；
    
    -> 上述这种方法又叫做选择计数法，也是一种常见的递推思想。)

网格(1,1)到(x,y) 加法、乘法、排列组合原理

问题：给定一张网格图，你在(1,1),走到(x,y)有多少走法？

相关推荐