排列数和组合数

《组合数学》 第一章 组合数学基础

第1章 组合数学基础

1. 排列组合的基本计数问题 2. 多项式系数的计算及其组合意义 3. 排列组合算法 1.1 绪 论

（一） 背景

起源：数学游戏

幻方问题：给定自然数1, 2, …, n2，将其排列成n阶方阵，要求每

行、每列和每条对角线上n个数字之和都相等。这样的n阶方阵称为n阶幻方。每一行（或列、或对角线）之和称为幻方的和（简称幻和）。

例：3阶幻方，幻和＝(1＋2＋3＋?＋9)/3＝15。

关心的问题 存在性问题：即n阶幻方是否存在？

计数问题：如果存在，对某个确定的n，这样的幻方有多少种？ 构造问题：即枚举问题，亦即如何构造n阶幻方。

8 3 4 1 5 9 6 7 2 2 9 4 7 5 3 6 1 8 奇数阶幻方的生成方法：

一坐上行正中央，依次斜填切莫忘， 上边出格往下填，右边出格往左填， 右上有数往下填，右上出格往下填。

例：将2，4，6，8，10，12，14，16，18填入下列幻方：

1/51 姜建国

《组合数学》 第一章 组合数学基础

《组合数学》 第一章 组合数学基础

第1章 组合数学基础

1. 排列组合的基本计数问题 2. 多项式系数的计算及其组合意义 3. 排列组合算法 1.1 绪 论

（一） 背景

起源：数学游戏

幻方问题：给定自然数1, 2, …, n2，将其排列成n阶方阵，要求每

行、每列和每条对角线上n个数字之和都相等。这样的n阶方阵称为n阶幻方。每一行（或列、或对角线）之和称为幻方的和（简称幻和）。

例：3阶幻方，幻和＝(1＋2＋3＋?＋9)/3＝15。

关心的问题 存在性问题：即n阶幻方是否存在？

计数问题：如果存在，对某个确定的n，这样的幻方有多少种？ 构造问题：即枚举问题，亦即如何构造n阶幻方。

8 3 4 1 5 9 6 7 2 2 9 4 7 5 3 6 1 8 奇数阶幻方的生成方法：

一坐上行正中央，依次斜填切莫忘， 上边出格往下填，右边出格往左填， 右上有数往下填，右上出格往下填。

例：将2，4，6，8，10，12，14，16，18填入下列幻方：

1/51 姜建国

《组合数学》 第一章 组合数学基础

? 排列问题题型分类：

1.信号问题 2.数字问题 3.坐法问题 4.照相问题 5.排队问题 ? 组合问题题型分类：

1.几何计数问题

2.加乘算式问题 3.比赛问题 4.选法问题 ? 常用解题方法和技巧 1. 优先排列法 2. 总体淘汰法

3. 合理分类和准确分步 4. 相邻问题用捆绑法 5. 不相邻问题用插空法 6. 顺序问题用“除法” 7. 分排问题用直接法 8. 试验法 9. 探索法 10. 消序法 11. 住店法 12. 对应法

13. 去头去尾法 14. 树形图法 15. 类推法

16. 几何计数法 17. 标数法 18. 对称法

分类相加，分步组合，有序排列，无序组合

? 基础知识（数学概率方面的基本原理）

一. 加法原理：做一件事情，完成它有N类办法，

在第一类办法中有M1中不同的方法， 在第二类办法中有M2中不同的方法，……， 在第N类办法中有Mn种不同的方法，

那么完成这件事情共有M1+M2+……+Mn种不同的方法。

二. 乘法原理：如果完成某项任务，可分为k个步骤，

完成第一步有

小学奥数排列组合的内容,属于小学奥数中计数这个大模块

排列组合复习

全力以赴

GEC Program

赢在精锐

小学奥数排列组合的内容,属于小学奥数中计数这个大模块

主要内容乘法原理加法原理 排列 组合 例题讲解 习题2010 06 18

全力以赴

赢在精锐

小学奥数排列组合的内容,属于小学奥数中计数这个大模块

基本计数原理 1. 乘法原理

设完成一件事有m个步骤，则完成这件事共有 第二个步骤有n2种方法, …; n1 n2 nm 第m个步骤有nm种方法, 种不同的方法 . 必须通过每一步骤, 才算完成这件事，全力以赴 赢在精锐

第一个步骤有n1种方法，

小学奥数排列组合的内容,属于小学奥数中计数这个大模块

例如，若一个男人有三顶帽子和两 件背心，问他可以有多少种打扮？

可以有 3 2 种打扮全力以赴 赢在精锐

小学奥数排列组合的内容,属于小学奥数中计数这个大模块

基本计数原理

2. 加法原理设完成一件事有m种方式， 第一种方式有n1种方法， 第二种方式有n2种方法, 则完成这件事总共 …; 有n1 + n2 + … + nm 第m种方式有nm种方法, 种方法 . 无论通过哪种方法都可以 完成这件事，全力以赴 赢在精锐

小学奥数排列组合的内容,属于小学奥数中计数

第三节 排列与组合问题

【目录】

题型1 排列应用题中的数字问题 题型2 排列应用题中的排队问题 题型3 排列应用题中的其它问题

题型4 排列数、组合数的计算公式及组合数的性质 题型5 组合应用题中的选举及抽样问题 题型6 组合应用题中的几何问题 题型7 组合应用题中的分配问题 题型8 排列、组合的综合应用题

三、解答题

题型1 排列应用题中的数字问题

1．用数字0、1、2、3、4、5组成无重复数字的数：

（1）可以组成多少个六位数？ （2）可以组成多少个四位奇数？ （3）可以组成至少有一个偶数数字的三位数多少个？

（4）可以组成多少个能被3整除的四位数？ （5）可以组成多少个大于324105的六位数？

1解：（1）从特殊元素0入手：0不能排在十万位，0有A5种排法，剩下的5个数字可排在5个数位下，515有A5种，故可组成A5A5?600个六位数。

1515从特殊位置十万位入手：有A5种排法，剩下的五个位置有A5种，故可组成A5A5?600个六位数。65六个数字可组成A6个“六位数”（其中包括0在十万位的情形），而0在最高位上的“六位数”应扣除有A565个，故共有A6?A5?600个

第五章 排列与组合 （1）

【考点解读】

考点 内容解读 1、.理解分类计重庆市4年高职考试统计（分值） 常考题型 2012 2013 2014 2015 数原理和分步计第一节 数原理，能区分 计数的基本原它们的使用条件理 和方法 2、能运用原理分析解决一些简单的实际问题。 1、.理解排列、组2 2 2 2 计算题 合的概念，能正确识别排列、组合问题 .2掌握排列、组第二节 合数的计算公排列、组合的概式，了解组合数念与计算 的两个性质 3.能用排列、组合的知识处理一些简单的应用题 1、能进一步正确5 7 7 7 选择题 识别排列问题、组合问题 第三节 2、.能用排列组排列、组合的应合的知识解决一用 些简单的有限制条件的应用题 掌握一些常用方法。 【分析解读】 排列与组合在近几年高职考试中以选择题或填空题为主，主要考查： 1、排列、组合的理解，排列问题、组合问题的正确识别； 2、排列数、组合数公式的计算，了解组合数的两个性质

3、用计数原理和排列组合的知识处理一些简单的有限制条件的应用题

第一节 计数的原理 【知识要点】 一、计数原理：

1、分类计数原理（

1．分类计数原理: 完成一件事，有n类办法，在第1类办法中有m1种不同的方法，在第2类办法中有m2种不同的方法， ，在第n类办法中有mn种不同的方法，那么完成这件事共有N= n1+n2+n3+ +nM种不同的方法．

2.分步计数原理:完成一件事,需要分成n个步骤,做第一步有m1种不同的方法,做第二步有m2种不同的方法, ,做第n步有mn种不同的方法，那么完成这件事共有N=n1·n2·n3· nM 种不同的方法．

注：分类计数原理和分步计数原理是排列组合的基础和核心，既可用来推导排列数、组合数公式，也可用来直接解题。它们的共同点都是把一个事件分成若干个分事件来进行计算。只不过利用分类计算原理时，每一种方法都独立完成事件；如需连续若干步才能完成的则是分步。利用分类计数原理，重在分“类”，类与类之间具有独立性和并列性；利用分步计数原理，重在分步；步与步之间具有相依性和连续性.比较复杂的问题，常先分类再分步。

3. 排列的定义：从n个不同的元素中任取m(m≤n)个元素，按照一定顺序排成一列，叫做从n个不同元素中取出m个元．．．．．．素的一个排列.

排列数的定义: 从n个不同元素中取出m(m≤n)个元素排成一列，称为从n个不

ACM暑期集训 组合数学（1） 数论

1 约数和倍数

设 a，b为整数，a≠0.

若有一整数c，使得 b = ac，则称 a是b的因数 或称a是b的约数 称b为是a的倍数

并称a整除b，记为a|b

整数的整除性有下列基本性质： ① 1|a ② a|0 ③ a|a

④ 若a|b且b|c，则a|c.

⑤ 若a|b，则对任意整数m，有am|bm ⑥ 若ac|bc且c≠0，则a|b

⑦ 若a|b且a|c，有 a|(b+c) 整数的表示法：

带余形式 b=aq+r 0≤r<|a|

十进制表示形式 b?ann?1n10?an?110????a0

标准分解式 b?pa1aan1p22??pn 2的乘方与奇数之积式 b?2mt(t为奇数)

2 最大公约数和最小公倍数 最大公约数GCD(a,b)

若GCD(a,b)=1，称a与b互素。 最小公倍数LCM(a,b)

ab = GCD(a,b)×LCM(a,b)

辗转相除法（Euclid算法）

如果m除以n的商是q，余数是r，即 m=nq+r，则 GCD(m,n)=GCD(n,r) int gcd(int a,int b) int GCD(in

第十一讲 Burnside 引理与 Polya 定理

§1 (置换群基本概念) (本页） §2 (Burnside 引理与循环指标) §3 (Burnside 引理的应用) §4 (Polya 定理及其应用)

Redfield-Polya 定理是组合数学理论中最重要的定理之一．自从 1927 年 Redfield 首次运用 group reduction function 概念，现在称之为群的循环指标（circle index of a group），至今 60 多年来，他在许多实际计数问题上得到了广泛的应用，它以置换群为理论基础，与生成函数有机地结合在一起，揭示了一类具有组合意义的计数的规律性．

抽象地说在一集合内，定义了一个等价关系，人们往往关心由这个等价关系所决定的等价类的数目，Refield-Polya 理论就是为解决这类问题而发展起来的复杂计数理论．

为了帮助读者理解，本章例举了较多的实例． §1 置换群的基本概念

设有限集合 换 是从 到自身上的

，集合中的元素称为“点”．集合 上的一个置对应的映射：

设 是集合 上的另一个置换，置换 与 的乘积定义为复合映射：

例 1 设 上的二个置换：

求乘积

第二章作业答案

7. 证明，对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。

证明 用100分别除这52个整数，得到的余数必为0, 1,?, 99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，?，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a和b。若a和b被100除余数相同，则a?b能被100整除。若a和b被100除余数之和是100，则a?b能被100整除。

11. 一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。 证明 设从第一天到第i天她共学习了ai小时。因为她每天至少学习1小时，所以

a1,a2,?,a37和a1?13,a2?13,?,a37?13都是严格单调递增序列。因为总的学习时间

不超过

60

小时，所以a37?60，a37?13?73。a1,a2,?,a37,

a1?13,a2?13,?,a37?