计数原理之递推问题.doc

排列组合经典问题学案 1递推关系问题一、阶梯问题例 1． 问题提出：有阶梯有 n 级台阶，上台阶时每步只能跨一阶或两阶台阶，问共有多少种走法？（公式：F n=_______________________________________________）注：此公式不需记忆，不需推导，只供增长知识面.变式 1：有 10 级台阶，上台阶时每步只能跨一阶或两阶台阶，问共有多少种走法？变式 2：有 8 级台阶，上台阶时每步可以跨一阶、两阶或三阶台阶，问共有多少种走法？变式 3：10 级台阶，要求 7 步走完，每步可跨一阶，也可跨两阶，问有多少种不同的跨法？变式 4：某教学楼从底楼到二楼有 10 级台阶，上楼可以一步上一级，也可以一步上两级，若从底楼到二楼用 8 步走完，则不同的走法的种数为？二、圈状染色问题：例 2．问题提出：用 m 种不同的颜色去染如图 n 个扇形，相邻的扇形之间不能同色，问有多少种不同的涂法？（公式：Q n=_______________________________________________） 注：此公式不需记忆，不需推导，只供增长知识面.变式 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，A 2，A 3，A 4 四个点，在直线 l2 上还有 B1，B 2，B 3，B 4，B 5 五个点.若在 A1，A 2，A 3，A 4 四个点中任取一点与B1，B 2，B 3，B 4，B 5 五个点中各取一点连成一条线段，则这些线段的交点个数最多有多少个？变式 4：已知圆周上有 n 个点，这 n 个点两两之间形成一条线段，问这些线段的交点最多有多少个？四、比赛问题例 4．某次足球比赛共 12 支球队参加，分三个阶段进行.(1) 小组赛：经抽签分成甲、乙两组，每组 6 队进行单循环比赛，以积分及净胜球数取前两名；(2) 半决赛：甲组第一名与乙组第二名，乙组第一名与甲组第二名作主客场交叉淘汰赛(每两队主客场各赛一场)决出胜者；(3) 决赛：两个胜队参加决赛一场，决出胜负.问：全程赛程共需比赛多少场？变式 5：某年全国足球甲级(A 组) 联赛共有 14 队参加，每队都要与其余各队在主客场分别比赛一次，则共进行比赛的场次为__________变式 6：甲、乙两队各出 7 名队员按事先排好的顺序出场参加围棋擂台赛，双方先由 1 号队员比赛，负者被淘汰，胜者再与负方 2 号队员比赛，……直到有一方队员全被淘汰为止，另一方获胜，形成一种比赛过程，那么所有可能出现的比赛过程共有多少种？变式 7：在 100 名选手之间进行淘汰赛(即一场比赛失败要退出比赛) ，最后产生一名冠军，问要举行多少场比赛？五、圆排列问题例 5．6 个人围成一圈，一共有多少种坐法？变式 8：6 颗不同颜色的钻石，可以穿成几种石圈？排列组合经典问题学案 3球盒模型问题按以下要求分配 6 本不同的书，各有几种方法：1． 平均分配甲、乙、丙三人，每人 2 本；2． 平均分成三份，每份 2 本；3． 甲乙丙三人一人得 1 本，一人得 2 本，一人得 3 本；4． 分成三份，一份 1 本，一份 2 本，一份 3 本；5． 甲乙丙三人中，一人得 4 本，另外两个每人得 1 本；6． 分成三份，一份 4 本，加两份每份 1 本；7． 甲得 1 本，乙得 1 本，丙得 4 本；8． 分成三份，每份至少 1 本；9． 分给甲乙丙三个人，每人至少 1 本。