组合计数问题的基本方法--对应

组合计数问题的基本方法——对应(学生版)

一、例题分析

1. 在如图所示的8⨯6的网格中, 若一只小虫子每次只能向右或向上爬一格, 求这只小虫子从A 点爬到B 点的不同的路线数

.

2.(1)在如图所示的7⨯5的方格纸中, 一共有多少个长方形？

(2)在如图所示的7⨯5的方格纸中, 一共有多少个包含阴影部分的长方形？

3. 设凸n (n ≥4) 边形的任意三条对角线不相交于形内一点, 求凸n 边形对角线在形内的交点数.

4. 将三角形的各边n 等分, 过各分点作其余两边的平行线, 求在三角形内所形成的平行四边形的个数S .

5. 在圆周上有n (n ≥6) 个点, 每两点间连一线段, 假设其中任意三条线段在圆内不共点, 于是任意三条线 段相交构成一个三角形. 求这些线段构成的三角形的个数.

6. 求以凸n (n ≥6) 边形的顶点为顶点, 对角线为边的凸k (3≤k ≤

7.(1)已知数列{a n }共有2k +1项, a 1=0, a 2k +1=0, 且|a i +1-a i |=1(i =1, 2, , 2k ) . 求满足这种条件的不同数列的个数.

(2)已知数列{a n }共有2k +1项, a 1=0, a 2k +1=0, |a i +1-a i |=1且a i ≥0(i =1, 2, , 2k ) . 求满足这种条件的不同数列的个数.

8. 戏院票房前有2n 人排队买票, 每张票5元, 其中有n 个人各持一张5元的纸币, 另n 个人各持一张10元 的纸币, 售票处没零钱找补. 求能顺利买票而不发生找补零钱的困难的排队方法数.

第 1 页 共 8 页 1n ) 边形的个数. 2

9.(1)将n 个相同的小球装进m 个不同的盒子, 求装球方法数.

(2)将n 个相同的小球装进m (m ≤n ) 个不同的盒子, 每个盒子至少1个小球, 求装球方法数.

10. 设集合S ={1, 2, 3, , 2n }, 其中n 为正整数. 现规定A n ={A ⊆S ||A |=n , A 中各元素之和为偶数}, B n ={B ⊆S ||B |=n , B 中各元素之和为奇数}, 求|A n |-|B n |.

二、巩固练习

11.(2011,卓越自主) 已知数列{a n }共有11项, a 1=0, a 11=4, 且|a k +1-a k |=1(k =0, 1, 2, , 10) . 满足这种条件的不同数列的个数为【 】.

A.100 B.120 C.140 D.160

12.(2012,华约自招) 有六个棋子, 分别是红色和黑色的车、马、炮, 将它们排成一列, 使得任何一个棋子左边的红色棋子不少于黑色棋子, 则不同的排列方式数为____________.

13.(1)若将12个志愿者名额分给5个班, 则分配方法数为____________.

(2)若将12个志愿者名额分给5个班, 每个班至少1个名额, 则分配方法数为____________.

14. 若设集合M ={1, 2, , 1000}, 现对M 的任一非空子集X , 令a X 表示X 中最大数与最小数之和, 则所有这样的a X 的算术平均值为____________.

15. 圆周上有100个等分点, 以其中三个点为顶点的钝角三角形的个数为____________.

16. 甲乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛. 若双方先由1号队员比赛, 负者被淘汰, 胜者再与负方2号队员比赛, ……, 直到有一方队员全被淘汰为止, 另一方获得胜利, 形成一种比赛过程, 则所有可能出现的比赛过程的种数为____________.

17. 在数列9, 9, 9, , 9

18. 甲、乙两人参加竞选, 甲得m 张选票, 乙得n 张选票, m >n . 在m +n 张选票逐一唱票的过程中, 甲得的 票数一直领先的唱票记录有多少种可能的结果？

第 2 页 共 8 页 0122013中, 删去首位数字是9的项, 这个数列余下的项数为____________.

组合计数问题的基本方法——对应(教师版)

一、例题分析

1. 在如图所示的8⨯6的网格中, 若一只小虫子每次只能向右或向上爬一格, 求这只小虫子从A 点爬到B 点的不同的路线数. C

12=792 5

解析:由于小虫子从A 点爬到B 点共需要爬行12格, 其中向右爬行7格, 向上爬行5格, 爬行的某一格是向 右还是向上, 就决定了爬行路线的不同, 因此, 我们只需要确定小虫子爬行的12格中的哪几格是向右, 哪几 格是向上就可以了, 即不同的爬行路线数为C 12=792.

2.(1)在如图所示的7⨯5的方格纸中, 一共有多少个长方形？ C 8⋅C 6=420

(2)在如图所示的7⨯5的方格纸中, 一共有多少个包含阴影部分的长方形？ C 3⋅C 5⋅C 2⋅C 4=120 解析:(1)由于任意两条水平线和竖直线就确定了一个长方形, 且任意一个长方形的两条水平边对应着两 条水平线, 两条竖直边对应着两条竖直线, 因此图中长方形的个数为C 8⋅C 6=420.

(2)要包含阴影部分的长方形, 两条竖直线中一条是阴影部分左侧3条线中的一条, 另一条则是其右 侧5条线中的一条, 两条水平线中一条是阴影部分下方2条线中的一条, 另一条则是其上方4条线中的一 条, 因此符合题意的长方形的个数为C 3⋅C 5⋅C 2⋅C 4=120.

3. 设凸n (n ≥4) 边形的任意三条对角线不相交于形内一点, 求凸n 边形对角线在形内的交点数. C n 解析:由于一个交点是由两条对角线相交而得, 反之, 两条相交的对角线有唯一的交点, 又由于两条相交的 对角线对应着凸n 边形中的四个点, 且凸n 边形中的四个点能确定两条相交的对角线, 因此, 凸n 边形对角 线在形内的交点数等于凸n 边形中四点组的组数, 即凸n 边形对角线在形内的交点数为C n .

第 3 页 共 8 页 [**************]

4. 将三角形的各边n 等分, 过各分点作其余两边的平行线, 求在三角形内所形成的平行四边形的个数S . 解析:如图, 延长BA 到点M , 使AM =

到点N , 使CN =1AB , 延长BC n 1CB . 设线段MN 的n +1等分的分点n

(包括M , N 共n +2个点) 依次记为0, 1, 2, 3, , n +1, 于

是图中的平行四边形每边所在直线恰与线段MN 交于四

点i , j , k , l (0≤i

的平行线, 过k , l 作BC 的平行线, 便可得图中的一个平

行四边形, 这种对应是一一对应. 因此边与AC 不平行的平行四边形共C n +2个, 从而图中平行四边形的总个数为S =3C n +2.

注意：将题目中的三角形改为正三角形, 平行四边形改为菱形, 其结果又如何？

结论:当n 为偶数时, S =

5. 在圆周上有n (n ≥6) 个点, 每两点间连一线段, 假设其中任意三条线段在圆内不共点, 于是任意三条线 段相交构成一个三角形. 求这些线段构成的三角形的个数. C n +4C n +5C n +C n 解析:由于符合题意的三角形按顶点所在的位置可分为以下四类:

(1)第一类:三个顶点均为圆上的点, 其个数为C n (图1) ；

(2)第二类:三个顶点中有两个是圆上的点, 一个是圆内的点, 其个数为4C n (图2) ；

(3)第三类:三个顶点中有一个是圆上的点, 两个是圆内的点, 其个数为5C n (图3) ；

(4)第四类:三个顶点均为圆内的点, 其个数为C n (图4) ；

6334564411n (n +2)(2n -1) ；当n 为奇数时, S =(n -1)(n +1)(2n +3) . 8845

综上可知, 符合题意的三角形的个数为C n +

4C n +5C n +C n . 3456

第 4 页 共 8 页

6. 求以凸n (n ≥6) 边形的顶点为顶点, 对角线为边的凸k (3≤k ≤1k -1k n ) 边形的个数. C n -k -1+C n -k 2

解析:设凸n 边形为A 1A 2 A n , 符合条件的凸k 边形为A i 1A i 2 A i k (1≤i 1

第一种情况:i 1=1, 3≤i 2

第二种情况:2≤i 1

对于第一种情况, 我们可以构造一个一一对应关系(i 2, i 3, , i k ) →(i 2-2, i 3-3, , i k -k ) , 这也就有

k -11≤i 2-2

不同取法. 这种情况下的凸k 边形有C n -k -1个.

对于第二种情况, 我们可以构造一个一一对应关系(i 1, i 2, , i k ) →(i 1-1, i 2-2, , i k -k ) , 这也就有k -11≤i 1-1

综上可知, 符合条件的凸k 边形有C n -k -1+C n -k 个.

7.(1)已知数列{a n }共有2k +1项, a 1=0, a 2k +1=0, 且|a i +1-a i |=1(i =1, 2, , 2k ) . 求满足这种条件的不同数列的个数. C 2k

(2)已知数列{a n }共有2k +1项, a 1=0, a 2k +1=0, |a i +1-a i |=1且a i ≥0(i =1, 2, , 2k ) . 求满足这种条件的不同数列的个数. C 2k -C 2k 解析:(1)由于|a i +1-a i |=1, 因此a i +1是在a i 的基础上+1或-1, 而a 1=0, a 2k +1=0, 也就是说, a 2k +1是在a 1的基础上进行了2k 次+1或-1的运算, 其结果为a 2k +1-a 1=0, 所以在2k 次+1或-1的运算中共进行了k 次+1运算, k 次-1运算, 故满足条件的不同数列的个数为C 2k .

(2)由(1)知:应在C 2k 的基础上去掉不符合a i ≥0的情况. 对于有a i

第 5 页 共 8 页 k -1k k -1k k k k k -1k k k -1