This is a testing post for writing markdown with latex

排列组合

独立重复性事件

\: n^m

从n个不同物品中取一个物品，每次取一个，取m次的结果（考虑先后顺序）

n^m = n \times n \times n ... \times n \tag 1

\: A_n^n

从n个不同物品中取一个物品，每次取一个, 不放回，取n次(完）的结果.（考虑先后顺序）

第一次有n个结果， 依据独立性事件，第二次有n-1中结果，以此类推

A_n^n = n(n-1)(n-2)... \times 2 \times 1 \tag 2

\: A_n^m

从n个不同物品中取一个物品，每次取一个, 不放回，取m次(可能不取）的结果.（考虑先后顺序），未取到的结果有\: A_{n-m}^{n-m}种

A_n^m = \frac{A_n^n}{A_{n-m}^{n-m}} =  n(n-1)(n-2)...(n-m+1) \tag 3

\: C_n^m

从n个不同物品中取一个物品，每次取一个, 不放回，取m次(可能不取）的结果.（不考虑先后顺序）

C_n^m = \frac{A_n^m}{A_m^m} = \frac{n!}{m! \times (n-m)!} \tag 4

例子

3 * 4 的格子, 从左上走到右下角，只能往下或者往右。

• 分析：

总步数是固定的往右3步，往下2步, 一共5步， 不需看图，我们知道每一步只需要往前走(往右或往下）即可到达终点。（每行的具体位置确定了，路线就确定了）

以往下走为例，当往下的两步选定以后（因为是同类型，所以无顺序），路线便确定了，（因为选出的两步都是往下走，没有先后顺序）， 剩余的3步默认生成。

故其总的走法为

C_5^2 = \frac{A_5^2}{A_2^2} = \frac{5\times4}{2\times1} = 10 

• 动态规划

可以使用memory function， 使用一个数组即可

recurrence formula:

f[i,j] = f[i-1,j] + f[i, j-1] for i > 1 and j > 1

f[0,j] = f[i,0] = 1