二项式系数 Binomial Coefficients
本文最后更新于 45 天前,其中的信息可能已经有所发展或是发生改变。

1.1 基本恒等式 Basic Identities

1.1.1 定义 Definition

$\binom nk$ 表示二项式系数,其中 $n$ 称作上指标 (upper index),而称 $k$ 为下指标 (lower index)。

$$
\binom rk=
\begin{cases}
\frac{r^{\underline{k}}}{k!} ,& k\ge0\\
0, & k<0
\end{cases}

\quad (k\in \Z)
$$

1.1.2 对称恒等式 Symmetric Identity

$$
\binom nk=\binom n{n-k}\quad n\in \N
$$

证明:
$$
\binom nk=\frac{n!}{k!(n-k)!}=\frac{n!}{(n-(n-k))!(n-k)!}=\binom n{n-k}
$$

1.1.3 吸收恒等式 Absorption Identity

$$
\binom rk=\frac rk\binom {r-1}{k-1}
$$

证明:

  1. $k> 0$
    $$
    \binom rk=\frac{r^{\underline k}}{k!}=\frac{r{(r-1)}^{\underline {k-1}}}{k(k-1)!}=\frac rk\binom {r-1}{k-1}
    $$
  2. $k<0$

$$
\binom rk = 0 = \binom {r-1}{k-1}
$$

1.1.3+ 相伴恒等式 Companion Identity

$$
(r-k)\binom rk=r\binom {r-1}k
$$

证明:
$$
\begin{aligned}
(r-k)\binom rk & =(r-k)\binom r {r-k}\\
& = r\binom {r-1}{r-k-1}\\
& = r\binom {r-1}k
\end{aligned}
$$
容易发现上述证明过程仅当 $r\in \Z$ 时成立,但其实相伴恒等式对于所有 $r\in \R$ 均成立。具体证明需要用到多项式推理法。

1.1.4 加法公式 Addition Formula

$$
\binom rk = \binom {r-1}k+\binom {r-1}{k-1}
$$

证明:
$$
r\binom rk=(r-k)\binom rk +k\binom rk=r\binom {r-1}k+r\binom {r-1}{k-1}
$$

1.1.5 上指标求和 Summation of Upper Indicators

$$
\begin{align}
\sum_{0\leq k\leq n}\binom km =\binom{n+1}{m+1}\quad m,n\in \N \tag1
\end{align}
$$

证明:

利用数学归纳法。

$n=0$ 时,左边 $=\binom 0m=[m=0]=\binom 1{m+1}=$ 右边

设 $n=N \ (N\in \N_+)$ 时 $(1)$ 成立,那么 $n=N+1$ 时,
$$
\begin{aligned}
\sum_{0\leq k\leq n+1}\binom km & =\sum_{0\leq k\leq n}\binom km+\binom {n+1}m\\
& = \binom {n+1}{m+1} +\binom {n+1}m\\
& = \binom {n+2}{m+1}
\end{aligned}
$$

所以对一切 $n\in \N$,$(1)$ 成立。

1.1.6 平行求和法 Parallel Summation

$$
\sum_{k\leq n}\binom {r+k}k=\binom{r+n+1}n \quad n\in \Z
$$

证明:
$$
\begin{aligned}
\sum_{k\leq n}\binom {m+k}k & =\sum_{-m\leq k\leq n}\binom {m+k}k\\
& = \sum_{-m\leq k\leq n}\binom {m+k}m\\
& = \sum_{0\leq k\leq m+n}\binom km\\
& = \binom {m+n+1}{m+1}
\end{aligned}
$$

注意到以上证明当且仅当 $m+k\ge 0$ 才可以这么做(第二行运用到对称法则),因此我们在第一步去掉了 $k<-m$ 的项。

1.1.7 上指标反转 Upper Negation

$$
\binom rk=(-1)^k \binom {k-r-1}k \quad k\in \Z
$$

证明:

  1. $k\ge 0$
    $$
    \binom rk=\frac{r^{\underline k}}{k!}=\frac{(-1)^k (-r)(1-r)\cdots (k-1-r)}{k!}=\frac {(-1)^k(k-r-1)^{\underline k}}{k!}=(-1)^k\binom {k-r-1}k
    $$
  2. $k<0$

$$
\binom rk = 0 = (-1)^k\binom {k-r-1}k
$$

1.1.8 三项式版恒等式 Trinomial Version of Identity

$$
\binom rm\binom mk=\binom rk\binom {r-k}{m-k} \quad m,k\in \Z
$$

证明:

若 $r\ge m\ge k\ge 0$,
$$
\begin{aligned}
\binom rm\binom mk & = \frac{r!}{m!(r-m)!}\frac{m!}{k!(m-k)!} \\
& = \frac{r!}{k!(m-k)!(r-m)!}\\
& = \frac{r!}{k!(r-k)!}\frac{(r-k)!}{(m-k)!(r-m)!}\\
& = \binom rk \binom {r-k}{m-k}
\end{aligned}
$$

若 $m<k$ 或 $k<0$ 等式两边都是 $0$。

1.1.9 范德蒙德卷积 Vandermonde Convolution

$$
\sum_k \binom r{m+k}\binom s{n-k}=\binom {r+s}{m+n} \quad m,n\in \Z
$$

证明:

这里可以暂时通过组合意义来简单证明:

先从 $r$ 个球中取 $m+k$ 个,再从 $s$ 个球中取 $n-k$ 个,就相当于在 $r+s$ 个球中取 $m+n$ 个。

具体严谨证明见下文——生成函数。

1.1.10 二项式定理 Binomial Theorem

$$
(x+y)^n=\sum_{k=0}^n\binom nky^kx^{n-k}\quad n\in Z_+
$$

特别地,

$$
(1+x)^n=\sum_{k=0}^n\binom nkx^k\quad n\in Z_+
$$

1.1.11 其他基本组合恒等式 Other Basic Combination Identities

$$
\sum_{k=0}^n \binom nk=2^n \tag 1
$$

$$
\sum_{k=0}^n (-1)^k\binom nk=0 \tag 2
$$

1.2 生成函数 Generating Function

1.2.1 卷积 Convolution

$$
c_n=\sum_{k=0}^na_kb_{n-k} \tag1
$$

由 $(1)$ 所定义的序列 $\langle c_n\rangle$ 称为序列 $\langle a_n\rangle$ 和 $\langle b_n \rangle$ 的卷积。

1.2.2 二项式定理与生成函数 Binomial Theorem and Generating Function

$$
(1+z)^r=\sum_{k\ge 0}\binom rkz^k \tag1
$$

类似地,

$$
(1+z)^s=\sum_{k\ge 0}\binom skz^k \tag2
$$

将 $(1)(2)$ 相乘,我们可以得到另外一个生成函数:

$$
(1+z)^r(1+z)^s=(1+z)^{r+s}
$$

让这个等式两边 $z^n$ 的系数相等就给出:

$$
\sum_{k=0}^n\binom rk\binom s{n-k}=\binom {r+s}n
$$

我们就发现了范德蒙德卷积。

此外我们还有一系列重要的恒等式:

$$
(1-z)^r=\sum_{k\ge 0}(-1)^k\binom rk\tag 3
$$

$$
\frac 1{(1-z)^{n+1}}=\sum_{k\ge 0}\binom {n+k}nz^k \quad n\in \N \tag 4
$$

当 $n=0$ 时,我们就得到了 $(4)$ 的特例,即几何级数:

$$
\frac 1{1-z}=1+z+z^2+z^3+\cdots =\sum_{k\ge 0}z^k
$$

这就是序列 $\langle 1,1,1,\cdots \rangle$ 的生成函数。

1.3 基本练习 Basic Practice

1.3.1 利用基本组合恒等式 Use Basic Combinatorial Identities

  1. 证明:$\sum_{k=1}^n (-1)^{k-1}k\binom nk=0 \ (n\ge2)$

$$
\begin{aligned}
LHS & = \sum_{k=1}^n(-1)^{k-1}n\binom {n-1}{k-1} \\
& = n\sum_{k}(-1)^k\binom nk\\
& = n\binom 0n\\
& = n[n=0]\\
& = 0 = RHS
\end{aligned}
$$

  1. 证明:$\sum_{k=p}^n\binom nk\binom kp=\binom np2^{n-p}$

$$
\begin{aligned}
LHS & = \sum_{k=p}^n\binom np\binom {n-k}{k-p}\\
& = \binom np\sum_{k=0}^{n-p}\binom {n-p-k}k\\
& = \binom np 2^{n-p} = RHS
\end{aligned}
$$

1.3.2 利用生成函数 Use Generating Functions

  1. 证明:
  2. $\sum_{k=0}^n{\binom nk}^2=\binom n{2n}$
  3. $\sum_{k=1}^{2n-1}\binom {2n}k[2 | (k-1)]=\frac 12{\binom {4n}{2n}+(-1)^{n-1}\binom {2n}n}$

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇