初中奥数竞赛培优专题讲座：专题二十六 组合计数（PDF版）

十六、组合计数 二十六、组合计数 [竞赛要点] 组合问题经常涉及到计数,计算具有某种性质的事物的数量、多少等等.计数就是 数数,它是组合数学的基本内容之一,也是数学竞赛中经常涉及的问题 [方法述要] 解决这类问题的方法大都是特殊的、技巧性的方法常用的方法有极端性原理、构 造法、枚举法、抽屉原理、整数性质、染色对应等等.用这些方法时,不能直接照搬,要认 真分析问题,找出问题的本质,才能有效地解决问题 初 1.枚举法:把符合要求的安排一一列举出来,既不重复,又无遗漏,从而得到所求安 数排的总数。枚举法是最原始最基本最简单的计数方法 学 2.加法原理和乘法原理: 竞 赛 加法原理:如果完成一件工作有n类方法,在第一类方法中有m1种方法,在第 培类方法中有m2种方法,…,在第n类方法中有mn种方法,那么,完成这件工作共有: 数N=m+m2+…+mn种方法 程 乘法原理:如果完成一件工作,需要分成n个步骤,完成第一步有m1种方法,完成 专第二步有m2种方法,…完成第n步有mn种方法,那么,完成这件工作共有:N=m1 题 讲 an3 mn种方法 座 运用加法原理的关键在于恰当地进行分类,使所分类别不重复不遗漏;运用乘法原 理的关键在于分步骤,要正确地设计分步的程序,使每步之间既互相联系,又彼此独立 3配对法(一一对应法):如果能将符合条件A的所有安排与符合条件B的所有安 排配成对,形成一一对应关系,则符合条件A的安排与符合条件B的安排数相等 配对法是计数问题中技巧性较强的常用方法,它可以将较难计数的问题转化为较 容易的计数问题. 领[赛题精析] 例1书架上有不同的中文书20本,不同的英文书10本,现从书架上取书,试问 1)取出一本书,有多少种不同的取法? (2)取出中文书和英文书各一本,有多少种不同的取法? 二十大、组合计数 解(1)这个问题应该用加法原理,因为从书架上取书有两类办法:第一类办法取 中文书,可以从20本书中任选一本,有20种方法;第二类办法取英文书,可以从10本 书中任选一本,有10种方法.所以不同的取书方法总共有:N=20+10=30(种) (2)这与上一个问题不同,应该用乘法原理取出中文书和英文书各一本这件事情, 可以分为下面两个步骤完成:第一步取一本中文书,有20种方法;第二步取一本英文 书,有10种方法所以由乘法原理,20本中文书取遍后共有:N=20×1