西安交通大学组合数学期末重点

组合数学期末重点第一章： 7 11 14 25 267. n 个男 n 个女排成一男女相间的队伍，试问有多少种不同的方案？若围成一圆桌坐下，又有多少种不同的方案？[解].(1)若第 1 个位置是男，有n n (n-1) (n-1)3 3 2 2 1 1=(n!) 2 种排法；若第 1 个位置是女，也有(n!) 2 种排法；故 n 个男 n 个女排成一男女相间的队伍，有2(n!) 2 种不同的排法。因为若不记座位的差别，只记人与人之间的相对位置的变化，则每一种坐法可产生2n个男女相间的排列，从而坐法为22])!1[()!1(!2)!(2nnnnnn种，若不记顺、逆时针则有坐法22])!1[(21)!1(!2122)!(2nnnnnn种。(2)若第 1 个座位坐男， 有 n 个可能， 则第 2 个坐女为 n 个可能， ⋯⋯， 根据乘法原理，故有 n n (n-1) (n-1)3 3 2 2 1 1=(n!) 2 种方案。同理，第1 个座位坐女，也有(n!) 2 种方案。故有 2(n!) 2 种方案。11.凸 10 边形的任意三条对角线不共点。试求这凸10 边形的对角线交于多少个点？又把所有的对角线分割成多少段？[解].(参见柯召《组合数学》上册。P34 例 1.6.1)(1)从一个顶点可引出7 条线和第一条（从右到左）交的有1 7，和第二条交的有2 6 条故 和 一 个 顶 点 引 出 的7 条 线 相 交 的 点 为 ：1 7+2 6+3 5+4 4+5 3+6 2+7 1=84故 和 从10点 引 出 的 对 角 线 交 的 点 有 个84 10=840，但每个点重复了四次（因为每个点在两条线上， 而每条线有两个端点） 。故凸 10 边形（这样的）对角线交于2104840个点。故也可为210123478910410C(2)从上。一个点引出的7 条线中第一条线上有7 个点，故将该线段分成8 段；第二条线上有 12 个点，故将该线段分成13 段，故从一个点出发的7 条线上的段数为第 11 题图 1第 11 题图 28+13+16+17+16+13+8=91故有 10 个点。故总的段数可为91 10=910。但有重复，重复数为2（因为每条线有两个端点）。故总的段数为4552910。14.从 26 个英文字母中取出6 个字母组成一字, 若其中有 2 或 3 个母音 . 问分别可构成多少个字( 不允许重复 )? [解].英语中有 6 个元音字母a,e.i,(y),o,u,其余 20 个是辅音。(1)若取出 6 个字母组成一字, 其中有 2 个元音 , 可构成1234561256123417181920!626420=52 326 000(2)若有三个元音 , 可构成123456123456123181920!636320=16 416 000；另一种解法认为有5 个元音，其余21 个是...