离散数学中的排列.pptx

排列 ; 研究排列问题的主要目的是求出根据已知的条件所能作出的不同排列的种数. 排列按照元素的排列方式可分为三种排列：1.线排列；2.圆排列；3.重排列. 一、线排列 定义1.1 设 是具有 个元素的集合， 是正整数. 从这 个 不同的元素中取 个按照一定的次序排列起来 ，称为集合 的 -排列. 其排列数记为 . 换言之， 的 -排列为 的 有序子集. 另外，为了 处理问题的方便，我们定义 例如，集合 ，则集合 有6个2-排列： 和 6个3-排列： ，故有 . 定理1.1 对于正整数 ，有 (1.3) 证明：在构造集合 的 -排列时，可以从集合 的 个元素 中 任选一个元素作为排列的第一项，这可以有 种选法. 当第一项选定后，又可以 从剩下的 个元素中任选一个元素作为排列的第二项，这又有 种选法. 照此下去，只要选定了前 项，则就有 种选法来选择排列的第 项. 由乘法法则，这 个项可以有 种选法. 故有 ;证毕. 注意，当 时，则称 的 -排列为全排列，于是由公式(1.3)有 推论1 当 时，有 (1.4) 证明：在集合 的 个元素中，任何一个元素都可以排在它的 -排列的首 位，故首元有 种取法. 当首元取定后，其他位置上的元正好是从 的另 个 元素中取 个的排列，因此有 种取法. 由乘法规则知有 证毕. 推论2 当 时，有 (1.5) 证明：当 时，把集合 的 -排列分为两大类：一类含有 中的某固定 元，比如是 ；另一类不含 . 如果先从 中选取 个元进行排列， 共有 个这样的排列. 对于每一个上述排列，可将 放入而得到 第一类排列. 由于对任一上述排列， 都有 种放入方法，因此第一类排列;共有 个，再由加法法则有 证毕. [例1] 由数字1,2,3,4,5,6可以构成多少个数字互不相同的四位数. 解：由于所有的四位数字互不相同，故一个四位数就是集合 的一个4-排列，因而符合题目要求的四位数个数是 [例2] 将具有9个字母的单词FRAGMENTS进行排列，要求字母A总是紧跟在字 母R的右边，问有多少种这样的排法？ 解：由于A总在R的右边，故这样的排列可以看成是具有8个元素的集合 的一个全排列，其个数为 [例3] 5面不同颜色的旗帜，20种不同的盆花，排成两端是两面旗帜，中间 放3盆花的形式，试问有多少种不同的方案数？ 解：5面旗取2面的排列数为 20盆花取3盆的排列数为 根据乘法法则，共有的方案数为 ; [例4] 求2000到7000间的偶数中，由不同数字组成的4位数的个数. 解：设这4位数为 ， 由于偶数，故 只能取0,2,4,6,8五个数字. 限制在2000到7000之间的数，故 只能取2,3,4,5,6五位数字. 分别讨论 如下： (1) 当 取2,4或6时， 只能有4种选择，而 则只能从余下的8位数字取 2个进行排列，故符合条件的数，根据乘法法则有 个 (2) 若 不取2,4,6，则 有5种选择， 为余下的8位数字取2个进行排列，故有符合条件的偶数个数为