前言

排列组合公式一直都记不住,每次用到了都会去网上搜索。当然,没记住肯定是因为没理解。最近想搞懂它,在知乎看到这篇文章之后,有了些许启发,下面来说说我的一点理解。

排列组合公式

$n$个元素中选$k$个
排列数$A(n,k)=\frac{n!}{(n-k)!}=n(n-1)\cdots(n-k+1)$
组合数$C(n,k)=\frac{A(n,k)}{k!}=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots1}$

我的理解

当一种事件发生次数难以计算时,我们往往会用大的事件发生次数除去重复计算的次数。

排列数中,首先,很容易理解的是,全排列的次数是元素个数的阶乘。当不是全排列时,是什么重复计算了呢?是未被选择元素的全排列!所以就有这种递归定义的排列数公式

$$ A(n,k)=\begin{cases} n! & n = k \\ \frac{A(n,n)}{A(n-k,n-k)} & n \neq k \end{cases} $$

组合数中,先取排列数,然而组合数并不关注顺序,所以组合数相对于排列数多算了被选择元素的排序,也即是选择元素的全排列!所以组合数公式为
$$
C(n,k)=\frac{A(n,k)}{A(k,k)}
$$

后记

本想把标题写成简单理解排列组合公式,但当我写完重新审视了一遍我的理解,我想把标题改成复杂理解排列组合公式😂,我估计本来不理解排列组合公式的人看了我的理解,可能会更加不理解。

对于程序或算法而言,递归要比迭代更容易理解。而且,写$A(n,n)$而不写$n!$则更像是程序员调用方法一样,所以我觉得这是我作为程序员的一种理解方式,于是就有了现在的标题。

实际上,我最终理解了排列组合得益于,我首先明确全排列是$n!$,然后剩下的全都用全排列去解释。这正是人类的认知方式,用已知通用的去理解创造未知个别的。