Skip to content
Notes

第五章 二项式系数

5.1 帕斯卡三角形

帕斯卡恒等式

(nk)=(n−1k)+(n−1k−1)\displaystyle{ { n \choose k } = { n - 1 \choose k } + { n - 1 \choose k - 1 } } (n0)+(n1)+…+(nn)=2n\displaystyle{ { n \choose 0 } + { n \choose 1 } + \ldots + { n \choose n } = 2 ^{ n } }

5.2 二项式定理

(x+y)n=(n0)xn+(n1)xn−1y+…(nn)yn=∑k=0n(nk)xn−kyk\displaystyle{ \begin{aligned}\left( x + y \right) ^{ n } & = { n \choose 0 } x ^{ n } + { n \choose 1 } x ^{ n } - 1 y + \ldots { n \choose n } y ^{ n } \\ & = \sum _{ k = 0 } ^{ n } { n \choose k } x ^{ n - k } y ^{ k }\end{aligned} }

证明

1(n1)+2(n2)+…+n(nn)=n2n−1\displaystyle{ 1 { n \choose 1 } + 2 { n \choose 2 } + \ldots + n { n \choose n } = n 2 ^{ n - 1 } }

由于

k(nk)=n(n−1k−1)\displaystyle{ k { n \choose k } = n { n - 1 \choose k - 1 } }

所以

1(n1)+…+n(nn)=n(n−10)+…n(n−1n−1)=n2n−1\displaystyle{ 1 { n \choose 1 } + \ldots + n { n \choose n } = n { n - 1 \choose 0 } + \ldots n { n - 1 \choose n - 1 } = n 2 ^{ n - 1 } }

范德蒙卷积公式

∑k=0n(nk)2=(2nn)\displaystyle{ \sum _{ k = 0 } ^{ n } { { n \choose k } } ^{ 2 } = { 2 n \choose n } }
  • 从 2n\displaystyle{ 2 n } 个物体中选出 n\displaystyle{ n } 个，有 (2nn)\displaystyle{ { 2 n \choose n } } 种选择的方法
  • 分为奇偶两个集合，从奇数集合中选 k\displaystyle{ k } 个，从偶数集合中选 n−k\displaystyle{ n - k } 个，两者独立，因此有 (nk)(nn−k)\displaystyle{ { n \choose k } { n \choose n - k } } 种方法，k\displaystyle{ k } 取 0∼n\displaystyle{ 0 \sim n }，因此等式两边相等

设 r\displaystyle{ r } 是实数，k\displaystyle{ k } 是整数，定义二项式系数 (rk)\displaystyle{ { r \choose k } } 为

(rk)={r(r−1)…(r−k+1)k!k⩾11k=00k⩽−1\displaystyle{ { r \choose k } = \left\lbrace \begin{array}{ll} \frac{ r \left( r - 1 \right) \ldots \left( r - k + 1 \right) }{ {k !} } & k \geqslant 1 \\ 1 & k = 0 \\ 0 & k \leqslant - 1 \end{array} \right. } (r0)+(r+11)+…(r+kk)=(r+k+1k)\displaystyle{ { r \choose 0 } + { r + 1 \choose 1 } + \ldots { r + k \choose k } = { r + k + 1 \choose k } }

5.3 二项式系数的单峰性

对于正整数 n\displaystyle{ n }，二项式系数 (ni)\displaystyle{ { n \choose i } } 中的最大者为 (n⌊n2⌋)=(n⌈n2⌉)\displaystyle{ { n \choose \left\lfloor\frac{ n }{ 2 }\right\rfloor } = { n \choose \left\lceil\frac{ n }{ 2 }\right\rceil } }

反链

n\displaystyle{ n } 元素集合 S\displaystyle{ S } 的一个反链是 S\displaystyle{ S } 的一个子集的一个集合 A\displaystyle{ \mathcal{ A } }，其中 A\displaystyle{ \mathcal{ A } } 中的子集不互相包含

  • S={a,b,c,d},A={{a,b},{b,c,d},{a,d},{a,c}}\displaystyle{ S = \left\lbrace a , b , c , d \right\rbrace , \mathcal{ A } = \left\lbrace \left\lbrace a , b \right\rbrace , \left\lbrace b , c , d \right\rbrace , \left\lbrace a , d \right\rbrace , \left\lbrace a , c \right\rbrace \right\rbrace } 是一个反链
  • S\displaystyle{ S } 的所有 k\displaystyle{ k } 子集的集合 Ak\displaystyle{ \mathcal{ A } _{ k } } 是 S\displaystyle{ S } 的一个反链
    • 用这种方法构造的反链最长为 (n⌊n2⌋)\displaystyle{ { n \choose \left\lfloor\frac{ n }{ 2 }\right\rfloor } }
  • 反链最多包含 (n⌊n2⌋)\displaystyle{ { n \choose \left\lfloor\frac{ n }{ 2 }\right\rfloor } } 个集合

链

S\displaystyle{ S } 的子集的集合 C\displaystyle{ C } 是一条链，只要对于 C\displaystyle{ C } 中的每一对子集，总有一个包含在另一个之中。A1,A2∈C,A1≠A2  ⟹  A1⊂A2 or A2⊂A1\displaystyle{ A _{ 1 } , A _{ 2 } \in C , A _{ 1 } \ne A _{ 2 } \implies A _{ 1 } \subset A _{ 2 } \text{ or } A _{ 2 } \subset A _{ 1 } }

  • S={1,2,3,4,5}\displaystyle{ S = \left\lbrace 1 , 2 , 3 , 4 , 5 \right\rbrace }
  • {∅,{2},{2,3},{1,2,3,5}}\displaystyle{ \left\lbrace \varnothing , \left\lbrace 2 \right\rbrace , \left\lbrace 2 , 3 \right\rbrace , \left\lbrace 1 , 2 , 3 , 5 \right\rbrace \right\rbrace } 是一个链

链和反链的交至多只有一个成员

最大链

包含 S\displaystyle{ S } 各种可能大小的子集各一个，在这个链中不可能再加入更多的子集

一般地，如果 S={1,2,…,n}\displaystyle{ S = \left\lbrace 1 , 2 , \ldots , n \right\rbrace }，最大链为

A0=∅⊂A1⊂A2⊂…⊂An=S\displaystyle{ A _{ 0 } = \varnothing \subset A _{ 1 } \subset A _{ 2 } \subset \ldots \subset A _{ n } = S }

最大链的数目等于 n!\displaystyle{ {n !} }，实际上是选择 {1,2,…,n}\displaystyle{ \left\lbrace 1 , 2 , \ldots , n \right\rbrace } 的一个全排列的过程

S\displaystyle{ S } 的一个子集 A\displaystyle{ A }，假设 A\displaystyle{ A } 的长度为 k\displaystyle{ k }，包含 A\displaystyle{ A } 的最大链 C\displaystyle{ C } 个数为 k!(n−k)!\displaystyle{ {k !} {\left( n - k \right) !} }

Sperner 定理

证明 S\displaystyle{ S } 是一个 n\displaystyle{ n } 元素集合，S\displaystyle{ S } 上的一个反链至多包含 (n⌊n2⌋)\displaystyle{ { n \choose \left\lfloor\frac{ n }{ 2 }\right\rfloor } } 个集合

设 A\displaystyle{ \mathcal{ A } } 是一个反链，用两种不同的方法计算有序对 (A,C)\displaystyle{ \left( A , C \right) } 的数目 β\displaystyle{ \beta }，其中 A\displaystyle{ A } 在 A\displaystyle{ \mathcal{ A } } 中，C\displaystyle{ C } 是包含 A\displaystyle{ A } 的最大链，有

β=∣{(A,C):A∈A,A∈C}∣\displaystyle{ \beta = \left| \left\lbrace \left( A , C \right) : A \in \mathcal{ A } , A \in C \right\rbrace \right| }
  • β\displaystyle{ \beta } 至多等于最大链的个数，即 β⩽n!\displaystyle{ \beta \leqslant {n !} }
    • 每个最大链最多只能包含 A\displaystyle{ \mathcal{ A } } 中的一个子集，因此最多只能是最大链的个数
  • 设 ak=∣{A:A∈A,∣A∣=k}∣\displaystyle{ a _{ k } = \left|\left\lbrace A : A \in \mathcal{ A } , \left|A\right| = k \right\rbrace\right| }，表示反链 A\displaystyle{ \mathcal{ A } } 中大小为 k\displaystyle{ k } 的子集个数
    • 如果 ∣A∣=k\displaystyle{ \left| A \right| = k }，则包含 A\displaystyle{ A } 的最大链 C\displaystyle{ C } 个数为 k!(n−k)!\displaystyle{ {k !} {\left( n - k \right) !} }
    • 由乘法原理，所有 ∣A∣=k\displaystyle{ \left| A \right| = k } 的 (A,C)\displaystyle{ \left( A , C \right) } 对数目为 akk!(n−k)!\displaystyle{ a _{ k } {k !} {\left( n - k \right) !} }
    • 由加法原理，β=∑k=0nakk!(n−k)!\displaystyle{ \beta = \sum _{ k = 0 } ^{ n } a _{ k } {k !} {\left( n - k \right) !} }

故

∑k=0nakk!(n−k)!⩽n!∑k=0nak(nk)⩽1\displaystyle{ \begin{aligned}\sum _{ k = 0 } ^{ n } a _{ k } {k !} {\left( n - k \right) !} & \leqslant {n !} \\ \sum _{ k = 0 } ^{ n } \frac{ a _{ k } }{ { n \choose k } } & \leqslant 1\end{aligned} }

为什么能推出

∣A∣⩽∑k=0nak⩽(n⌊n2⌋)\displaystyle{ \left| \mathcal{ A } \right| \leqslant \sum _{ k = 0 } ^{ n } a _{ k } \leqslant { n \choose \left\lfloor\frac{ n }{ 2 }\right\rfloor } }

多项式定理

(x1+x2+…xt)n=∑n!n1!n2!…nt!x1n1x2n2…xtnt\displaystyle{ \left( x _{ 1 } + x _{ 2 } + \ldots x _{ t } \right) ^{ n } = \sum \frac{ {n !} }{ {n _{ 1 } !} {n _{ 2 } !} \ldots {n _{ t } !} } x _{ 1 } ^{ n _{ 1 } } x _{ 2 } ^{ n _{ 2 } } \ldots x _{ t } ^{ n _{ t } } }

其中求和是对 ∑i=1tni=n\displaystyle{ \sum _{ i = 1 } ^{ t } n _{ i } = n } 的所有非负整数解 n1,n2,…,nt\displaystyle{ n _{ 1 } , n _{ 2 } , \ldots , n _{ t } } 进行的

项 x1n1x2n2…xtnt\displaystyle{ x _{ 1 } ^{ n _{ 1 } } x _{ 2 } ^{ n _{ 2 } } \ldots x _{ t } ^{ n _{ t } } } 出现的次数等于 (nn1)(n−n1n2)…(n−n1−…−nt−1nt)\displaystyle{ { n \choose n _{ 1 } } { n - n _{ 1 } \choose n _{ 2 } } \ldots { n - n _{ 1 } - \ldots - n _{ t - 1 } \choose n _{ t } } }，等价于在 n1+n2+…+nt=n\displaystyle{ n _{ 1 } + n _{ 2 } + \ldots + n _{ t } = n } 这个方程中找非负整数解

多项式系数

(nn1,n2,…,nt)=n!n1!n2!…nt!\displaystyle{ { n \choose n _{ 1 } , n _{ 2 } , \ldots , n _{ t } } = \frac{ {n !} }{ {n _{ 1 } !} {n _{ 2 } !} \ldots {n _{ t } !} } }