组合数学 第一节.ppt

组合数学 第一节.ppt 重集的排列与组合? 重集的概念? 重集的排列? 重集的组合 重集的概念?定义 元素可以重复出现的集合称为重集( multiset )。元素 a出现的次数叫做该元素的重数(repetition number) 。?重集 S表示为 S= {n 1·a 1 , n 2·a 2,…, n k·a k} 其中 a 1 ,a 2,…,a k为S中k个不同类型的元素, n i (n i是正整数或∞)(i= 1,2, …,k) 为 a i的重数。 重集的概念?重集 S的r排列 S的r个元素的有序摆放?重集 S的全排列或排列?重集 S的r组合 S中r个元素的无序选择 S的子重集( submultiset ) 重集的排列?定理 重集 S={ ∞·a 1, ∞·a 2,…, ∞·a k} 的r排列的个数为 k r?证明重集合 S的r排列形为: 第一位第二位第r位…从k个元个元素中任取一个从k个元素中任取一个从k个元素中任取一个 重集的排列?定理 重集 S= {n 1·a 1 , n 2·a 2,…, n k·a k},且 S的元素个数为 n=n 1+n 2+…+n k,则 S的全排列的个数为 P(n 1 , n 2,…, n k ) = !!! !nnnn k21? 重集的排列?证明重集 S的全排列形为: 先从这 n个位置中选出 n 1个位置放置 a 1,有 C(n,n 1)种结果; 再从剩下的 n-n 1个位置中选出 n 2个位置放置 a 2,有 C(n -n 1 ,n 2)种结果; 类似地, 依次选出位置放置 a 1 ,a 2,…,a k ????????个 n 重集的排列乘法原则,重集 S的全排列的个数为 C(n , n 1 )C(n -n 1 , n 2)… C(n -n 1-n 2-…-n k-1 ,n k ) == P(n 1 , n 2,…, n k ) !!! !nnnn k21? 重集的排列?例 某停车场有 6个入口处,每个入口处每次只能通过一辆汽车。有9辆汽车要开进停车场,试问有多少种入场方案? 重集的排列?解设9辆车分别标号为 1,2, …,9 则汽车的入场方案一一对应重集 S= {1· 1,1 · 2,…,1· 9,5 ·◇}的全排列排列 12 ◇3◇ 456 ◇◇◇ 789 排列◇ 12 ◇3◇◇ 456789 ◇故入场方案数为 P(14,1,1,1,1,1,1,1,1,1,5) = 726485760 重集的排列?例 求关于 x 1 , x 2 , x 3 , x 4的方程 x 1+x 2+x 3+x 4= 15 的非负整数解的个数