组合数几乎是万物之根。
\(n\) 个元素里选 \(k\) 个，不看顺序，那么选第一个，有 \(n\) 种可能，第二个时，只剩 \(n-1\) 种选法，以此类推。比如，\(3\) 个里选 \(2\) 个，选法就是，\(3 * 2\)。通用公式是：
$$ \binom nk = \frac{n!}{(n-k)!k!} $$为什么要除以 \(k!\)？因为组合不看顺序。先从 3 个里选一个时，可以先选的是 \(A\)，也可以是 \(B\)，如果是 \(A\)，第二个就可能选 \(B\)，反之亦然。排列方式不重要，所以要除以排列方式的数量。那一个长度 \(k\) 的序列，有多少种排列方式呢？
排列 #
对 \(k\) 个元素排列，第一个位置，有 \(k\) 种选择，第二个位置，还剩 \(k - 1\)，以此类推，直到最后的位置，只剩一个元素，一个选择，于是有：
$$ k! $$种排列方式。
n+m 的表达 #
如果元素总数是 \(n+m\) 个，选其中的 \(n\) 个组合，那么总可能性是：
$$ \binom {n+m}{n} = \frac{(n+m)!}{n!m!} $$为啥？首先，分子肯定是元素总量的阶乘。和前一种表达里的 \(n\) 一样，只是这次换成了 \(n+m\)。
再看分子，\(n!\) 代表要选择的 \(n\) 个元素的排列方式数；同理，\(m!\) 代表不选的（也是一种选）\(m\) 个元素的排列方式数。根据前面的讨论，排列方式不重要，所以应当除以排列方式的总可能性，即 \(m!n!\)。
对称性 #
很显然，上面讨论揭示了，从 \(n + m\) 个里选 \(n\) 个，逻辑上完全等于选 \(m\) 个：
$$ \binom {n+m}{n} = \binom {n+m}{m} = \frac{(n+m)!}{n!m!} $$可以理解为，选和反选（不选）的操作是平等的，对称的；即 \(n\) 和 \(m\) 是平等、对称的；所以除数都是 \({n!m!}\)。我也更喜欢这个视角看待组合数，对称往往指向更简洁优雅的结构。