关于组合恒等式$inom{2n}{3} = 2 inom{n}{3} + 2n inom{n}{2}$的组合证明问询

嗨，我来帮你理清这个组合证明的思路——组合证明的核心就是给等式两边的表达式赋予完全一致的计数场景，让两边只是对同一件事的不同分类计数方式而已。

你已经搞懂左边了：$\binom{2n}{3}$就是从包含$2n$个元素的集合里选出3个元素的所有可能方法数。那我们只需要给右边的每一项找到对应的分类场景就行，步骤如下：

首先，把这$2n$个元素拆分成两个完全不相交的$n$元子集，比如叫集合A和集合B（你可以直观想象成n个红球和n个蓝球）。现在，从$2n$个元素里选3个的所有选法，我们可以分成两大类：

• 第一类：3个元素都来自同一个子集

  • 全从集合A里选3个：有$\binom{n}{3}$种选法
  • 全从集合B里选3个：也有$\binom{n}{3}$种选法
    这两类加起来就是$2\binom{n}{3}$，正好对应等式右边的第一项。

• 第二类：3个元素来自两个不同的子集
  这种情况又能拆成两种小情况：

  • 选1个来自集合A，2个来自集合B：选A里的1个元素有$n$种方式，选B里的2个元素有$\binom{n}{2}$种方式，总共有$n\binom{n}{2}$种选法
  • 选1个来自集合B，2个来自集合A：同理，也是$n\binom{n}{2}$种选法
    这两部分加起来就是$n\binom{n}{2} + n\binom{n}{2} = 2n\binom{n}{2}$，对应等式右边的第二项。

现在，所有可能的选法就是这两大类的总和，也就是$2\binom{n}{3} + 2n\binom{n}{2}$，而它和左边$\binom{2n}{3}$计数的是同一件事，所以等式必然成立。这样就完成了组合证明啦！

备注：内容来源于stack exchange，提问作者Ben Cohen