第3讲排列与组合.PDF

应用组合数学 第3讲排列与组合 张坤龙 zhangkl@tju.edu.cn 目录 • 排列与组合 • 二项式系数 • 格路 • 应用举例 排列与组合 • 排列 – 排列，可重复排列，圆排列 • 组合 – 组合，可重复组合 排列 [定义1] 从n个不同的元素中取r个不重复的元素按 次序排成一列，称为从n个元素中取r个元素的一 个排列。当r=n时，称为全排列。 n! [定理1] P (n, r) P n r n r ( − )! [例1] A单位有7位代表，B单位有3位代表，排成 一列，要求B单位的3个人排在一起，问有多少种 不同的排列方案？ 可重复排列 [定理2] 从n个不同的元素中取r个允许重复的元素按 次序排成一列，排列的个数为nr [例2] 若|A|=m，|B|=n，则从A到B上的函数f :A→B 的个数为nm个。 圆排列 [定理3] 从n个不同的元素中，取r个不重复的元素沿 一圆周排列，排列的个数为P(n,r)/r个 [例3] 5对夫妇出席一宴会，围一桌坐下，试问有几 种不同的方案？若要求每对夫妻相邻又有多少种 不同的方案？ 组合 [定义2] 从n个不同元素中取r个不重复的元素组成 一个子集，而不考虑其元素的顺序，称为从n个 中取r个的一个组合。 n   n! [定理4] ( , ) n   C n r C r   r (n −r)!r!   [例4] 某车站有6个入口处，每个入口处每次只能 进一人，一组9个人进站的方案有多少？ 组合（续） [解法1] 进站方案可表示为12300450607089，其中1-9表示 人，0表示入口，注意6个入口只用5个0 。任意进站方案可 表示成上面14个元素的一个排列。对0标号，可产生5!个 14个元素的全排列。若设x为所求方案，则x ·5!=14!，因 此可得：x=14!/5!=726485760 [解法2] 在14个元素的排列中先确定入口的位置，有C(14,5) 种选择，再确定人的位置，有9 ！种选择。故得C(14,5)·9! [解法3] 把全部选择分解成若干步，使每步宜于计算。1有6 种选择；2除可有1的所有选择外，还可（也必须）选择当 与1同一入口时在1的前面还是后面，故2有7种选择；3的 选择方法同2，故共有8种。以此类推，9有14种选择。故 所求方案数为6X7X8X9X11X12X13X14 可重复组合 [定理5] 从n个不同的元素中取r个进行组合，若允许 重复，则组合数为C(n+r-1,r) [证明一] 一一对应，假设a =a a =…=a ，则