组合数学引论

+!+Р组合数学引论! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !Р语#法语=门外语课"设# 与$ 都能教英语#日语!% 能教英语#德语#法语!& 能教Р德语"问能否设计一种工作安排方案!使得每位教员在下学期教且仅教一门外Р语课0Р 在平面上将每位教员和每门外语课分别用一个点来表示!若教员' 能教外语Р课(!则在相应的两点间连一条边"如此构造出图6!将原问题变为在图6中找出=Р条边!使这=条边两两之间无公共端点"Р 图$Р 从图6可以看出!有两种不同的工作安排方案"# 教英语#$教日语#%教法语#Р& 教德语!或者# 教日语#$ 教英语#% 教法语#& 教德语"但如果#!$!%!& 能教Р的语种分别为英语与日语#德语与法语#英语#日语!就不存在一种每位教员教且仅Р教一门外语课的工作安排"Р 从上例可以看出!满足一定条件的安排并不总是存在的!这就给我们提出了这Р样一个问题"在什么样的条件下这种安排是存在的0这也是安排的存在性所研究的Р中心问题"Р 3B 安排的枚举和分类"计数问题#Р 如果所要求的安排存在!则可能有多种不同的安排"这又经常给人们提出这样Р的问题"有多少种可能的安排方案0如何对安排的方案进行分类0Р 例如!对正三角形的<个顶点进行红#蓝两色着色!如图3所示!共有3< )5种Р方案"Р 在图3中!如果我们将经旋转后互相重合的两种方案看成是同类的!则图中的Р每一列就是一类着色方案!共有=类着色方案"Р 对于一般的计数问题!我们需要给出两个分配方案是否属于同一类的数学模Р型!表明判定同类分配方案的数学方法!进而给出计算分配方案分类的计算公式"Р 虽然任何组合问题中都包含存在性问题和计数问题!但通常来说!若一组合问Р题的存在性问题需作大量研究的话!则其计数问题的难度是难以想象的"然而!若Р +"+