05 Counting - Blade's Blog

237 字

1 分鐘

05 Counting

2025-04-14

discrete-math

Permutations#

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

C(n, r) = \begin{pmatrix} n \\ r \end{pmatrix} = \frac{P(n, r)}{r!} = \frac{n!}{r!(n - r)!}

重要性質

\begin{pmatrix} n \\ r \end{pmatrix} = \begin{pmatrix} n \\ n-r \end{pmatrix}

How many bit strings of length $n$ containing an even number of 1s are there?

每在前面加一位，就剛好增值奇數一倍、偶數一倍。所以加一位永遠還是偶數。

Binomial Theorem

\begin{pmatrix} n \\ k \end{pmatrix} = \begin{pmatrix} n - 1 \\ k - 1 \end{pmatrix} + \begin{pmatrix} n - 1 \\ k \end{pmatrix}

解讀：取 $k$ 個東西，可以二分為「第一個取」跟「第一個不取」兩種情況。第一個情況中，你還需要取 $k-1$ 個東西；第二個情況則還需要取 $k$ 個。

05 Counting

作者

Blade/磯江

發佈於

2025-04-14

許可協議