2-5数学竞赛中的组合问题数学竞赛中的组合数学不是一个严格的概念，它离中学 教材最远，通常指中学代数、几何、算术（数论）之外的内 容（俗称杂题）.对中学生而言，这类问题的基本特点是不 需要专门的数学语言就可以表述明白，解决起来也没有固定 的程式（非常规），常需精巧的构思.从内容上可以归结为 两大类：组合计数问题，组合设计问题.（1） 组合计数问题这包括有限集合元素的计算、相应子集的计算、集合分 拆方法数的计算等，表现为数值计算、组合恒等式或组合不 等式的证明.知识基础是加法原理、乘法原理和排列组合公 式；常用的方法有：代数恒等变形、二项式定理、数学归纳 法、递推、组合分析、容斥原理等.（2） 组合设计问题其基本含义是，对有限集合A，按照性质卩来作出安排， 有时，只是证实具有性质卩的安排是否存在、或者验证作出 的安排是否具有性质P （称为存在性问题，又可分为肯定型、 否定型和探究型）；有时，则需把具体安排（或具体性质） 找出來（称为构造型问题）；进一步，还要找出较好的安排 （称为最优化问题）.值得注意的一个新趋势是组合与几何、数论的结合，产 生组合几何、组合数论，它们与集合分拆一起组成IMO试题 的三个热点，突出而鲜明的体现数学竞赛的“问题解决”特 征.这三方而之所以成为热点，从思维方式、解题技巧上分 析，是因为其更适宜数学尖子的脱颖而出，口常与现代数学 思想相联系；从技术层面上分析，述由于都能方便提供挑战 中学生的新颖题目.链接资料组合数学又称组合分析或组合学.研究将有限个元素安 排到适合(服从)某些限制条件的集合.有三个基本问题：(1) 组态问题，解决存在这种安排的条件，给出明确的 结论；(2 )组态存在时，确定其数目或将它们进行分类；(3) 研究安排的性质和结构，包括最优化问题.组合数学最早出现的是神话传说：大禹时代(公元前2200年)的神龟背上驮着的幻方，古代称为"九宫"，即4 9 23 5 78 1 6一般是将1,2,…,"2放到"X"格子中，使每行每列各数之和 相等，称为"阶幻方.还有缺角棋盘的覆盖问题、柯克曼1 5女生散步问题、欧拉3 6名军官问题都是著名的组合学例 子.现代科学技术中，又提出离散性问题及关系结构分析， 图论、信息论、编码、实验设计、线性规定划等领域也提了 一系列问题，促进了组合学的发展.一. W0中的组合题(智力题)1. 数量统计从 imo6_4, imo6_5 开始，A 20%2. 基本类型(1) 组合计数问题：① 问题类型有限集合元素的计算，子集的计算，集合分拆的计算② 解题方法：代数恒等变形二项式定理组合等式递推组合分析容斥原理数学归纳法.(2) 组合设计问题：对集合A,按照某种性质P来作出安排.① 问题类型存在性问题，构造性问题，最优化问题.② 解题方法：构造法、反证法抽屉原理染色方法递推方法更多的解题技巧见2-73. 发展特点以组合计数、组合设计为基础，与数论、几何交叉，形 成组合数论、组合几何、集合分拆三大热点.二、基础知识（与基本类型相一致）有7个定义、9条定理：定义1 从"个不同的元素中取出加个0"）,按照一定的 顺序排成一列,叫做从“个不同的元素中取出加个元素的一个 排列.相异元素排列数的计算公式为：定乂 2 从烈个彳、同的兀素中取出加个(m |B（3 ）若厂是一一映射（双射），贝lj|A| = |B|.2.主要类型（1） 排列、组合的知识.（2） 集合、影射的知识.（3） 抽屉原理.（4） 容斥原理.（5） 组合恒等式.三、例题讲解例1 （1）将10个苹果分给3个人，每人至少1个，问 有几种不同的分法？（10的有序分拆）（2）将10个苹果分成3堆，每堆至少1个，问有几种 不同的分法？ （10的无序分拆）解（1）设第/个人分得兀个苹果，则有X] + 兀2 +兀3 = 10（兀 n 1）1 + 1 +・・・+ 1 = 10对应9个加号取2个的取法，得C；=36.相当于10个苹果一字排开两手拿隔板往里一插，得一 种分法.(2) 10的3项分拆：每堆先放1个苹果，剩下的7个 苹果可以拆开放到3堆，也可以放到2堆，或全放到1堆， 故得10的3项分拆=7的3项分拆+7的2项分拆+7的1项分拆=4的3项分拆+4的2项分拆+4的1项分拆+3+1= 14-2+1+3+1 =8.一般地m的n项分拆= m-n的〃项分拆+加7的1项分拆+・・・ +加-斤的2项分拆+加-〃的1项分拆.数字小时可以列举10=1+1+8=1+2+7=1+3+6=1+4+5 =2+2+6=2+3+5=2+4+47123•4567；8910二宀11• • • •12it131415*;•* 项1111111111111：1二项.1122334 -45：566门7…三项112.3457:1012141619四项112・35：691115182327五项11 •:23571013182330六项1 •123「；5「711142026「七项;」• 丿・• •• 存，・•・・:•宀1.1• 2：357-111521L八项“■•■112.3.5.71113i九项• Y:*7• • J,• :•• h ■/• ・•・ • • • *• 9 •• • •• • • •A -• 9• •■ •• .•訂:•■ 01: 123■5-皿11十项•••112勺•・35；7十一项••1• — •123• 5十二项•・ ・• •• • ••• • • F••••.•• •■1123:.壬十三项：1 *• 々• ■• .• •*辺•：:.. .%・•・・..;•… •• • •• • R• ■• ■・ 1 ■1吐2 -十四项■• ••• ••1.1十五项1总计•-123571115223042(5677101135174例2 （1988,高中联赛，例2-104）甲乙两队各出7名队 员按事先安排好的顺序出场参加围棋擂台赛’双方先由1号 队员比赛，负者被淘汰，胜者再与负方2号队员比赛，依次 类推，直到有一方队员全被淘汰为止，另一方获胜利，形成 一种比赛过程，那么所有可能出现的比赛过程的种数有多 少？ （P. 205）解法1 A ‘ ^2 ‘ 4^ ‘ Ai,人9 “I ‘ B?, B3, B4, , B7 G4解法2设4胜兀场，甲胜等价于方程xi+x2+x3+x4 + x5+xf）+x1 =7 ,非负整数解的个数，令）"齐+1,方程X + 儿 + 儿 + 儿 + % + 儿 + >7 = 14，正整数解的个数1+1+1+1+1+1+1+1+1+1+1+1+1+1=14,从13个加号取6个的方法数G：种.同理，乙胜也有第种.得2=皤种.2 c侣邙=3432种.例2-1联欢晚会准备了2“个礼物，平分为两串公开巾。
