文章目录
第一章 组合分析概述
集合的计数
有 限 集 合 N { ∣ N ∣ : 集 合 中 元 素 的 个 数 ( N 的 基 ) ; B ( N ) : N 的 所 有 子 集 构 成 的 集 合 ; B ′ ( N ) : N 的 所 有 非 空 子 集 构 成 的 集 合 ( 块 , b l o c k ) . 有限集合N \begin{cases} |N|&: 集合中元素的个数(N的基);\\ \mathfrak{B}(N)&: N的所有子集构成的集合;\\ \mathfrak{B}'(N)&: N的所有非空子集构成的集合(块,block).\\ \end{cases} 有限集合N⎩⎪⎨⎪⎧∣N∣B(N)B′(N):集合中元素的个数(N的基);:N的所有子集构成的集合;:N的所有非空子集构成的集合(块,block).
-
N
N
N 的子集
B
(
N
)
\mathfrak{B}(N)
B(N)通过交/并/补运算构成一个布尔代数, 且其运算满足
De Morgan公式. - N N N的一个系 S \mathscr{S} S(一称子集系)是指 N N N的无重复块(block)构成的集合, 即 S ∈ B ′ ( B ′ ( N ) ) \mathscr{S}\in \mathfrak{B}'(\mathfrak{B}'(N)) S∈B′(B′(N));
- k − k- k−系是由 k k k个块构成的系.
加法原理
设事件 A A A有 m m m种选取方式,事件 B B B有 n n n中选取方式, 则选 A A A或 B B B共有 m + n m+n m+n种方式.
集合表示:
设 A , B A,B A,B为有限集,且 A ∩ B = ∅ A\cap B=\varnothing A∩B=∅,则 ∣ A ∪ B ∣ = ∣ A ∣ + ∣ B ∣ |A\cup B|=|A|+|B| ∣A∪B∣=∣A∣+∣B∣, n n n个有限集 A 1 , . . . , A n A_1,...,A_n A1,...,An满足 A i ∩ A j = ∅ ( i ≠ j ) A_i\cap A_j=\varnothing(i\ne j) Ai∩Aj=∅(i=j),
⇒ ∣ ⋃ i = 1 n A i ∣ = ∑ i = 1 n ∣ A i ∣ . \Rightarrow \left|\bigcup_{i=1}^nA_i\right|=\sum_{i=1}^n|A_i|. ⇒∣∣∣∣∣i=1⋃nAi∣∣∣∣∣=i=1∑n∣Ai∣.
乘法原理
设事件 A A A有 m m m种选取方式,事件 B B B有 n n n中选取方式, 则选 A A A之后再选 B B B共有 m ⋅ n m\cdot n m⋅n种方式.
集合表示: 设 A , B A,B A,B为有限集, ∣ A ∣ = m , ∣ B ∣ = n |A|=m,|B|=n ∣A∣=m,∣B∣=n, 则 ∣ A × B ∣ = ∣ A ∣ ⋅ ∣ B ∣ = m n |A\times B|=|A|\cdot|B|=mn ∣A×B∣=∣A∣⋅∣B∣=mn.
乘积集合, m m m个有限集 N i ( 1 ⩽ i ⩽ m ) N_i(1\leqslant i\leqslant m) Ni(1⩽i⩽m)的笛卡尔积 N 1 × N 2 × ⋯ × N m N_1\times N_2\times\cdots\times N_m N1×N2×⋯×Nm,
其元素为 ( y 1 , y 2 , . . . , y m ) , ( y i ∈ N i ) (y_1,y_2,...,y_m),\quad(y_i\in N_i) (y1,y2,...,ym),(yi∈Ni)
- 当 N i = N ( i ⩽ i ⩽ m ) ⇒ N 1 × N 2 × ⋯ × N m ≜ N m N_i=N(i\leqslant i\leqslant m)\Rightarrow N_1\times N_2\times\cdots\times N_m\triangleq N^m Ni=N(i⩽i⩽m)⇒N1×N2×⋯×Nm≜Nm;
定理: 有限个有限集的乘积集合的元素个数为
∣
∏
i
=
1
m
N
i
∣
=
∏
i
=
1
m
∣
N
i
∣
=
∣
N
1
∣
∣
N
2
∣
⋯
∣
N
m
∣
.
\left|\prod_{i=1}^mN_i\right|=\prod_{i=1}^m|N_i|=|N_1||N_2|\cdots|N_m|.
∣∣∣∣∣i=1∏mNi∣∣∣∣∣=i=1∏m∣Ni∣=∣N1∣∣N2∣⋯∣Nm∣.
例子: 正整数 n n n的素分解为 n = p 1 α 1 p 2 α 2 ⋯ p k α k n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} n=p1α1p2α2⋯pkαk( p i p_i pi为素数), 则 n n n的因子个数 d ( n ) = ? d(n)=? d(n)=?
n n n的因子个数为 p 1 δ 1 p 2 δ 2 ⋯ p k δ k p_1^{\delta_1}p_2^{\delta_2}\cdots p_k^{\delta_k} p1δ1p2δ2⋯pkδk, 其中, δ i ∈ A i = { 0 , 1 , 2 , . . . α i } \delta_i\in A_i=\{0,1,2,...\alpha_i\} δi∈Ai={0,1,2,...αi},
则 n n n的一个因子对应一组 ( δ 1 , δ 2 , … , δ k ) ∈ A 1 × A 2 × ⋯ × A k (\delta_1,\delta_2, \ldots ,\delta_k)\in A_1\times A_2\times\cdots \times A_k (δ1,δ2,…,δk)∈A1×A2×⋯×Ak,
⇒ d ( n ) = ∣ A 1 × A 2 × ⋯ × A k ∣ = ∣ A 1 ∣ ∣ A 2 ∣ ⋯ ∣ A k ∣ = ( α 1 + 1 ) ( α 2 + 1 ) ⋯ ( α k + 1 ) . \begin{aligned} \Rightarrow d(n)&= |A_1\times A_2\times \cdots \times A_k|\\ & = |A_1| |A_2| \cdots |A_k|\\ &= (\alpha_1+1)(\alpha_2+1)\cdots (\alpha_k+1). \end{aligned} ⇒d(n)=∣A1×A2×⋯×Ak∣=∣A1∣∣A2∣⋯∣Ak∣=(α1+1)(α2+1)⋯(αk+1).
一个具体的例子:
12 = 2 2 ⋅ 3 1 , ⇒ d ( 12 ) = 3 × 2 = 6. 12=2^2\cdot_3^1, \Rightarrow d(12)=3\times 2=6. 12=22⋅31,⇒d(12)=3×2=6.
映射
有限集
M
M
M到
N
N
N的映射
f
:
M
→
N
x
↦
y
=
f
(
x
)
\begin{aligned} f: M&\to N\\ x&\mapsto y=f(x)\\ \end{aligned}
f:Mx→N↦y=f(x)
- F ( M , N ) , o r N M F(M,N), or \ N^M F(M,N),or NM表示集合 M M M到 N N N的全体映射 f f f的集合.
定理A: 有限集
M
M
M到
N
N
N的映射个数为:
∣
F
(
M
,
N
)
∣
=
∣
N
M
∣
=
∣
N
∣
∣
M
∣
|F(M,N)|=|N^M|=|N|^{|M|}
∣F(M,N)∣=∣NM∣=∣N∣∣M∣
Proof:
设 ∣ M ∣ = m , ∣ N ∣ = n |M|=m,|N|=n ∣M∣=m,∣N∣=n, M = { x 1 , x 2 , . . . , x m } M=\{x_1,x_2,...,x_m\} M={x1,x2,...,xm}.
则 ∀ f ∈ F ( M , N ) \forall f\in F(M,N) ∀f∈F(M,N), 等价于给出 N N N的以一个 m m m元组 ( y 1 , y 2 , . . . , y m ) , ( y i ∈ N ) (y_1,y_2,...,y_m), (y_i\in N) (y1,y2,...,ym),(yi∈N)
即给定一个 f f f等价于给出 N m N^m Nm的一个 m m m元组, 于是有
∣ F ( M , N ) = ∣ N m ∣ = ∣ N ∣ m = n m = ∣ N ∣ ∣ M ∣ . |F(M,N)=|N^m|=|N|^m=n^m=|N|^{ |M| }. ∣F(M,N)=∣Nm∣=∣N∣m=nm=∣N∣∣M∣.
映射的分类:
f : M → N { 单 射 : ∀ x 1 , x 2 ∈ M , x 1 ≠ x 2 ⇒ f ( x 1 ) ≠ f ( x 2 ) ; 满 射 : ∀ y ∈ N , ∃ x ∈ M , 有 y = f ( x ) ; 双 射 : 既 是 单 射 又 是 满 射 ( 一 一 对 应 ) . f:M\to N \begin{cases} 单射: \forall x_1,x_2\in M, x_1\ne x_2\Rightarrow f(x_1)\ne f(x_2);\\ 满射: \forall y\in N, \exist x\in M, 有y=f(x);\\ 双射: 既是单射又是满射(一一对应).\\ \end{cases} f:M→N⎩⎪⎨⎪⎧单射:∀x1,x2∈M,x1=x2⇒f(x1)=f(x2);满射:∀y∈N,∃x∈M,有y=f(x);双射:既是单射又是满射(一一对应).
对于双射 f : M → N f:M\to N f:M→N(一一对应), ⇒ ∣ M ∣ = ∣ N ∣ \Rightarrow |M|=|N| ⇒∣M∣=∣N∣.
定理B: 有限集 M M M的子集个数为: ∣ B ( M ) ∣ = 2 ∣ M ∣ |B(M)|=2^{|M|} ∣B(M)∣=2∣M∣
Proof:
∀ A ∈ B ( M ) \forall A\in B(M) ∀A∈B(M), 即 A ⊂ M A\subset M A⊂M,
构造 f A f_A fA(子集 A A A的示性函数)
f A : M → N = { 0 , 1 } x ↦ f A ( x ) = { 1 , x ∈ A 0 , x ∉ A f_A: M\to N=\{0,1\}\\ x\mapsto f_A(x)=\begin{cases} 1,x\in A\\ 0,x\not\in A\\ \end{cases} fA:M→N={0,1}x↦fA(x)={1,x∈A0,x∈A
建立了 B ( M ) B(M) B(M)与 F ( M , N ) F(M,N) F(M,N)的一个一一对应.
于是 ∣ B ( M ) ∣ = ∣ F ( M , N ) ∣ = ∣ N ∣ ∣ M ∣ = 2 ∣ M ∣ |B(M)|=|F(M,N)|=|N|^{|M|}=2^{|M|} ∣B(M)∣=∣F(M,N)∣=∣N∣∣M∣=2∣M∣.
法二: 令
u
m
=
∣
B
(
M
)
∣
u_m=|B(M)|
um=∣B(M)∣
给定
x
∈
M
x\in M
x∈M 则< 的不含有$x
的
子
集
与
含
有
的子集与含有
的子集与含有x
的
子
集
个
数
一
样
多
,
且
均
为
的子集个数一样多, 且均为
的子集个数一样多,且均为u_{m-1}$, 于是我们有如下的递推关系
u
m
=
2
u
m
−
1
u_m=2u_{m-1}
um=2um−1
又由
u
0
=
1
u_0=1
u0=1,得到
u
m
=
2
m
=
2
∣
M
∣
u_m=2^m=2^{|M|}
um=2m=2∣M∣.
例子: n n n元集合 N N N的偶数元子集 E E E,奇数元子集 F F F, 则 ∣ E ∣ = ? , ∣ F ∣ = ? |E|=?,|F|=? ∣E∣=?,∣F∣=?.
解: 构造映射,
f
:
E
→
F
∀
A
∈
E
,
A
↦
f
(
A
)
=
{
A
\
{
x
}
,
x
∈
A
A
∪
{
x
}
,
x
∉
A
(
x
∈
N
)
\begin{aligned} f:E&\to F\\ \forall A\in E, A&\mapsto f(A)= \begin{cases} A\backslash\{x\},&x\in A\\ A\cup \{x\}, &x\not\in A \end{cases} (x\in N) \end{aligned}
f:E∀A∈E,A→F↦f(A)={A\{x},A∪{x},x∈Ax∈A(x∈N)
f
f
f为
E
E
E到
F
F
F的双射.
⇒ ∣ E ∣ = ∣ F ∣ = 1 2 ∣ B ( N ) ∣ = 2 n − 1 \Rightarrow |E|=|F|=\frac12|B(N)|=2^{n-1} ⇒∣E∣=∣F∣=21∣B(N)∣=2n−1.
集合的排列与组合
集合的排列
令 N N N表示 n n n元集合( ∣ N ∣ = n |N|=n ∣N∣=n), [ k ] = { 1 , 2 , . . . , k } [k]=\{1,2,...,k\} [k]={1,2,...,k}
定义1: 集合
N
N
N的一个
k
k
k排列
α
(
1
⩽
k
⩽
n
)
\alpha(1\leqslant k\leqslant n)
α(1⩽k⩽n)就是一个从
[
k
]
[k]
[k]到
N
N
N的单射
α
\alpha
α.
α
(
[
k
]
)
=
(
α
(
1
)
,
α
(
2
)
,
.
.
.
α
(
k
)
)
,
(
α
(
i
)
∈
N
,
α
(
i
)
≠
α
(
j
)
)
.
\alpha([k])=(\alpha(1),\alpha(2),...\alpha(k)),\quad (\alpha(i)\in N,\alpha(i)\ne \alpha(j)).
α([k])=(α(1),α(2),...α(k)),(α(i)∈N,α(i)=α(j)).
即
N
N
N的一个有序的
k
k
k元子集.
- A k ( N ) A_k(N) Ak(N)表示 N N N的所有的 k − k- k−排列的集合.
定理1: 集合
N
N
N的
k
−
k-
k−排列的个数
(
1
⩽
k
⩽
n
=
∣
N
∣
(1\leqslant k\leqslant n=|N|
(1⩽k⩽n=∣N∣)为
∣
A
k
(
N
)
∣
=
n
(
n
−
1
)
⋯
(
n
−
k
+
1
)
≜
(
n
)
k
(
n
的
降
k
阶
乘
)
|A_k(N)|=n(n-1)\cdots(n-k+1)\triangleq (n)_k \quad(n的降k阶乘)
∣Ak(N)∣=n(n−1)⋯(n−k+1)≜(n)k(n的降k阶乘)
球盒模型:
k k k个不同的球放入 n n n个不同的盒子, 每个盒子至多一个球的不同放法: n n n的降 k k k阶乘.
一些记号:
- ( n ) k = n ( n − 1 ) ⋯ ( n − k + 1 ) (n)_k=n(n-1)\cdots(n-k+1) (n)k=n(n−1)⋯(n−k+1), ( n ) 0 = 1 (n)_0=1 (n)0=1. n n n的降 k k k阶乘
- ⟨ n ⟩ k = n ( n + 1 ) ⋯ ( n + k − 1 ) \lang n\rang_k=n(n+1)\cdots(n+k-1) ⟨n⟩k=n(n+1)⋯(n+k−1), ⟨ n ⟩ 0 = 1 \lang n\rang_0=1 ⟨n⟩0=1. n n n的升 k k k阶乘
(超几何级数中, ( n ) k (n)_k (n)k表示 n n n的升 k k k阶乘)
更一般地, 对于复数z,非负整数k,
- ( z ) k = z ( z − 1 ) ⋯ ( z − k + 1 ) (z)_k=z(z-1)\cdots(z-k+1) (z)k=z(z−1)⋯(z−k+1), ( z ) 0 = 1 (z)_0=1 (z)0=1. z z z的降 k k k阶乘
- ⟨ z ⟩ k = z ( z + 1 ) ⋯ ( z + k − 1 ) \lang z\rang_k=z(z+1)\cdots(z+k-1) ⟨z⟩k=z(z+1)⋯(z+k−1), ⟨ z ⟩ 0 = 1 \lang z\rang_0=1 ⟨z⟩0=1. z z z的升 k k k阶乘
引入
Γ
−
\Gamma-
Γ−函数
Γ
(
x
+
1
)
=
x
Γ
(
x
)
\Gamma(x+1)=x\Gamma(x)
Γ(x+1)=xΓ(x)
(
z
)
k
=
Γ
(
z
+
1
)
Γ
(
z
−
k
+
1
)
,
⟨
z
⟩
k
=
Γ
(
z
+
k
)
Γ
(
z
)
(z)_k=\frac{\Gamma(z+1)}{\Gamma(z-k+1)}, \lang z\rang_k=\frac{\Gamma(z+k)}{\Gamma(z)}
(z)k=Γ(z−k+1)Γ(z+1),⟨z⟩k=Γ(z)Γ(z+k)
k
k
k可以不是非负整数
Γ
\Gamma
Γ函数的两种定义
Γ
(
x
)
=
∫
0
+
∞
t
x
−
1
e
−
t
d
t
Γ
(
x
)
=
lim
n
→
∞
n
!
n
x
−
1
⟨
x
⟩
n
\begin{aligned} \Gamma(x)&=\int_0^{+\infty}t^{x-1}e^{-t}\text{d}t\\ \Gamma(x)&=\lim_{n\to\infty}\frac{n!n^{x-1}}{\lang x\rang_n}\\ \end{aligned}
Γ(x)Γ(x)=∫0+∞tx−1e−tdt=n→∞lim⟨x⟩nn!nx−1
N N N的置换, σ : N → N \sigma: N\to N σ:N→N(一一对应) (全排列)
定理2: n n n元集合 N N N的所有置换的个数为 n ! n! n!.
集合的组合
定义2: 集合 N N N的一个 k − k- k−组合(or k − b l o c k k-block k−block) B B B就是 N N N的一个 k k k元非空子集(即: B ⊂ N B\subset N B⊂N, 且 1 ⩽ k = ∣ B ∣ ⩽ n = ∣ N ∣ 1\leqslant k=|B|\leqslant n=|N| 1⩽k=∣B∣⩽n=∣N∣)
- 若 k ⩾ 0 k\geqslant0 k⩾0, 称 N N N的 k − k- k−子集 用 B k ( N ) B_k(N) Bk(N)表示.
几种等价形式:
- 令
φ
:
N
→
{
0
,
1
}
)
\varphi:N\to\{0,1\})
φ:N→{0,1}), 且
∑
x
∈
N
φ
(
x
)
=
k
\sum_{x\in N}\varphi(x)=k
∑x∈Nφ(x)=k, 这样映射的全体与
B
k
(
x
)
B_k(x)
Bk(x)一一对应;
B ∈ B k ( N ) ⟺ φ = φ B = { 1 , x ∈ B 0 , x ∉ B ( x ∈ N ) B\in B_k(N)\iff \varphi=\varphi_B=\begin{cases} 1,x\in B\\ 0,x\not\in B\\ \end{cases}(x\in N) B∈Bk(N)⟺φ=φB={1,x∈B0,x∈B(x∈N) - 不定方程
x
1
+
x
2
+
⋯
+
x
n
=
k
x_1+x_2+\cdots+x_n=k
x1+x2+⋯+xn=k, 其中
x
i
=
0
o
r
1
x_i=0or1
xi=0or1.
方程的解集合与 B k ( N ) B_k(N) Bk(N)一一对应; ( N = { y 1 , y 2 , . . . , y n } N=\{y_1,y_2,...,y_n\} N={y1,y2,...,yn}) -
球盒模型:
将 k k k个相同的球放入 n n n个不同的盒子, 且每个盒子至多一个球的不同放法.
定理3:
N
N
N的
k
−
k-
k−子集的个数(
0
⩽
k
⩽
n
=
∣
N
∣
0\leqslant k\leqslant n=|N|
0⩽k⩽n=∣N∣)为:
∣
B
k
(
N
)
∣
=
n
!
(
n
−
k
)
!
k
!
=
(
n
)
k
k
!
≜
(
n
k
)
(
称
为
二项式系数
)
|B_k(N)|=\frac{n!}{(n-k)!k!}=\frac{(n)_k}{k!}\triangleq{n\choose k}(称为\textbf{二项式系数})
∣Bk(N)∣=(n−k)!k!n!=k!(n)k≜(kn)(称为二项式系数)
证明:
用映射证明: k ! ∣ B k ( N ) ∣ = ∣ A k ( N ) ∣ = ( n ) k k!|B_k(N)|=|A_k(N)|=(n)_k k!∣Bk(N)∣=∣Ak(N)∣=(n)k.
令
f : A k ( N ) → B k ( N ) α = ( α ( 1 ) , α ( 2 ) , . . . , α ( k ) ) ↦ f ( α ) = { α ( 1 ) , α ( 2 ) , . . , α ( k ) } ( 由 有 序 变 为 无 序 ) \begin{aligned} f:A_k(N)&\to B_k(N)\\ \alpha=(\alpha(1),\alpha(2),...,\alpha(k))&\mapsto f(\alpha)=\{\alpha(1),\alpha(2),..,\alpha(k)\}(由有序变为无序) \end{aligned} f:Ak(N)α=(α(1),α(2),...,α(k))→Bk(N)↦f(α)={α(1),α(2),..,α(k)}(由有序变为无序)
则 ∀ B ∈ B k ( N ) ⇒ ∣ f − 1 ( B ) ∣ = k ! \forall B\in B_k(N)\Rightarrow |f^{-1}(B)|=k! ∀B∈Bk(N)⇒∣f−1(B)∣=k!,
当 B B B选定 B k ( N ) B_k(N) Bk(N), f − 1 ( B ) f^{-1}(B) f−1(B)互不相交且完全覆盖 A k ( N ) A_k(N) Ak(N), 故
( n ) k = ∣ A k ( N ) ∣ = ∑ B ∈ B k ( N ) ∣ f − 1 ( B ) ∣ = k ! ∣ B k ( N ) ∣ , ⇒ ∣ B k ( N ) ∣ = ( n ) k k ! = ( n k ) . \begin{aligned} (n)_k&=|A_k(N)|=\sum_{B\in B_k(N)}|f^{-1}(B)|=k!\,|B_k(N)|,\\ &\Rightarrow |B_k(N)|=\frac{(n)_k}{k!}=\binom nk. \end{aligned} (n)k=∣Ak(N)∣=B∈Bk(N)∑∣f−1(B)∣=k!∣Bk(N)∣,⇒∣Bk(N)∣=k!(n)k=(kn).
(牧羊人原理)
二项式系数满足的关系式:
- ( n k ) = ( n − 1 k − 1 ) + ( n − 1 k ) \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k} (kn)=(k−1n−1)+(kn−1);(可以推出杨辉三角,Pascal三角)
- ( n k ) = n k ( n − 1 k − 1 ) \binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1} (kn)=kn(k−1n−1);
- ( n + 1 k + 1 ) = ( k k ) + ( k + 1 k ) + ⋯ + ( n k ) \binom{n+1}{k+1}=\binom{k}{k}+\binom{k+1}{k}+\cdots+\binom{n}{k} (k+1n+1)=(kk)+(kk+1)+⋯+(kn);
- ( n + k + 1 k ) = ( n + k k ) + ( n + k − 1 k − 1 ) + ⋯ + ( n + 1 1 ) + ( n 0 ) \binom{n+k+1}{k}=\binom{n+k}{k}+\binom{n+k-1}{k-1}+\cdots+\binom{n+1}{1}+\binom{n}{0} (kn+k+1)=(kn+k)+(k−1n+k−1)+⋯+(1n+1)+(0n);
其中1,2,4式的
n
n
n可以推广到
z
z
z(复数), 对于3则不能直接推广(由于3式右边的
n
n
n是由
k
k
k递增得到的, 需要满足
z
z
z的降
k
k
k阶乘)需要变成如下的递减形式(通过1式一步步递归得到下式):
(
z
+
1
k
+
1
)
=
(
z
k
)
+
(
z
−
1
k
)
+
⋯
+
(
z
−
s
k
)
+
(
z
−
s
k
+
1
)
\binom{z+1}{k+1}=\binom{z}{k}+\binom{z-1}{k}+\cdots+\binom{z-s}{k}+\binom{z-s}{k+1}
(k+1z+1)=(kz)+(kz−1)+⋯+(kz−s)+(k+1z−s)
其中
s
s
s为正整数, 最后一项保证了当
z
−
s
=
k
+
1
z-s=k+1
z−s=k+1时, 能够和上面原来的3式中
(
k
k
)
\binom kk
(kk)保持一致.
代数证明:
直接展开之后再合并即可(代入验证等式成立), 这里不赘述.
组合证明:
(利用映射,双射以及相应的组合定义来证明)
可以直接从组合意义出发, 或者通过集合的计数方法.