Skip to content

第五章 二项式系数

5.1 帕斯卡三角形

帕斯卡恒等式

(nk)=(n1k)+(n1k1)\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)xn1y+(nn)yn=k=0n(nk)xnkyk\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)=n2n1\displaystyle{ 1 { n \choose 1 } + 2 { n \choose 2 } + \ldots + n { n \choose n } = n 2 ^{ n - 1 } }

由于

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

所以

1(n1)++n(nn)=n(n10)+n(n1n1)=n2n1\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 } 个,从偶数集合中选 nk\displaystyle{ n - k } 个,两者独立,因此有 (nk)(nnk)\displaystyle{ { n \choose k } { n \choose n - k } } 种方法,k\displaystyle{ k }0n\displaystyle{ 0 \sim n },因此等式两边相等

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

(rk)={r(r1)(rk+1)k!k11k=00k1\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 } } 中的最大者为 (nn2)=(nn2)\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 } 的一个反链
    • 用这种方法构造的反链最长为 (nn2)\displaystyle{ { n \choose \left\lfloor\frac{ n }{ 2 }\right\rfloor } }
  • 反链最多包含 (nn2)\displaystyle{ { n \choose \left\lfloor\frac{ n }{ 2 }\right\rfloor } } 个集合

S\displaystyle{ S } 的子集的集合 C\displaystyle{ C } 是一条链,只要对于 C\displaystyle{ C } 中的每一对子集,总有一个包含在另一个之中。A1,A2C,A1A2    A1A2 or A2A1\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=A1A2An=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!(nk)!\displaystyle{ {k !} {\left( n - k \right) !} }

Sperner 定理

证明 S\displaystyle{ S } 是一个 n\displaystyle{ n } 元素集合,S\displaystyle{ S } 上的一个反链至多包含 (nn2)\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):AA,AC}\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:AA,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!(nk)!\displaystyle{ {k !} {\left( n - k \right) !} }
    • 由乘法原理,所有 A=k\displaystyle{ \left| A \right| = k }(A,C)\displaystyle{ \left( A , C \right) } 对数目为 akk!(nk)!\displaystyle{ a _{ k } {k !} {\left( n - k \right) !} }
    • 由加法原理,β=k=0nakk!(nk)!\displaystyle{ \beta = \sum _{ k = 0 } ^{ n } a _{ k } {k !} {\left( n - k \right) !} }

k=0nakk!(nk)!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} }

为什么能推出

Ak=0nak(nn2)\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!x1n1x2n2xtnt\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 } } 进行的

x1n1x2n2xtnt\displaystyle{ x _{ 1 } ^{ n _{ 1 } } x _{ 2 } ^{ n _{ 2 } } \ldots x _{ t } ^{ n _{ t } } } 出现的次数等于 (nn1)(nn1n2)(nn1nt1nt)\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 } !} } }