计数原理笔记

前言

最近开坑来学计数原理。随缘更新~

在定义上可能中文的表达具有二义性 , 会附上英文版本的表达 , 有些是摘自 $\texttt{MIT 6.042J}$ , 有些是自己瞎翻的。

历史版本修改后 , 如果历史版本有一定的特有的优越性 , 会以括号内附版本号的形式给出。

当前版本 : $\texttt{Version 0.0.2}$

如果是在LG Blog上看到这篇文章 , 由于LG Blog对latex行间公式的支持不是很好 , 无法使用一些基本的环境 , 所以多行公式只能压成一行 , 目前只能凑合了。

前置知识

集合相关

$\texttt{[Def]}$ 集合、集合的基数、序列、排列

$\texttt{[Def]}$ 集合(set) : 集合是无序不重元素的聚集。(A set is a collection of unordered distinct elements. )

$\texttt{[Def]}$ 基数(Cardinality) : 一个集合的基数是集合包含的元素数。 (Cardinality ::= # of elements in the set. )

$\texttt{[Def]}$ 序列(Sequence) : 序列是有序元素的可重聚集。 (A sequence is an ordered collection of ordered elements(items/components), not necessarily distinct. )

$\texttt{[Def]}$ 排列(permutation) : 一个集合 $S$ 的排列是一个包含 $S$ 中所有元素仅各一个的序列。 (A permutation of a set $S$ is a sequence which containing every elements in $S$ actually once. )

笛卡尔积

若干个集合 $A_1, A_2, ..., A_n$ 的笛卡尔积记为 $A_1 \times A_2 \times ... \times A_n$

A_1 \times A_2 \times ... \times A_n ::= \{(a_1, a_2, ..., a_n) | a_1 \in A_1, a_2 \in A_2, ..., a_n \in A_n \}

基本计数法则

基本计数原则

$\texttt{[theorem]}$ 双射规则

若能建立集合 $A$ 到集合 $B$ 的一个双射 , 则 $\left| A \right| = \left| B \right|$ 。

常见用途 : 将计数对象表示为集合 , 通过双射规则将问题转化为求较简单的计数。

$\texttt{[theorem]}$ 广义乘积法则

有穷集 $A_1, A_2, ..., A_m$ 的笛卡尔积的 $\texttt{size}$ 为各集合 $\texttt{size}$ 之积。

\left| A_1 \times A_2 \times \cdots \times A_m \right| = \left| A_1 \right| \cdot \left| A_2 \right| \cdots \left| A_m \right|

该法则的另一种经典的表述为 : 对于一个序列 $<a_1, a_2, \cdots, a_n>$ , $a_1$ 有 $s_1$ 种选择 , $a_2$ 有 $s_2$ 种选择 , $\cdots$ , $a_n$ 有 $s_n$ 种选择 , 则生成的序列一共有 $s_1 \cdot s_2 \cdots s_n$ 种。

$\texttt{[theorem]}$ 加和法则

不相交集合 $A_1, ..., A_n$ 的并的 $\texttt{size}$ 为各集合 $\texttt{size}$ 之和。

\left| A_1 \cup A_2 \cup \cdots \cup A_n \right| = \left| A_1 \right| + \left| A_2 \right| + \cdots + \left| A_n \right|\\ (\forall i,j \in n, i \neq j : A_i \neq A_j)

$\texttt{[practice]}$ 加和法则与乘积法则的结合

许多复杂问题都可以通过加和法则与乘积法则结合完成。来看一个例子。

$\texttt{EX1}$ $6$ ~ $8$ 位密码 , 首位为字母 , 其余位为字母或数字, 求共有可能密码的种数。

$F ::= \{a, b, \cdots, z, A, B, \cdots, Z\}$

$S ::= \{a, b, \cdots, z, A, B, \cdots, Z, 0, 1, \cdots, 9\}$

( $F$ 和 $S$ 是完全根据题中规定的合法值的定义的已知集合。)

记可能的密码集合为 $A$ , $A = (F \times S^5) \cup (F \times S^6) \cup (F \times S^7)$

( 通过分析 , 运用已知集合的封闭形式表示出待求集合 : 利用并表示"或" , 利用笛卡尔积表示并列的选择。 )

\begin{align} \left| A \right| &= \left| (F \times S^5) \cup (F \times S^6) \cup (F \times S^7) \right|\\ &= \left| F \times S^5 \right| + \left| F \times S^6 \right| + \left| F \times S^7 \right|\\ &= \left| F \right| \times \left| S \right|^5 + \left| F \right| \times \left| S \right| ^ 6 + \left| F \right| \times \left| S \right| ^ 7\\ &= 52 \times 62^5 + 52 \times 62^6 + 52 \times 62^7\\ &= 186125210680448\\ \end{align}\\

( 运用计数法则拆分成已知集合的基数表示的封闭形式并代入数值求解。 )

$\texttt{Tips}$ 在表示或的关系中考虑 $\cup$ 运算 , 在表示选择的并列考虑笛卡尔积运算。

计数问题的本质

计数的本质

将所有计数的对象看作元素 , 计数就是求集合的基数的过程。

一般化套路

明确计数的对象构成的集合。
通过双射规则将原计数转化成其他等价计数 ,
通过计数法则将集合运算构建的复杂计数(即原问题或其通过双射规则转化到的等价问题所求的对象的集合的基数)化为由若干简单计数(即简单集合的基数)表示的封闭形式。
求出简单计数的基数的表达式。
代入表示简单计数的基数的表达式求值。

（ $\texttt{Version0.0.1: }$ 将待计数的所有情况视为一个集合的元素 , 用已知或易求的计数的集合通过集合运算、双射规则等方式表示待求计数的集合 , 然后通过计数法则用已知集合的表示当前计数的集合的 , 代入变量或数据求出当前计数的值。)

Reference

《计算机科学中的数学》
《离散数学及其应用》
《具体数学》
$\texttt{MIT 6.042J}$

寒鸽儿のBlog

前言