组合数学初步

Kirkman女学生问题

某寄宿学校有十五名女生,她们经常每天三人一行地散步,问要怎样安排才能使每个女生同其他女生每一个女生在同一行中散步,并且恰好每周一次?

把15个女生分成5组，每组3人，例如  A 1 2 3 ，并假设它们不是队列而是循环体
                                                   B 1 2 3
                                                   C 1 2 3
                                                   D 1 2 3
                                                   E 1 2 3
第一次如上同行。第二次就把A1和B1对调，A2和C2对调，A3和C3对调；同理，每一行的第一个人与其数字间隔相同的彼行的同一位置对调，也就是说B1就和C1对调，B2和D2对调，B3和E3对调，以此类推。

Euler 36军官问题

36军官问题是普鲁士国王腓特烈大帝在一次阅提出来的，他要求将来自六个不同部队，六种军阶各一名的总共36名军官排成六行、六列，使得每一行、每一行都既有各部队的代表，又有各军阶的代表。

结果，指挥官急的团团转，却无论怎样要求，。后来，他们只得去请教数学家欧拉。

欧拉用六个大写拉丁字母（A，B，C，D，E，F）表示六个不同的部队，六个小写拉丁字母（a,b,c,d,e,f）表示六种不同的军阶，这样，每一名军官就可以用一对有序拉丁字母对表示了。如（A，a）就表示A部队的军阶是a的那一名军官，于是问题变为将36对有序拉丁字母对排成六行列的方阵，使得每行、每列中，A、B、C、D、E、F、a、b、c、d、e、f中的每个字母都出现一次。这个方阵可以看出是由两个方阵合成的，一个方阵由Ａ，Ｂ，Ｃ，Ｄ，Ｅ，Ｆ这六个大写字母各重复出现六次组成，另一方阵由a,b,c,d,e,f这六个小定字母各重复六次组成，在每个方阵的每一行第一列中，每个字母恰出现一次。这种由拉丁字母组成的方阵就叫拉丁方。当然，这是用拉丁字母作记号并非本质的，也可以换成任何其它的记号。一般由n个不同的符号，每符号出现n次所排成的几阶方阵，若在这个方阵的每一行、每一列中，n个符号中的每一wh 都恰出现一次，这样的方阵就叫符号就叫n阶拉方。由两个n阶拉丁方可以这样合成一个由有序符号对组成的方阵，使得每有序符号对的第一个符号和第二个符号分别是第一个和第三个拉丁方中同一位置的符号。后所合成的有序对方阵中的任何两个有序对都不同，则称原来的两个拉丁方正交。这样一来，问幻又变为是否存在六阶正交拉丁幻方的问题了。

欧拉在作了种尝长工之后，断言：六阶正交拉丁方是不存在的。但是，他末能给出严格的证明，他进而想：任何阶数是奇数的２倍的正交拉方都不存在，直到1900年，塔里（Tarrg）才用完全归纳法很吃力地证明了：六阶正交拉丁不存在。

欧拉末能严格证明六阶正交拉丁方的不存在，但都发现了拉丁方和幻方之间的一种联系。他发表了一篇题为《Ｏn  A  New Tgpe of Magic Square》（《一种新型幻方》）的论文，提出了用正交拉丁方合成幻方的方法，这是在幻方构造理论上的一大贡献。

拉丁方和正交拉丁方

可以证明,对于自然数n,总存在n阶拉丁方.

当n!=2,6时,总存在两个正交的n阶拉丁方；

S到T的映射M: 对于每个a in S, 都有T中惟一确定的元素 b=M(a)与它对应.

若对于每个b in T都存在a in S,使M(a)=b,则称映射M是映上的.

映上的1-1映射称为一一对应.

具有n个元素的有限集称为n-集.

集合S中具有n个元素的子集称为S的n-子集.

S的r-可重排列(或r-样本). =n^r.

n-集的r-排列P(n,r). 可以证明P(n,r)=n(n-1)…(n-r+1).

S的r-可重组合(或r-选取). (ⁿ_r), S中的元素b在r-可重组合中出现的次数称为b在这可重组合中的重数.

S的r-组合(或n集的r-组合).

n-集中所有不同r-组合(或r-子集)的个数用C(n,r)来表示.

定理:C(n,r)=(ⁿ_r).

例1.5 给定平面上任意3点不共线的25点,能确定多少条直线?能确定多少个三角形?

解: C(25,2)=300；             C(25,3)=2300

定理1.6 n-集中所有不同r-可重组合的个数为:(^n+r-1_r).

证明: n-集S的每一个r-可重组合 <- --- ->(n+r-1)集S*的每一个r-组合

容易证明此映射为一一映射.

例4 某食品店供应8种糕点.如果一盒装12只糕点,有多少种不同的盒装糕点?

(^8+12-1₁₂)=(¹⁹₇)种

例1.7 从k-集中选取序列的项,能组成多少个长为r的递增序列? (^k+r-1_r)

定理1.7 k-集中每个元素重数至少为1的所有r-可重组合的个数为(^r-1_k-1),这里r>=1.

证明: k>r; k=r易证.

k<r时,映射: A的所有(r-k)-可重组合

例4中,每盒中都装有8种糕点,问有多少种不同的盒装糕点?(^12-1_8-1)

定理1.8 k-集S={a₁,a₂,…,a_n},而n₁,n₂,…,n_k是k个正整数,且: n=n₁+n₂+…+n_k.则S中元素a_i出现n_i次的所有n-可重排列的个数为:

n!/ (n₁!n₂!...n_k!)

证明: n-可重排列有n个有序位置.

首先,从n个位置中选出n₁个位置放a₁, 有(ⁿ_n1)种选法;

再从余下的n-n₁个位置中选出n₂个位置放a₂,有(^n-n1_n2)种选法;

…

依此类推,最后得证.

二项式系数

Pascal定理: (ⁿ_k)=(^n-1_k)+(^n-1_k-1)

证明: 取x in S, 分成两类:不含x；含x

定理1.0 n是正整数,若n是偶数 (ⁿ_n/2)最大,先增后减；若n是奇数,(ⁿ_(n-1)/2)= (ⁿ_(n+1)/2),亦先增后减.

二项式定理:

证明方法一: 取因子

证明方法二: 数学归纳法

性质2: (ⁿ_k)=n/k (^n-1_k-1)

性质3:sum_k=0ⁿ(ⁿ_k)=2ⁿ.

性质4: sum_k=0ⁿ (-1)^k (ⁿ_k)=0.

性质5: sum_k=0ⁿ k(ⁿ_k)=n2^n-1.

证明: 方法一,由性质2,3；

方法二: (1+x)ⁿ求导 -- ->同理,对(1+x)ⁿ求二阶导sum_k=0ⁿ k²(ⁿ_k)=n(n+1)2^n-2.

性质7:设n为自然数,则:

sum_k=0ⁿ (-1)^k+1/(k+1) (ⁿ_k)=n/(n+1).

证明:方法一,性质2,4,

方法二: 对(1-z)ⁿ求原函数,常数项C令z=0则得C=1/(n+1).

性质8:设m,m,n为自然数,则有:

sum_k=0ⁿ(^m1_k)(^m2_n-k)=(^m1+m2_n)

证明:<1> n>m₁+m₂,

<2> n<=m₁+m₂,

在性质8中令m₁=m₂=n,得结论sum_k=0ⁿ (ⁿ_k)²=(²ⁿ_n).

证明组合数恒等式的方法很多,归纳起来大致有下面几种方法(有时会综合使用):

(1)     用公式(ⁿ_k)=n!/[k!(n-k)!]

(2)     用Pascal定理: (ⁿ_k)=(^n-1_k)+(^n-1_k-1)

(3)     数学归纳法;

(4)     用公式sum_k=0ⁿ (ⁿ_k)x^k=(1+x)ⁿ.

(5)     用组合方法.

有限集的子集类

分配

抽屉原理:

证明:任意给定7个实数,其中必有两个数 a,b满足:

0<= (a-b)/(1+ab) <=sqrt(3)/3

此题是加拿大16届数学奥林匹克试题(1984年).

由推论2.2.1,在所给的7个实数中,至少有4个数同时为非负数或同时为负数,不妨设为前者.

从中取出4个非负数,设它们为:

tan theta1, tan theta2, tan theta3, tan theta4 (0<=theta_i<=PI/2)

0, PI/6, PI/3, PI/2分成三个区间,4个非负数中必有两个属于同一区间.不妨设theta1<=theta2属于同一区间,则0<=theta2-theta1<=PI/6.

由tan(a-b)= (tan a-tan b)/(1+tan b * tan a)可知结论成立.

容斥原理:

递推关系:

Fibonacci数列, 通项公式

定理1.3:

f(n)=sum_i=0ⁿ (^n-i_i) = sum_i=0^[n/2] (^n-i_i) 归纳法证明

所有互异特征根q₁,q₂,…,q_t,且q_i的重数为l_i,

递推关系式的一般解:

H*(n)=sum_i=1^t q_iⁿ (sum_j=0^li-1 C_{i j-1} n^j)

迭代与归纳:

梵塔之谜:

h(0)=0, h(n)=2h(n-1)+1;

用数学归纳法可知h(n)=2ⁿ-1

Catalan数

Sirtling数

生成函数:

幻方:

辛几何引论

Chapter 1:数学基础

反对称形式:

我们用V来表示特征!=2的域k上的有限维向量空间,用A^p(V)来表示V上取值于k中的反对称p-线性形式(或称p-形式)所构成的向量空间,特别地, A⁰(V)=k, A¹(V)就是V的对偶空间V*.

设α∈A^p(V), β∈ A^q(V),则p-形式α和q-形式β的外积α∧β是一个p+q – 形式,它在(x₁,x₂,…,x_p+q)∈V×V×…×V (p+q个V)处的值由下式决定：

α∧β(x₁,x₂,…,x_p+q)=∑r∈S(p,q)sg(τ) (x_τ(1),x

实变摘要

Def:环

X上的集类R称为一个环,如果对任何E,F in R有

E并F in R, E-F in R.

如果还有X in R,则称R为X上的代数

环是只对有限并运算封闭的集类

σ-环是对差与可列并运算封闭的集类,而σ-代数则是对余运算也封闭的σ-环

推论:从一个集类直接生成σ-环与先生成环,再由环生成σ-环是一样的

Def:单调类 X上的集类M称为单调类,如果M中任何单调列 {E_n}都有limE_n in M.

注:

1.       任意多个单调类的交仍是单调类

2.       σ-环一定是单调类

3.       单调环一定是σ-环,但是一般的单调类未必是环

Def同胚: f与f ^-1均连续

Hausdorff空间:两个任意不同的点有彼此不相交的邻域 (R上的普通拓扑 和 离散拓扑都 是Hausdorff空间)

离散事件动态系统-极大代数方法

R’是实数集合，e定义为-infinity,令R=R’并e，在R上定义加法和乘法：

加法：a⊕b:=max(a,b)

乘法：a.b:=a+b (普通意义下的加法)

称D={R, ⊕，.}为一个极大代数

其他的类似代数系统有半环( semiring) 、双子代数(dioid)和极小代数等.双子代数是一个比极大代数更一般的代数系统概念;极小代数是极大代数的对偶形式。

设E_n×n=[a_ij] a_ii=0, 其余a_ij=e；则E是D上的n阶单位矩阵。

满足BA=AB=E的矩阵A、B互逆。

图G(A)称为矩阵A的关联图.

定理1.2.1：设A_n×n, 则A^r_ij＝Σ_pW_p,其中p是G(A)中从点i到点j的任意一条长为r的路，W_p表示其权重。

证明：归纳法

定理1.2.2(化下三角阵): 设A_n×n, G(A)含w个强连通支,则存在置换阵P_n×n,使得

PAP^-1=[A₁              A₁₂          …             A_1w

Phi               A₂            …             A_2w

… …             …             …

Phi               Phi          …             A_w]

其中:A_i都是不可约的,它们对应G(A)的w个强连通支,Phi是每个元素均为e的阵.

离散事件动态系统的建模

法国人G.Cohen等人创立了极大代数上的线性系统理论.

定义: 一个确定性离散事件系统,可以用一个四元组(A,V,R,P)来描述,其中(A,V)是一个赋权有向图,A是所有活动的集合,设共有phi个活动,对它们编号为1,2,…,phi；V是所有弧的集合,(ij) in V表示活动i到活动j的弧.系统是确定的,是指图(A,V)中没有回路.否则,可能此回路上任意两个活动a和b,a既比b早发生,又比b晚发生,矛盾. R是所有资源的集合,设共有N个资源,对它们编号1,2,…,N；任一资源r in R,图中对应一条路Pr,称Pr为资源r的路.P表示所有资源在图(A,V)中所对应的路的集合. 每一个Pr in P,都有一个起始活动和终止活动,分别用l(r)和k(r)来表示.在图(A,V)中,弧(ij)的权重用tij来表示. 设zi表示活动i的开始时刻,ur表示资源r可以投入使用的时刻,如果(ji) in V,则有: zi>=zj+tji 这里加法是通常意义下的. 如果i=l(r),即资源r的起始活动是i,则有: zi>=ur zi表达式略… 设F in D phi×phi是图(A,V)的关联矩阵,则有: (F)ij:=      t, 如果(ij) in V;     e, 否则 设G in D N×phi,它的元素定义为: (G)ri:=     0, 如果l(r)=i                        e,否则 令Z=(z1z2…zphi),U=(u1u2…uN) 于是得到zi表达式矩阵形式: Z=ZF⊕UG 用xr表示资源r释放出来的时刻,设F in D phi×N,它的元素定义为: (F)ir:=      ti, 如果k(r)=i                       e,否则 其中t表示活动i从开始到结束的时间间隔,令X=(x1x2…xN),那么有X=ZH. 定理1.3.1 如果U是已知的,则方程Z=ZF⊕UG有如下解: Z=UGF* 且解是唯一的,其中F*=E⊕F⊕F2⊕…⊕Fphi-1. 证明: 由Z=ZF⊕UG有 Z=ZF⊕UG=(ZF⊕UG)F⊕UG  =ZF2⊕UG(E⊕F)     (?????????????????????????????????????)  =…  =ZFphi⊕UG(E⊕F⊕F2⊕…⊕Fphi-1) 因为F是(A,V)的关联矩阵,所以由定理1.2.1知(Fphi)ij等于图(A,V)中从点i到点j的长为phi的最重路的权重,但图(A,V)中没有回路,图中任何路的长度都不大于phi-1,因此必定有(Fphi)ij =e, 即有Fphi=Phi, 得证.

设加工第k批时资源r可以投入使用的时刻为u_r(k),释放出来的时刻为x_r(k) (1<=r<=N),

在文献[6]中指出,假设系统中的每个资源从加工第k-1批中释放出来后,即可投入到第k批的加工中去,这样对于系统则有:

u_i(k)=k_ix(k-1)

因为资源一释放出来即可投入到下一批加工,所以某一时刻在系统中加工的工件可能不是同一批的,而是同时加工两批或两批以上的工作.

一般地,确定性离散事件系统的模型为:

X(k)=U(k)GF*H

如果仍按文献[6]中的假定,令u_i(k)=k_ix(k-1),则系统的动态方程是:

X(k)=X(k-1)A

其中A=KGF*H, A in D ^N×N, 而K=

[k₁           e              …           e

e              k₂            …           e

…           …           …           …

 e             e             …           k_N]

制造系统的动态模型

设一个制造系统有m台机器,一批加工p个工作,则系统有m+p个资源.设系统有phi个加工活动, phi<=mp,则系统的模型为X(k)=U(k)GF*H.

现在把机器资源和工件资源分开来考虑,令: X(k)=(X_m(k)    X_p(k)),     U(k)=(U_m(k)           U_p(k)),把矩阵也相应地分块为:

GF*H=[D_m             D_mp；D_pm                             D_p]

那么X(k)=U(k)GF*H可以写为:

[X_m(k)     X_p(k)] = [U_m(k)      U_p(k)] [D_m              D_mp；D_pm                             D_p]

假设每台机器加工完第k-1批工件后即可投入加工第k批,则有:

U_m(k)=X_m(k-1)K_m

其中K_m称为机器反馈阵,且: K_m=

[k₁           e              …           e

e              k₂            …           e

…           …           …           …

 e             e             …           k_m]

这里k_i表示机器资源i两批之间的转换时间,令A_m=K_mD_m,B=D_pm,C_p=K_mD_mp,记Y_p(k)=X_p(k),则:

X_m(k)=X_m(k-1)_m⊕U_p(k)B_m

Y_p(k)=X_m(k-1)C_p⊕U_p(k)D_p

这与传统的线性系统类似,U_p(k)表示第k批工件可以进入系统的时间向量,它是系统的控制量,第二章将讨论DEDS的控制理论.

计时Petri网的极大代数描述

计时Petri网也称为事件图

一般地,一个计时Petri网,如果它的运行满足前面所提的四个条件,那么它可以用形如下面的极大代数方程描述:

Z(k)=Z(k-1) A⊕V(k)B

Y(k)=Z(k)C

其中变换Z(k)=[X(k)           X(k-1)], V(k)=[U(k)               U(k-1)].

串行生产线的建模略…

极大代数上矩阵的特征问题

在DEDS的稳态分析中有重要作用

定义1.5.1: A_n*n  XA=λX,   λ!=e, X!=空Phi, 则称λ为A的特征值,X为A的属于λ的特征向量,如果X的每个分量均不为e,则称X为A的有限特征向量.

定理1.5.1和1.5.2分别给出了特征值的必要条件和充分条件.一个实数λ是矩阵A的特征值,当且仅当λ是G(A)中某一回路的平均权重且该回路到任何平均权重比它的平均权重大的回路都没有路.(λ₁~λ_p如果有相等的,则称为重根)

特征向量

定义1.5.2: A_w1,A_w2,…,A_wn中的临界回路称为特征回路.

定义1.5.3: 设X以及X₁,X₂,…,X_k都是极大代数上的N维行向量,如果存在a₁,a₂,…,a_k in R (实数集并上-infinity),满足:

X=Σ_i=1^Na_iN_i=a₁X₁⊕…⊕a_kX_k,

则称X可由X₁,…,X_k线性表出.

定理1.5.3:

定理1.5.4:

矩阵的有限特征向量：

定理1.5.5: 矩阵A有有限的特征向量的充分必要条件是:

周期分析与动态方程的解

D上的动态系统: X(k)=X(k-1)A

A对应的有向图为G(A).当G(A)有几个连通分支时,系统可在各支中分别讨论,因此仅研究弱连通的G(A).不失一般性,本节设A是下面定理所示的标准形式.

定理1.2.2(化下三角阵): 设A_n×n, G(A)含w个强连通支,则存在置换阵P_n×n,使得

PAP^-1=[A₁              A₁₂          …             A_1w

Phi               A₂            …             A_2w

… …             …             …

Phi               Phi          …             A_w]

记

周期阵分析与动态方程的解

定义1.6.1 若λ!=-infinity,且存在正整数n₀使得:

A^d+n=λ^dAⁿ, for all n>n₀,

则称A是d阶λ周期阵.这里D中乘法为普通加法, λ^d就是普通的dλ.

分块周期阵分析与动态方程的解

定义1.6.2 若存在一个正整数n₀及Λ阵:  Λ=

[λ₁           λ₁₂          …             λ_1w

e              λ₂            …             λ_2w

…             …             …             …

e              e              …             λ_w]

使得:

{A^n+d}=λ^d_IJ{Aⁿ}_IJ, for all n>n₀, I, J

则称A为d阶Λ分块周期阵.

定理1.6.2: 在假设(H₂)之下

实现理论

实现的定义和Cayley-Hamilton定理:

定义1.7.1 设{G(k)}_k=1^infintiy是一个单位脉冲响应矩阵序列,G(k) in D^m*p,且: G(k)={g_ij(k)}

如果存在矩阵A in D^n*n,B in D^m*n,C^n*p满足:

BA^k-1C=G(k), k=1,2,…

则称{G(k)}_k=1^infintiy是能实现的,系统Σ: X(k)=X(k-1)A⊕U(k)B

Y(k)=X(k)C

称为{G(k)}_k=1^infintiy的一个实现, Σ也可记为(A,B,C),如果(A,B,C)在所有实现中A的阶数n是最低的,则称它为一个最小实现,维数为n.

极大代数中已经建立了特征方程的概念并且证明了Cayley-Hamilton定理成立,关于这方面的理论参考文献[9].这里直接引用某些结果.

定义1.7.2(线性相关): 设X₁,X₂,…,X_n是极大代数上的n个行向量,如果存在{1,2,…,n}的一个划分(N₁,N₂)以及不完全为e的a_i, a_i in R, i=1,2,…,n,使得:

Σ_{i in N1}a_iX_i=Σ_{i in N2}a_ix_i,

则称线性相关,否则称为线性无关.

引理1.7.1(Cayley-Hamilton定理)设A in D^n*n,它的特征方程为:

其中是的一个划分,那么有:

像传统线性系统理论一样,Cayley-Hamilton定理在实现理论中有重要作用,但与一般线性代数不同的是,极大代数中没有减法,{2,…,n}的不同划分(N₁,N₂),对应方程本质上是不同的,这是传统线性系统的实现理论难以推广到DEDS中的原因所在.

能实现的条件

定理1.7.1: 给定一个单位脉冲响应矩阵序列,如果它是能实现的,那么必存在{2,…,n}的一个划分(N₁,N₂),以及不完全为e的a_i, a_i in R, i=1,2,…,n,使得下式成立: