组合数学算法(二).ppt

二、组合与排列不同,组合是研究无次序的选取问题。定义:从 n个不同元素中无次序地选取 k个,叫做从 n个元素中选 k个的一个组合。记或其中 bination 的第一个字母, 而是 Andreas Von Ettingelausen(1796 — 1876) 发明的排列与组合的关系: ∴(1) 由( 1)可推出组合数的两个基本恒等式: (i) (ii) 另外,还约定: 当 k>n 及 k<0 时,都有,, knC????????k n knC?????????? k!CPCP kn kk kn kn??? k)! (n k! n! k! PC kn kn??? kn ??k1n 1kn ????0C kn? 0P kn? 1CC nn 0n??例 1 印度人早已了解组合规律,大约在公元前六世纪的一本书就记载了如下问题: “甜、酸、咸、辣、苦、涩六味可以调出多少种味道? ”书上所附答案是: “六种单味,十五种双味,二十种三味,十五种四味,六种五味,一种六味。”这就是组合数例 2 公元 628 年写的一本书中还有这样一道题: “一位有经验的建筑师为国王建造一座雄伟的宫殿,这座宫殿有八个门,每次开一个门,或二,三, …,共有多少种不同的开门方式? ”答: 255 种 66 56 46 36 26 16C,C,C,C,C,C C 88 28 18?????*例 3 在一平面直角坐标系中考虑格点( x,y),其中 x,y? Z 满足 1≤x≤ 12 ,1≤y≤ 12 。将这 144 个格点分别染成红、白、蓝三色。证明:存在一个长方形,它的边平行于坐标轴,它的顶点具有相同的颜色。证:首先这三种颜色的点中,至少有一种不少于 144/3=48 个,不妨设为红色点。设这些红点中,纵坐标 y=j 的点有 m j个( 1≤j≤ 12 ),则。又由 y=j 的红点连得条不同的线段。于是知由这些红点至少可以连得应用二次平均与算术平均不等式得(条)不同的平行于 x轴的线段。这些线段在 x轴上投影均落在 1≤x≤ 12 中。但该区间中,由坐标为整数的点所连成的线段一共只有 = ? x12x11=66 条。由此可知,上述平行于 x 轴的线段的投影中必有一些相互重合,而投影重合的两线段的四个端点恰构成一个长方形的点。它们都是红色的,且长方形的边分别平行于二个坐标轴。 48 m 121j j??? 1) (m m2 1C jj 2m j?? 72 3 48 2 1 1m 12 1m2 1mm 12 12 1 mm2 1C 121j j 121j j 121j j 2 121j j 121j j 121j 2j 121j 2m j????????????????????????????????????????????????????????????????2 12C *例 4 在平面上给定 5个点,已知连结这些点的直线互不平行,互不垂直, 也不重合。通过每一个点向其余 4点的各条连线作垂线,这些垂线的交点最多有几个?(不包括原来的 5个点) 解:由给定的 5个点可两两连成 =10 条线段,由其中每 4点可两两连成 =6 条直线。因此,由每个点都应引出 6条垂线,一共有 5x6=30 条,如果这些垂线中每两条都相交,则一共可交得 =435 个交点。但这些垂线是分别向 10 条连线引出的,每一条连线上都有 3条垂线(5点中除自连的两点外还剩 3点,可向这条连线引垂线) ,这三条垂线互相平行没有交点, 因此要减去 10x3=30 条。又由于由给定的 5个点可构成 =10 个三角形, 上述 30 条垂线恰好是这些三角形的全部高,每个三角形中的三条高线相交于同一点,因而还要减去 10x3-10=20 。最后,由于经过每个原来的点的垂线都有 6条,所以还要减去 =75 。因此得这些垂线的交点最多只能有 435-30-20-75=310 个。 435 :是 5个点中每点可引 6条垂线( )共 30 条垂线,其中每二条交于一点共 30 :原来 5点两两连接共 10 条线,每条线上有 3条平行垂线没有交点共 10x3=30 20 :每个三角形中三条高交于一点,不是一般的 3点,所以要(多出来的) 75 :原来从每点向其他 4点所成连线的垂线交于该点不算在内,故 25C 24C 2 30C 35C 26 5C 24C 435 C 2 30? 20 10 C 10 23??? 75 C5 26??例 5 有两位高一学生参加高二年级的象棋比赛,比赛时每二个棋手都要对弈一局,胜者得 1分,败者得 0分,平局每人?分。现知两位高一学生共得 8分,