组合数学初步

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数

生成函数:

幻方: