常用排列组合公式

1. 排列公式

(n) 个相异物件取 (r)（(1 leq r leq n)）个的不同排列总数，为

[P_r^n = n(n-1)(n-2)cdots(n-r+1) ]

特别地，若 (n=r)，得

[P_r^r = r(r-1)cdots 1 = r! ]

人们常约定把 (0!) 作为 (1)。当 (r) 不是非负整数时，记号 (r!) 没有意义。

2. 组合公式

(n) 个相异物件取 (r) 个（(1 leq r leq n)）个的不同组合总数，为

[C_r^n = inom{n}{r} = frac{P_r^n}{r!} = frac{n!}{r!(n-r)!} = frac{n(n-1) cdots (n-r+1)}{r!} ]

当 (r=0) 时，按 (0!=1) 的约定，算出 (inom{n}{0} = 1)，这可看作一个约定。

只要 (r) 为非负整数，(n) 不论为任何实数，都有意义。故 (n) 可不必限制为自然数。例如：

[inom{-1}{r} = (-1)(-2) cdots (-r) / r! = (-1)^r ]

3. 组合系数与二项式展开的关系

组合系数 (inom{n}{m}) 又常称为二项式系数，因为它出现在下面熟知的二项式展开的公式中：

[(a+b)^n = sum_{i=0}^n dbinom{n}{i}a^i b^{n-i} ]

利用这个关系式，可得出许多有用的组合公式。例如，令 (a=b=1)，得

[dbinom{n}{0} + dbinom{n}{1} + cdots + dbinom{n}{n} = 2^n ]

令 (a = -1，b = 1)，则得：

[dbinom{n}{0} - dbinom{n}{1} + dbinom{n}{2} - cdots + (-1)^ndbinom{n}{n} = 0 ]

另一个有用的公式是

[dbinom{m+n}{k} = sum_{i=0}^{k}dbinom{m}{i}dbinom{n}{k-i} ]

它是由恒等式 ((1+x)^{m+n} = (1+x)^m(1+x)^n) 即

[sum_{j=0}^{m+n} dbinom{m+n}{j} x^j = sum_{j=0}^{m} dbinom{m}{j} x^j sum_{j=0}^{n} dbinom{n}{j}x^j ]

比较两边的 (x^k) 项的系数得到的。

其实，这条公式从直观上理解要更容易，即有两堆物品，第一堆有 (m) 件，第二堆有 (n) 件，要从这两堆物品中取出 (k) 件，有多少种取法？显然，我们可以先在第一堆取 (i) 件（(0 leq i leq k)），然后在第二堆取 (k - i) 件，则取法有 (inom{m}{i} inom{n}{k-i}) 种，把 (i) 的所有取值结果相加，即得上面的公式。

4. 物品分堆

(n) 个相异物件分成 (k) 堆，各堆物件数分别为 (r_1, cdots, r_k) 的分法是

[frac{n!}{r_1! cdots r_k!} ]

此处，(r_1, cdots, r_k) 都是非负整数，其和为 (n)。注意：这里要计较堆的次序，例如，若有 5 个物体 (a，b，c，d，e) 分成 (3) 堆，则 ((ac)，(d)，(be)) 和 ((be)，(ac)，(d)) 应算作两种不同的分法。如果不考虑次序，还需要再除以 (k!)。

此式常称为多项式系数，因为它是 ((x_1+cdots+x_k)^n) 的展开式中 (x_1^{r_1} cdots x_k^{r_k}) 这一项的系数。