常用排列组合公式

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 = \binom{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$ 的约定,算出 $\binom{n}{0} = 1$,这可看作一个约定。

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

$$ \binom{-1}{r} = (-1)(-2) \cdots (-r) / r! = (-1)^r $$

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

组合系数 $\binom{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)^n\dbinom{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$ 件,则取法有 $\binom{m}{i} \binom{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}$ 这一项的系数。

你可能感兴趣的