Course-Note

Problem 1 证明 $$ \begin{align*} \sum_{i=0}^{n} (-1)^{i}\binom{ n }{ i } \binom{ n+m-i }{ k-i } = \binom{ m }{ k } \\ \sum_{i=0}^{n} \binom{ k }{ i } D_{n-i} = \sum_{j=0}^{n-k} (-1)^{j}\binom{ n-k }{ j } (n-j)! \end{align*} $$ 证 1 对于第一个式子，我们考虑组合意义。设有 $ A,B $ 两个集合，分别包含 $ n $ 和 $ m $ 个元素，总共 $ n+m $ 个元素。我们希望从集合 $ B $ 中恰好选择 $ k $ 个元素。我们可以通过容斥原理的补集形式求解，定义事件 $ A_{i} $ 为所选的 $ k $ 个元素中至少包含 $ i $ 个来自 $ A $ 的元素，那么我们需要求解的事件集合为 $ U\setminus\bigcup_{i\leq n}A_{i} $，并且 $$ \left| A_{i} \right| = \binom{ n }{ i } \binom{ n+m-i }{ k-i } $$ 因此根据容斥原理，就可以得到 $$ \left| U\setminus \bigcup_{i\leq n}A_{i} \right| = \sum_{i=0}^{n} (-1)^{i}\binom{ n }{ i } \binom{ n+m-i }{ k-i } = \binom{ m }{ k } $$ ...

题目 Problem 1.1 设 $ \mathcal{F} $ 是一个有限的 $ \sigma $-代数。定义其中“最小"的元素为其包含于 $ \mathcal{F} $ 中的子集仅为自身和空集，形式化地描述，若 $ A\in \mathcal{F} $ 为“最小”的元素，那么如果 $ B\in \mathcal{F} $ 并且 $ B\subseteq A $，那么一定有 $ B\in \{ \emptyset,A \} $。 可以证明这样的元素存在并且有限：如果不存在，那么我们每次任取一个 $ \mathcal{F} $ 中的元素，都能找到属于它的一个更小的元素，但 $ \mathcal{F} $ 是有限集，所以这样的过程不可能一直重复下去，因此“最小”元素必然存在并且有限。 我们设所有这些不同的“最小”元素为 $ S=\{ A_{1},A_{2},\dots,A_{n} \} $。我们先证明这构成了全空间的一个分划： 首先这些元素肯定两两不相交，否则不满足“最小”的定义。假设 $ A_{i}\cap A_{j}= C\neq\emptyset $，根据“最小”，非空的 $ C $ 是 $ A_{i} $ 的子集，一定有 $ C=A_{i} $，同样也有 $ C=A_{j} $，这就推出了 $ A_{i}=A_{j} $，从而矛盾。 ...

Exercise 1 (Multiplication of block matrices). Consider two block matrices $$ A = \begin{pmatrix} A_{11} & \cdots & A_{1t} \\ \vdots & \ddots & \vdots \\ A_{p1} & \cdots & A_{pt} \end{pmatrix} \quad \text{and} \quad B = \begin{pmatrix} B_{11} & \cdots & B_{1q} \\ \vdots & \ddots & \vdots \\ B_{t1} & \cdots & B_{tq} \end{pmatrix} $$ Moreover, for every $ i \in [p] $, $ j \in [t] $, and $ l \in [q] $ the number of columns of $ A_{ij} $ is equal to the number of rows of $ B_{jl} $. In particular, $ A_{ij} \cdot B_{jl} $ is defined. Prove that $$ A \cdot B = \begin{pmatrix} C_{11} & \cdots & C_{1q} \\ \vdots & \ddots & \vdots \\ C_{p1} & \cdots & C_{pq} \end{pmatrix} $$ with $$ C_{il} = \sum_{j \in [t]} A_{ij} B_{jl} $$ for any $ i \in [p] $ and $ l \in [q] $. ...

Exercise 1 What rows or columns or matrices do you multiply to find the second column of $ AB $ ? the first row of $ AB $ ? the entry in row $ 3 $, column $ 5 $ of $ AB $ ? the entry in row $ 1 $, column $ 1 $ of $ CDE $ ? To find the second column of $ AB $, we multiply matrix $ A $ by the second column of matrix $ B $. ...

Principle of Inclusion and Exclusion 对于任意有限集合 $ A_1, A_2, \dots, A_n $，容斥原理如下： $$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{i=1}^{n} \left| A_i \right| - \sum_{1\leq i< j\leq n} \left| A_i \cap A_j \right| + \dots + (-1)^{n} \left| \bigcap_{i=1}^{n} A_i \right| $$ 可更紧凑地表示为 $$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{k=1}^{n} (-1)^{k-1} \sum_{S \subseteq [n], |S|=k} \left| \bigcap_{i \in S} A_i \right| $$ 或 $$ \left| \bigcup_{i=1}^{n} A_i \right| = \sum_{\emptyset \neq S \subseteq [n]} (-1)^{|S|-1} \left| \bigcap_{i \in S} A_i \right| $$ ...

Problem 1 用生成函数求解递推式 $$ a_{n} = 4a_{n-1} - 5a_{n-2} + 2a_{n-3} $$ 初始值为 $ a_{0}=0,a_{1}=3,a_{2}=7 $。 解： 设数列 $ \{ a_{n} \} $ 的生成函数为 $ F(x) $，那么根据递推式和初值 $ a_{0}=0,a_{1}=3,a_{2}=7 $ 得到 $$ F(x) = 4xF(x) - 5x^{2}F(x) + 2x^{3}F(x) + 3x - 5x^{2} $$ 得到 $$ F(x) = \dfrac{5x^{2}-3x}{2x^{3}-5x^{2}+4x-1} = \dfrac{3x-5x^{2}}{(1-x)^{2}(1-2x)} $$ 我们希望分解成 $$ \dfrac{A}{1-x} + \dfrac{B}{(1-x)^{2}} + \dfrac{C}{1-2x} $$ 待定系数可以解得 $$ F(x) = \dfrac{-3}{1-x} + \dfrac{2}{(1-x)^{2}} + \dfrac{1}{1-2x} $$ 展开得到 $$ F(x) = \sum_{n=0}^{\infty} (-3+2(n+1)+2^{n})x^{n} $$ 因此 $$ a_{n} = -3+2(n+1)+2^{n} = 2^{n} + 2n - 1 $$ ...

Exercise 1 Let $ f:\mathbb{R}\to\mathbb{R} $ be a function. Prove that the following are equivalent: (i) There is a constant $ a\in\mathbb{R} $ such that for every$ x\in\mathbb{R} $ we have$ f(x)=ax $. (ii) For all $ x_1,x_2,c,x\in\mathbb{R} $ we have $ f(x_1+x_2)=f(x_1)+f(x_2) $ and $ f(cx)=c\,f(x) $. (i ⇒ ii) Assume there exists $ a\in\mathbb{R} $ such that $ f(x)=a x $ for all $ x\in\mathbb{R} $ . Then for any $ x_1,x_2,c,x\in\mathbb{R} $ , ...

考虑上一节引入的二项式定理 $$ (1+x)^{n} = \sum_{k=0}^{n} \binom{ n }{ k } x^{k} $$ 这可以理解成我们把二项系数转换成了一个函数，这使得我们能更有效地操作和分析序列，这个工具被成为生成函数。 Ordinary Generating Functions 给定序列 $ \{ a_{n} \}_{n\geq 0} $，由 $ \{ a_{n} \} $ 定义的普通生成函数 (OGF) 为： $$ G(x) = \sum_{n\geq 0} a_{n}x^{n} $$ 虽然看起来 OGF 并没有被很好的定义，对于和某些数列，这个形式不会收敛，但是实际上生成函数并不能被看成一个真正的函数，它是一个形式幂级数，并且不被要求收敛。 以下是一些生成函数的基础例子： $$ G(x) = 1+x+x^{2}+x^{3} +\dots = \dfrac{1}{1-x} $$ $$ G(x) = 1+ax+a^{2}x^{2} + a^{3}x^{3} + \dots = \dfrac{1}{1-ax} $$ 给定一个序列，写出他的生成函数是很容易的。尽管找到他的闭合形式不容易，但是我们一般不需要这样做。相反，我们需要考虑给定一个闭合形式，需要如何知道其对应的序列。 我们约定 $ [x^{n}]G(x) $ 表示生成函数中 $ x^{n} $ 的系数。 ...

Introduction 条件概率指一个事件在另一个事件发生的条件下发生的概率，用记号 $ \mathbb{P}(A|B) $ 表示，仅在 $ \mathbb{P}(B)>0 $ 时有定义： $$ \mathbb{P}(A|B) = \dfrac{\mathbb{P}(A \cap B)}{P(B)} $$ 可以写成 $$ \mathbb{P}(A \cap B) = \mathbb{P}(B)\cdot \mathbb{P}(A|B) $$ 对于 $ n $ 个事件，连续使用上式，即可得到 $$ \mathbb{P}\left( \bigcap_{i=1}^{n}A_{i} \right) = \prod_{k=1}^{n} \mathbb{P}\left( A_{k}\bigg|\bigcap_{i=1}^{k-1}A_{i} \right) $$ 这个式子被称为 链式法则。 Independence 对于事件 $ A,B $，如果 $ \mathbb{P}(A\cap B)=\mathbb{P}(A)\mathbb{P}(B) $，或者等价地 $ \mathbb{P}(A|B)=\mathbb{P}(A) $，那么我们称 $ A $ 和 $ B $ 是独立的。这表明 $ A $ 或 $ B $ 自己是否发生对对方是否发生没有影响。 ...

Motivation 例题：在圆上“随机”选一段弧，问弧长大于圆周的 $ \frac{1}{3} $ 的概率？（Bertrand paradox） 至少三种自然的“均匀化”模型会给出不同答案： 对弧长参数均匀（在 $ [0, 2\pi) $ 上均匀取长度，再随机起点）。 对端点在圆上独立均匀（等价于随机两点确定弧，需指定取较短或较长弧）。 对中心角或几何构造的中间量均匀（如均匀选角度后裁剪）。 核心问题：如何定义“随机”？不同“随机化”方案导致不同答案。 讨论概率问题必须先明确概率空间（样本空间、事件族与概率测度），否则“概率”无从谈起。 Probability Space 一个概率空间由三元组 $ (\Omega, \mathcal{F}, \mathbb{P}) $ 构成： $ \Omega $：样本空间（一次随机试验所有可能结果）。 $ \mathcal{F} \subseteq 2^{\Omega} $：事件族（允许讨论与运算的集合）。 $ \mathbb{P} : \mathcal{F} \to [0,1] $：概率测度（赋予事件概率）。 记号说明： $ \Omega $：样本空间。 $ 2^{\Omega} $：$ \Omega $ 的幂集（所有子集的集合）。 为什么 $ \mathbb{P} $ 要定义在 $ \mathcal{F} $ 上而非直接在 $ \Omega $ 上？ 离散可数时，取 $ \mathcal{F} = 2^{\Omega} $ 可行，且对单点赋值即可确定所有事件的概率。 连续时不同：单点的概率通常为 $ 0 $，但不可数并可有正概率；且 $ 2^{\Omega} $ 中存在不可测集合，无法一致赋值（见下文 Vitali set 与 Axiom of Choice）。因此需选择一个足够大又可控的 $ \sigma $- 代数作为事件族。 Sigma-Algebra 要求 $ \mathcal{F} $ 构成一个 $ \sigma $- 代数（域）： ...