「BUAA Discrete Mathematics Chapter5」二项式系数

Part 0

Part 1

Pascal公式

$$\tbinom{n}{k} = \tbinom{n-1}{k}+\tbinom{n-1}{k-1}$$

组合推理证明

• 一种依靠计数原理构建代数事实的证明方法
• 基本框架：
  1. 定义一个集合$ S $
  2. 通过一种计数方式得出$ |S|=n $
  3. 通过另一种计数方式得出$ |S| = m $
  4. 得出结论$ n=m $

二项式定理

$$(x+y)^n = \sum_{k=0}^{n}\tbinom{n}{k}x^{n-k}y^k$$

求导法和积分法

对于一些不等式证明和计算，需要使用这两种方法，以下举例说明

求导法

来源：《组合数学》P96 T15

题目：求证对${\forall}n>1$有$\tbinom{n}{1}-2\tbinom{n}{2}+3\tbinom{n}{3}+···+(-1)^{n-1}n\tbinom{n}{n}=0$

解答：

根据

$$(1-x)^n=\sum_{k=0}^{n}\tbinom{n}{k}(-1)^{k}x^k$$

求导得

$$-n(1-x)^{n-1}=\sum_{k=0}^{n}\tbinom{n}{k}(-1)^kkx^{k-1}$$

令$x=1$即证毕。

积分法

来源：《组合数学》P96 T18

题目：求和$1-\frac{1}{2}\tbinom{n}{1}+\frac{1}{3}\tbinom{n}{2}-\frac{1}{4}\tbinom{n}{3}+···+(-1)^n\frac{1}{n+1}\tbinom{n}{n}$

解答：

根据

$$(1-x)^n = \sum_{k=0}^{n} \tbinom{n}{k}(-1)^{k}x^k$$

左右不定积分得

$$-\frac{(1-x)^{n+1}} {n+1} = \sum_{k=0}^{n}\tbinom{n}{k}(-1)^k\frac{x^{k+1}}{k+1}+C$$

注意有$+C$。代入$x=0$得$C=-\frac{1}{n+1}$，代入$x=1$得所求式值为$-\frac{1}{n+1}$

二项式系数的单峰性

为了介绍二项式系数的单峰性，我们首先介绍单峰性概念

单峰性

设序列$ s_0, s_1, s_2, \cdots , s_n $，若存在一个整数$ t $，$ 0 \le t \le n $，使得：

$$s_0 \le s_1 \le s_2 \cdots \le s_t , s_t \ge s_{t+1} \ge s_{t+2} \ge \cdots \ge s_n$$

那么， 称序列是单峰的

二项式系数的单峰性

$ n $为正整数，二项式系数序列是单峰序列，其中：

• $ n $是偶数：

$$\tbinom{n}{0} < \tbinom{n}{1} < \cdots < \tbinom{n}{\frac{n}{2}} , \tbinom{n}{\frac{n}{2}} > \cdots > \tbinom{n}{n - 1} > \tbinom{n}{ n }$$

• $ n $是奇数：

$$\tbinom{n}{0} < \tbinom{n}{1} < \cdots < \tbinom{n}{\frac{n-1}{2}} , \tbinom{n}{\frac{n+1}{2}} > \cdots > \tbinom{n}{n - 1} > \tbinom{n}{ n }$$

多项式定理

二项式定理给出对正整数$n$ ， $ (x + y ) ^ n $的公式，扩展到 $ (x_1 + x_2 + \cdots +x_t) ^ n $ 的公式，二项式系数的角色被多项式系数取代，其定义为：

$$\tbinom{n}{n_1 \ n_2 \ \cdots \ n_t} = \frac{n!}{n_1!n_2! \cdots n_t!}$$

其中$ n_1, n_2, \cdots n_t $满足：

$$n_1 + n_2 + \cdots + n_t = n$$

根据这种记法，可以将二项式系数表示为：

$$\tbinom{n}{k} = \tbinom{n}{k \quad n-k}$$

帕斯卡公式

二项式

$$\tbinom{n}{k \quad n-k} = \tbinom{n-1}{k \quad n - k - 1} + \tbinom{n-1}{k-1 \quad n - k}$$

多项式

$$\tbinom{n}{n_1 \ n_2 \ \cdots \ n_t} = \tbinom{n - 1}{n_1-1 \ n_2 \ \cdots \ n_t} + \tbinom{n - 1}{n_1 \ n_2 - 1 \ \cdots \ n_t} + \cdots + \tbinom{n - 1}{n_1 \ n_2 \ \cdots \ n_t - 1}$$

规律为：上面$ - 1 $，下面依次各$ - 1 $，应用加法原理。

多项式定理

$$(x_1 + x_2 + \cdots + x_t) ^ n = \sum\tbinom{n}{n_1 \ n_2 \cdots n_t}{x_1}^{n_1}{x_2}^{n_2}\cdots{x_t}^{n_t}$$

其中，求和是对 $ n_1 + n_2 + \cdots + n_t = n $ 的所有非负整数解进行的。

牛顿二项式定理

牛顿扩展了二项式定理，得到 $ (x + y) ^ \alpha$ 的展开式， $ \alpha $ 是任意实数。

设 $ \alpha $是实数，对所有满足 $ 0 \le |x| < |y| $ 的 $ x $ 和 $ y $ ，有：

$$(x + y) ^ {\alpha} = \sum_{k = 0}^{\infty}\tbinom{\alpha}{k}x^ky^{\alpha - k}$$

其中

$$\tbinom{\alpha}{k} = \frac{\alpha(\alpha - 1) \cdots (\alpha - k - 1)}{k!}$$

Sperner定理

有一个$ n $元集合$ S_n $，从中选出若干个子集，满足没有任何两个子集之间存在包含关系，最多能选出$ \tbinom{n}{\lfloor \frac{n}{2} \rfloor}$个。

事实上，上述引出了反链的定义，以下逐个介绍链、最大链、反链。

链

$ S $的子集的集合$ C $是一条链(chain)，只要对于$ C $中的每一对子集，总有一个包含在另一个之中：$ A_1 $，$ A_2 $在$ C $中，且$ A_1 \ne A_2 $意味着$ A_1 \subset A_2 $或者$ A_2 \subset A_1 $。

最大链

链中不能挤入更多子集。

反链

$ S $的子集的集合$ C $是反链，当且仅当$ C $中的子集不互相包含。

通过以上定义，可以得到Sperner定理的等价表述：设$ S $是$ n $元素集合，那么$ S $上的一个反链至多包含$ \tbinom{n}{\lfloor \frac{n}{2} \rfloor}$个集合。

对称链划分

当下面两个条件满足时，$ {1, 2, \cdots , n} $ 的所有子集的集合的链划分是一个对称链划分：

1. 链中每一个子集比它前面的子集的元素个数多$ 1 $ ；
2. 链中第一个子集的大小加上最后一个子集的大小等于$ n $ 。（如果这个链只含一个子集，那么这个子集既是第一个子集也是最后一个子集，所以其大小的两倍等于$ n $ ；即它的大小是 $ \frac{n}{2} $ ， $ n $ 是偶数。）

对称链划分中的每一个链必须正好含有一个 $ \lfloor \frac{n}{2} \rfloor$ 子集（也正好含有一个$ \lceil \frac{n}{2} \rceil$ 子集）；因此，对称链划分中的链的个数等于

$$\tbinom{n}{\lfloor \frac{n}{2} \rfloor} = \tbinom{n}{\lceil \frac{n}{2} \rceil}$$

---

• ← Previous Post
• Next Post →

---