组合数学PPT第一章排列与组合-.pptx

第1章排列与组合;组合数学;1.1基本计数法则;1.1基本计数法则;例1.3 求比10000小的正整数中含有数字1的数的个数。

解 比10000小的正整数可以写为

的形式。

共有104-1=9999个

其中不含1的正整数有 94-1=6560个所求正整数的个数为 9999-6560=3439

个。;· 例1.4 求长度为n的二元码的数目。解 长度为n的二元码的形式为

由乘法法则，长度为n的二元码的数目为;的数目。可能取值的个数为;1.1基本计数法则;· 例1.9 求从a,b,c,d,e这5个字母中取6个所组成的字符个数。要求(1)第1个和第6个字符必为子音字符；(2)一字符串必有两个母音字符，且两个母音字母不相邻；

(3) 相邻的两个子音字符必不相同。

解 符合要求的字符串有以下几种模式：;·例设某地的街道把城市分割成矩形方格，每个方格叫做它的块。某甲从家中出发上班，向东要走过m块，向北要走过n块，问某甲上班的路径有多少;· 定理（Cayley）n个有标号的顶点的树的数目等;定义：从n个不同的元素中，取出r个按次序排成一列，称为从这n个元素中取r个的一个排列，其排列数记为 .

由定义显然有(1)

(2);· 例1.13 由5种颜色的星状物，20种不同的花排成如下的图案：两边是星状物，中间是3朵花，问共有多少种这样的图案？

解 图案的形状为

★〇〇〇★共有

种图案。; 例1.14A单位有7位代表，B单位有3位代表，排在一列合影，要求B单位的人排在一起，问有多少种不同的排列方案？

解B单位的某一排列作为一个元素参加单位A进行排列，可得种排列。

B单位的3人共有个排列，故共有排列方案。; 例1.15 若例1.14中A单位的两人排在两端，B单位的3人不能相邻，问有多少种不同的排列方案？

解 共有 种方案。; 例1.16 求20000到70000之间的偶数中由不同的数字所组成的5位数的个数。

解 设所求的数的形式为其中

若 ，这时e有4种选择，有

若 ，这时e有5种选择，有共有 个。;abcd,dabc,cdab,bcda;· 例1.195颗红色的珠子，3颗蓝色的珠子装在圆板的四周，试问有多少种排列方案？若蓝色的珠子不相邻又有多少种排列方案？蓝色珠子在一起又如何？;· 例1.205对夫妻出席一宴会，围一圆桌坐下，问有几种方案？若要求每对夫妻相邻又有多少种方案？

解 (1) 种方案；

(2) 种方案。;· 定义 从n个不同的元素中，取出r个而不考虑其次序，称为从这n个元素中取r个组合，其组合数记为 。;· 例1.21从1～300之间任取3个不同的数，使得这3个数和正好被3除尽，问共有几种方案？

解 将这300个数按照其被3除所得的余数分为三组：A={1,4,…,298}，B={2,5,…,299}，C={3,6,…,300}

① 三个数取自集合A：有C(100,3)种方案；

② 三个数取自集合B：有C(100,3)种方案；

③ 三个数取自集合C：有C(100,3)种方案；

④ 三个数分别取自集合A、B、C：有1003种方案；所求的方案数为：3C(100,3)+1003=1485100; 例1.22 甲和乙两单位共11个成员，其中甲单位7人乙单位4人，拟从中组成一个5人小组；

若要求必须包含乙单位2人；

若要求至少包含乙单位2人；

若要求乙单位某一人与甲单位某一人不能同时在这个小组；

试分别求各有多少种方案。解 (1)

(2)

(3); 例1.23假定有8位成员，两两配对分成4组，问有多少种分配方案？

解 方法1：

将8位成员排列，共有8!个排列，每个排列两两划分，分成4组，其重复数为24.4!，所求分配方案数为;· 方法2：; 例1.24某广场有6个入口处，每个入口处每次只能通过一辆汽车，有9辆汽车要开进广场，问有多少种入场方案？

解 方法1：

9辆汽车和5个标志的一个排列可表示一种入场方案，其重复数为5!，所求方案数为;· 方法2：

在9辆汽车和5个标志共14个位置中，首先选择5个作为标志的位置，这有 种选择，对每一种选择，将9辆汽车依次填入剩余的位置，这有

种填入方式，故所求方案数为;· 例1.25 求5位数中至少出现一个6，而被3整除的数的个数。

正整数n能够被3整除的的充要条件是n的各个数字之和能够被3整除。

设

因为 ，所以;5位数 共有90000个被3整除的有30000个

在这30000个数中不包含6的数有

个

所求个数为

30000-17496=12504;· 定理 在n!中，质数p的最高幂;· 例6．求1000!的末尾有几个0

解 1000!的末尾所含0的个数为1000!的因子分解中2和5的幂的最小者

1000!因子分解中5的幂为：;习题;允许重复的排列;定