一、什么是排列，什么是组合？
排列
从 n 个不同元素中，任取 m(m≤n) 个元素，按照一定的顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列。
组合
从 n 个不同元素中，任取 m(m≤n）个元素并成一组，叫做从 n 个不同元素中取出 m 个元素的一个组合。
通俗地讲
A (排列)：指把几个不但选出来，还要进行排列 如
A
4
2
A_4^2
A42 是指从 4 个物品中选出 2 个来，而且对它们的顺序是有要求的，顺序不一样，结果则不一样。
A
4
2
=
4
×
3
=
12
A_4^2 =4×3=12
A42=4×3=12 C (组合)：是指从 n 个数中选取几个出来，不排列，只组合。如
C
4
2
C_4^2
C42 是指从 4 个中选 2 个，不管它们的内部的顺序。
C
4
2
=
C_4^2 =
C42=
4
×
3
2
×
1
=
6
\cfrac{4×3}{2×1} = 6
2×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) 组合数
与求排列数一样，求组合数也是对公式的实现，不过组合这里有个小技巧可以对代码进行优化，那就是利用组合的互补率：
C
n
m
=
C
n
n
−
m
C_n^m = C_n^{ n - m}
Cnm=Cnn−m 来减少循环执行次数。
版本一
由上可得
C
n
m
=
C_n^m=
Cnm=
A
n
m
m
!
\cfrac{A_n^m}{m!}
m!Anm，而
m
!
m!
m!
=
A
m
m
=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;
}
版本二
根据
C
n
m
=
C_n^m=
Cnm=
A
n
m
m
!
\cfrac{A_n^m}{m!}
m!Anm，但我们注意到，
A
n
m
A_n^m
Anm 的代码实现中，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;
}