初中奥数讲义 组合计数技巧初中奥数讲义 组合计数技巧.pdf

组合计数技巧 计数是组合数学的主要课题，一般来说，组合计数方法是运用排列、组合的 基本公式为基础，依据加法原理、乘法原理，容斥原理，或建立一一对应关系， 递推关系等，以求出精确的计数式. 组合计数问题是组合数学的基础和重要板 块，所谓 “得组合者得天下”，掌握组合计数技巧的重要性不言而喻. 因此，学 习组合数学，掌握组合计数技巧对于竞赛获奖以及数学能力的培养都有着十分重 要的意义. 组合计数技巧多种多样，包括组合原理、枚举法、一一对应方法、生成函数 法、递归法等等，本讲重点讲解加法、乘法原理,枚举方法以及一一对应方法. 一、利用加法、乘法原理以及枚举方法计数 枚举法：就是把所要求计数的所有对象一一列举出来，最后计算总数的方法. 运用枚举法进行列举时，必须注意无一重复，也无一遗漏. 加法原理：完成一件事的方法可分成n个互不相交的类，在第1类到第n类 n 分别有m,m ,...,m 种方法，则总共完成这件事有m m m ...m 种方法. 1 2 n i 1 2 n i1 应用加法原理的关键在于通过适当的分类，使得每一类都相对易于计数. 乘法原理：完成一件事的方法有n 个步骤，在第 1步到第n 步分别有 n m,m ,...,m 种方法，则总共完成这件事有m mm ...m 种方法. 1 2 n i 1 2 n i1 应用乘法原理的关键在于通过适当的分步，使得每一步都相对易于计数. 1.1 10 例 （1）等腰三角形的三边均为正整数．它们周长不大于 ．这样不同的 三角形的种数为 （ ） A．8 B．9 C．10 D．1l （2）有两排座位，前排11个座位，后排12个座位，现安排2人就座，规 定前排中间的3个座位不能坐，并且这2人不左右相邻，那么不同排法的种数是 A.234 B．346 C. 350 D．363 【解析】 （1）C 设三边为x,y,z，则x+y+z≤10，由三边关系共有(1，1，1)，(1，2，2)， (1，3，3)，(1，4，4)，(2，2，2)，(2，2，3)，(2，3，3)，(2，4，4)，(3，3，3)，(3，3， 4)共10种. 2 A （2）B 限邻排列问题 前排中间的3个座位不能坐，有排法 ，其中相邻的分三类， 20 2 2 2 2 2 在前排的其中的4个座位有3 ；则符合条件的排法种数中 =346，故 A A 3A 3A 11A 2 20 2 2 2 选B （这是正难则反的思想，从总体中除去不符合要求的） 另解：分三类：①两人坐在前排，按要求有4·6+4·5=44种坐法．(4个在两侧和紧邻 中间的位置，4个普通位置) ②两人坐在后排，按要求有