一、什么是排列，什么是组合？
排列
从 n 个不同元素中，任取 m(m≤n) 个元素，按照一定的顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列。
组合
从 n 个不同元素中，任取 m(m≤n）个元素并成一组，叫做从 n 个不同元素中取出 m 个元素的一个组合。
通俗地讲
A (排列)：指把几个不但选出来，还要进行排列 如 A42A_4^2A42 是指从 4 个物品中选出 2 个来，而且对它们的顺序是有要求的，顺序不一样，结果则不一样。A42=4×3=12A_4^2 =4×3=12A42=4×3=12 C (组合)：是指从 n 个数中选取几个出来，不排列，只组合。如 C42C_4^2C42 是指从 4 个中选 2 个，不管它们的内部的顺序。C42=C_4^2 =C42= 4×32×1=6\cfrac{4×3}{2×1} = 62×14×3=6. 总结：排列与元素的顺序有关，组合与顺序无关。如 231 与 213 是两个排列；2+3+1 的和与 2+1+3 的和是一个组合。
由上可得，排列数和组合数的求法代码如下：
(1) 排列数
m 就是需要减 1 的次数。
int A(int n, int m) {
int res = 1;
for (int i = m; i >= 1; i--) {
res *= n; //n × n-1 × n-2 × ... n-m，m就是需要减1的次数
n--;
}
}
(2) 组合数
与求排列数一样，求组合数也是对公式的实现，不过组合这里有个小技巧可以对代码进行优化，那就是利用组合的互补率：Cnm=Cnn−mC_n^m = C_n^{ n - m}Cnm=Cnn−m 来减少循环执行次数。
版本一
由上可得 Cnm=C_n^m=Cnm= Anmm!\cfrac{A_n^m}{m!}m!Anm，而 m!m!m! =Amm=A_m^m=Amm，故代码可表达为：
int C(int n, int m) {
m = Math.min(m, n-m);
int numerator = A(n, m); //分子
int denominator = A(m, m); //分母
return numerator / denominator;
}
版本二
根据 Cnm=C_n^m=Cnm= Anmm!\cfrac{A_n^m}{m!}m!Anm，但我们注意到，AnmA_n^mAnm 的代码实现中，m 一直遍历到 1，所以在方法 A() 的代码实现中我们简单的加入对 m!m!m! 的求解即可，不需要为了求组合数还得多写一个求排列数的函数。
int A(int n, int m) {
int up = 1; //分子
int down = 1; //分母
m = Math.min(m, n-m);
for (int i = m; i >= 1; i--) {
up *= n; //累乘得到分子
n--;
down *= i; //累乘得到分母
}
return up / down;
}
