离散数学基础:排列与组合

思维导图¶

$排列组合计数问题$

P (n, r) = P_{n}^{r} = A_{n}^{r}

P (n, r) = \frac{n!}{(n - r)!}

P (n, n) = n!

P (n, r) = {\begin{aligned} \frac{n!}{(n - r)!} & , & 0 \leq r < n \\ n! & , & r = n \\ 0 & , & r > n \end{aligned}

C (n, r) = C_{n}^{r} = (\begin{matrix} n \\ r \end{matrix})

C (n, r) = C (r, n) = \frac{P (n, r)}{P (r, r)} = {\begin{aligned} \frac{n!}{r! (n - r)!} & , & 0 \leq r \leq n \\ 0 & , & r > n \end{aligned}

（不严谨）

（严谨）

(x + y)^{n} = \sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) x^{k} y^{n - k}

\sum_{k = 0}^{n} (\begin{matrix} n \\ k \end{matrix}) = 2^{n}

(\begin{matrix} n \\ k \end{matrix}) = (\begin{matrix} n - 1 \\ k \end{matrix}) + (\begin{matrix} n - 1 \\ k - 1 \end{matrix})

r (\begin{matrix} n \\ r \end{matrix}) = (n - r + 1) (\begin{matrix} n \\ r - 1 \end{matrix}) ， 1 \leq r < n

r (\begin{matrix} n \\ r \end{matrix}) = n (\begin{matrix} n - 1 \\ r - 1 \end{matrix}) ， 1 \leq r < n

(\begin{matrix} n \\ m \end{matrix}) (\begin{matrix} m \\ k \end{matrix}) = (\begin{matrix} n \\ k \end{matrix}) (\begin{matrix} n - k \\ m - k \end{matrix}) ， k \leq m \leq n

朱世杰恒等式

\begin{aligned} (\begin{array}{c} m + r + 1 \\ r \end{array}) \\ = & \sum_{k = 0}^{r} (\begin{array}{c} m + k \\ m \end{array}) = (\begin{array}{c} m \\ m \end{array}) + (\begin{array}{c} m + 1 \\ m \end{array}) + . . . + (\begin{array}{c} m + r \\ m \end{array}) \\ = & \sum_{k = 0}^{r} (\begin{array}{c} m + k \\ k \end{array}) = (\begin{array}{c} m \\ 0 \end{array}) + (\begin{array}{c} m + 1 \\ 1 \end{array}) + . . . + (\begin{array}{c} m + r \\ r \end{array}) \end{aligned}

\sum_{k = 0}^{n} (\begin{matrix} k \\ m \end{matrix}) = (\begin{matrix} 0 \\ m \end{matrix}) + (\begin{matrix} 1 \\ m \end{matrix}) + . . . + (\begin{matrix} n \\ m \end{matrix}) = (\begin{matrix} n + 1 \\ m + 1 \end{matrix})

\begin{aligned} \sum_{k = 0}^{r} (\begin{array}{c} m \\ r - k \end{array}) (\begin{array}{c} n \\ k \end{array}) = (\begin{array}{c} m + n \\ r \end{array}) \\ = (\begin{array}{c} m \\ r \end{array}) (\begin{array}{c} n \\ 0 \end{array}) + (\begin{array}{c} m \\ r - 1 \end{array}) (\begin{array}{c} n \\ 1 \end{array}) + . . . + (\begin{array}{c} m \\ 1 \end{array}) (\begin{array}{c} n \\ r - 1 \end{array}) + (\begin{array}{c} m \\ 0 \end{array}) (\begin{array}{c} n \\ r \end{array}) \end{aligned}