练习：排列组合分析

本文是Sheldon M. Ross的 概率论基础教程的第一章组合分析中个人感觉比较有意思的习题的总结。

Sheldon M. Ross的教材习题都超多，做多了有点刷数据的感觉。不过，对于强化理解书中知识点大有裨益。在刷题的过程中，把个人感觉有意义的习题拿出来总结一下。在刷题的过程中，发现对于组合恒等式，如果能找到对应的模型，则问题就会简单的多。从分析的方向证明分析恒等式总显得有些暴力和笨拙。倘若，有一个精巧的模型可以使用，一切都会简单得多。比如本文的第一题和第一章习题中的理论习题1.10。

证明：

(n+mr)=(n0)(mr)+(n1)(mr−1)+…+(nr)(m0)
(2nn)=n∑k=0(nk)2

第一个等式可以考虑为从n个男人和m个女人中选出r个人组成一个委员会。这样可以分两步走：先从n个男人中选取k个，再从m个女人中选取r−k个。其中k的取值范围是0到r的整数。

第二个等式是第一个等式的特例m=n,r=n，再利用(nk)=(nn−k)，得证。

证明费马组合恒等式：

(nk)=n∑i=k(i−1k−1)n≥k

等式左边表示从n个元素中选出k个的组合个数。我们可以考虑1,…,n的n个数，从中选出k个，这k个元素的最大值至少是k。所以(nk)也可以表示{1,…,n}这个集合中k个元素的子集个数。这些子集天然的满足最大元素至少是k。

右边就是(x1,…,xk)的个数，其中xi是正整数，且满足1≤xi≤n，且x1<x2<…<xk。所以右边是：

(k−1k−1)+(kk−1)+…+(n−1k−1)

考虑恒等式：

n∑k=1k(nk)=n2n−1

从组合的角度解释上式

  1. 从n个人中选择k个人，在从k个人中选择一个做主席，就是k(nk)
  2. 当k从1到n变化时就是等式左边。
  3. 考虑等式右边，把n个人排成一排，从中选出一个做主席一共有n个。在从剩余的n−1个人中选出k−1个构成委员会成员。一共(n−1k−1)，当k从1到n变化时就是等式左边。因为(n−10)+…+(n−1n−1)=2n−1

考虑恒等式：

n∑k=1k2(nk)=n(n+1)2n−2

从组合角度解释上式。

  1. 从n个人中选择k个人，在从k个人中选择一个做主席一个做秘书（秘书和主席可以是同一个人），就是k2(nk)
  2. 当k从1到n变化时就是等式左边。
  3. 考虑等式右边，把n个人排成一排：当主席和秘书是同一个人时，从中选出一共有n个。在从剩余的n−1个人中选出k−1个构成委员会成员。一共(n−1k−1)，当k从1到n变化时就是等式左边。因为(n−10)+…+(n−1n−1)=2n−1； 当主席和秘书是两个人时一共有n(n−1)2n−2种取法。综合考虑这两种情况。得证。
  4. 照这个方法归纳下去还可以证明n∑k=1k3(nk)=2n−11n2(n+3)
    不过，我不想算下去了。