计数原理之递推问题.doc

排列组合经典问题学案1递推关系问题一、阶梯问题例1 问题提出：有阶梯有n级台阶，上台阶时每步只能跨一阶或两阶台阶，问共有多少种走法？（公式：Fn=_） 注：此公式不需记忆，不需推导，只供增长知识面.变式1：有10级台阶，上台阶时每步只能跨一阶或两阶台阶，问共有多少种走法？变式2：有8级台阶，上台阶时每步可以跨一阶、两阶或三阶台阶，问共有多少种走法？变式3：10级台阶，要求7步走完，每步可跨一阶，也可跨两阶，问有多少种不同的跨法？变式4：某教学楼从底楼到二楼有10级台阶，上楼可以一步上一级，也可以一步上两级，若从底楼到二楼用8步走完，则不同的走法的种数为？二、圈状染色问题：例2问题提出： 用m种不同的颜色去染如图n个扇形，相邻的扇形之间不能同色，问有多少种不同的涂法？（公式：Qn=_） 注：此公式不需记忆，不需推导，只供增长知识面.变式5：用6种颜色给如下图形涂色，要求相邻区域不能涂同一种颜色， (1) (2) (3)变式6：用5种颜色给四棱锥、五棱锥的顶点涂色，同一条棱的两个顶点不能同色，问各有多少种不同的涂法？三、传球问题：例3问题提出：k个人相互传球，已知由甲开始发球，第n次传球后，依然传到甲的不同传球方式共有多少种？变式7：有甲、乙、丙、丁四人相互传球，第一次甲把球传给其他三人中的任何一人，第二次由拿球者再传给其他三人中的任何一人，这样共传6次球，球恰好回到甲手中的传球情形有几种？四、全错位排列问题：例4问题提出： 有n的同学，每人写了1张贺卡，再将这些贺卡混在一起，每人抽取一张，试问每个人拿到的贺卡都不是自己的情形有多少种？ (全错位排列公式：_) 此公式需背记，无需推导变式8：编号为1，2，3，4，5的5个人分别去坐在编号为1，2，3，4，5的座位上，至多有两个号码一致的坐法有_种排列组合经典问题学案2重点题型问题一、被3整除问题例1在集合1,2,3,4,5,6,7,8,9,10中任选2个数，其和能被3整除的选法共有多少种？变式1：在集合0,1,2,3,4,5,6,7,8,9中任选3个数，其和能被3整除的选法共有_种变式2：在集合1,3,5,7,9,11,13,15中任选2个数，其和能被3整除的选法共有_种二、关灯问题：例2马路上有编号为1、2、3、9的9只路灯，为节约用电，现要求把其中的三只灯关掉，但不能同时关掉相邻的两只或三只，也不能关掉两端的路灯，则满足条件的关灯方法共有_种变式3：马路上有11只路灯，为节约用电，现要求把其中四只关掉，但不能同时关掉相邻的两只或三只或四只，也不能关掉两端的路灯，则满足条件的关灯方法有_种.三、等价转化的问题例3射线l1与l2有公共端点O，除端点O外，直线l1上还有A1，A2，A3，A4四个点，在直线l2上还有B1，B2，B3，B4，B5五个点.若在A1，A2，A3，A4四个点中任取一点与B1，B2，B3，B4，B5五个点中各取一点连成一条线段，则这些线段的交点个数最多有多少个？变式4：已知圆周上有n个点，这n个点两两之间形成一条线段，问这些线段的交点最多有多少个？四、比赛问题例4某次足球比赛共12支球队参加，分三个阶段进行.(1) 小组赛：经抽签分成甲、乙两组，每组6队进行单循环比赛，以积分及净胜球数取前两名；(2) 半决赛：甲组第一名与乙组第二名，乙组第一名与甲组第二名作主客场交叉淘汰赛(每两队主客场各赛一场)决出胜者；(3) 决赛：两个胜队参加决赛一场，决出胜负.问：全程赛程共需比赛多少场？变式5：某年全国足球甲级(A组)联赛共有14队参加，每队都要与其余各队在主客场分别比赛一次，则共进行比赛的场次为_变式6：甲、乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，直到有一方队员全被淘汰为止，另一方获胜，形成一种比赛过程，那么所有可能出现的比赛过程共有多少种？变式7：在100名选手之间进行淘汰赛(即一场比赛失败要退出比赛)，最后产生一名冠军，问要举行多少场比赛？五、圆排列问题例56个人围成一圈，一共有多少种坐法？变式8：6颗不同颜色的钻石，可以穿成几种石圈？排列组合经典问题学案3球盒模型问题按以下要求分配6本不同的书，各有几种方法：1 平均分配甲、乙、丙三人，每人2本；2 平均分成三份，每份2本；3 甲乙丙三人一人得1本，一人得2本，一人得3本；4 分成三份，一份1本，一份2本，一份3