我总是分不清“排列(Permutation)”和“组合(Combination)”——哪个是哪个？
这里有个简单的记忆方法： 排列听起来很复杂，不是吗？确实如此。对于排列(Permutation)，每个小细节都很重要。爱丽丝、鲍勃和查理与查理、鲍勃和爱丽丝是不同的（请在此插入你朋友的名字）。
另一方面，组合(Combination)就随意多了。细节不重要。爱丽丝、鲍勃和查理与查理、鲍勃和爱丽丝是一样的。
排列用于列表（顺序重要），组合用于分组（顺序不重要）。
你知道吗，“组合锁(combination lock)”其实应该叫“排列锁(permutation lock)”。你输入数字的顺序很重要。
一个真正的“组合锁(combination lock)”会同时接受10-17-23和23-17-10作为正确密码。
排列(Permutation)：繁琐的细节
我们从排列(Permutation)开始，或者说 所有可能的方式 做某件事的方式。我们用了花哨的术语“排列(Permutation)”，所以我们要关心每一个细节，包括每个项目的顺序。假设我们有8个人：
1: Alice
2: Bob
3: Charlie
4: David
5: Eve
6: Frank
7: George
8: Horatio
在八名参赛者中，有多少种方式可以颁发一、二、三等奖？（金牌/银牌/铜牌）
我们将使用排列(Permutation)，因为颁发这些奖牌的顺序很重要。分解如下：
- 金牌：8个选择：A B C D E F G H（我让名字与字母对应，聪明吧？）。假设A赢得了金牌。
- 银牌：7个选择：B C D E F G H。假设B赢得银牌。
- 铜牌：6个选择：C D E F G H。假设……C赢得铜牌。
我们选了某些人获胜，但细节不重要：我们最初有8个选择，然后7个，然后6个。总选项数为$8 * 7 * 6 = 336$。
让我们看看细节。我们需要从8个人中选出3人的顺序。为此，我们从所有选项(8)开始，然后一次减少一个(7，然后6)，直到没有奖牌为止。
我们知道阶乘是：
不幸的是，那太多了！我们只想要$8 * 7 * 6$。如何让阶乘在5处“停止”？
这就是排列(Permutation)的酷炫之处：注意我们想要去掉$5 * 4 * 3 * 2 * 1$。它的另一个名称是什么？5的阶乘！
所以，如果我们计算8!/5!，我们得到：
我们为什么用了数字5？因为从8个中选3个奖牌后还剩5个。所以，更好的写法是：
其中 8!/(8-3)! 只是“使用8的前3个数”的一种花哨说法。如果我们有 n 总共有n个物品，想要按特定顺序选取 k r个，我们得到：
这就是花哨的排列公式：你有 n n个物品，想要找出 k r个物品可以排列的方式数：
组合(Combination)，嘿！
组合就简单多了。顺序不重要。你可以打乱顺序，结果看起来一样。假设我很抠门，买不起单独的Gold、Silver和Bronze奖牌。实际上，我只买得起空易拉罐。
有多少种方式可以把3个空易拉罐给8个人？
嗯，在这种情况下，我们选人的顺序无关紧要。如果我给Alice、Bob和Charlie每人一个罐子，这和先给Charlie、再给Alice、最后给Bob是一样的。不管怎样，他们一样失望。
这引出了一个有趣的问题——这里有一些冗余。Alice、Bob、Charlie = Charlie、Bob、Alice。我们先算算3个人有多少种重新排列方式。
嗯，第一个人有3种选择，第二个人有2种，最后一个人只有1种。所以有 $3 * 2 * 1$ 种方式重新排列3个人。
等等……这看起来有点像排列！你骗了我！
确实骗了你。如果你有N个人，想知道从中选出 所有 r个人的排列数，那就是N的阶乘，即N!
所以，如果我们有3个空罐子要送出，对于每一个选择的组合，都有3!即6种变化。如果我们想知道有多少种组合，我们只需 生成所有排列，再除以所有冗余除以每个排列的冗余数。在我们的例子中，有336种排列（从上面），除以每个排列的6种冗余，得到336/6 = 56。
通用公式是
意思是“找出从n个人中选k个人的所有方式，再除以k!种变体”。写出来，我们得到 组合公式(combination formula)即从n个物品中组合k个的方式数：
有时 $C(n,k)$ 写作：
也就是 二项式系数(binomial coefficient).
几个例子
这里有几个从排列（顺序重要）中区分组合（顺序无关）的例子。
组合：从10人中选3人组成团队。$C(10,3) = 10!/(7! * 3!) = 10 * 9 * 8 / (3 * 2 * 1) = 120$。
排列：从10人中选出一名主席、一名副主席和一名打水员。$P(10,3) = 10!/7! = 10 * 9 * 8 = 720$。
组合：从10种甜点中选3种。C(10,3) = 120。
排列：从10种甜点中按顺序列出你最喜欢的3种。P(10,3) = 720。
不要死记公式，要理解它们为什么成立。 组合听起来比排列简单，确实如此。组合的数量少于排列。
