第三讲 递推与计数综合（讲义和例题）
本讲要求：复习传球、染色；掌握递推计数法与对应原理
例1. 给ABCDEFG这7部分用4种颜色染色，要求相邻部分不同色，共有 种不
B A C D 同的染色方法。
E F G
A B 例2. 把图中A、B、C、D、E、F这6个正方形用4种颜色中的某种着色（F是图中最小的那个正
方形，在图上未用字母标出），且相邻部分不能用同色。那么共有 种不同的着色方法。
C D E
例3. 有甲乙丙丁4人互相传球。每人都可以把球传给另3人中的任意一个。现由甲发球，并作为第一次传球，要求
经过6次传球，球回到甲的手中，且在此之前只有一次甲接到别人传球的情况，这样的传球方法共有 种。 例4. 1）三个人分别身着红、黄、绿、蓝四色球衣练习传球，每人都可以把球传给另外两个人中的任意一个，由甲
发球，并作为第一次传球，经过八次传球球仍然回到甲手中，共有 种方法；如果经由任意一人发球，最后经过八次传球球仍然回到第一个发球人手中，那么共有 ；
2）有一个圆环被分成8部分（如右图所示），现在有4种颜色可选，要将每一部分染上某种颜色，并且相邻两部分颜色不同，共有 种染色方法。（图形位置固定，不能旋转，因此某些染色方法虽然能通过旋转重合，但仍算不同的染色方法）
例5. 有些五位数的各位数字均取自1，2，3，4，5，并且任意相邻两位数字（大减小）的差都是1．问这样的五位
数共有 个； 例6. 一段楼梯共10级台阶，规定每一步只能跨一级或两级，要登上10级台阶共有 种不同的方法；
例7. 用8个12的骨牌去覆盖一个28的网格，共有 种不同的覆盖方法；
例8. 10条直线最多能够把平面分成 部分；10条直线最多能够把圆的内部分为 部分；10个圆最多能够
把平面分为 部分； 例9. 对一个自然数作如下操作：如果是偶数则除以2，如果是奇数则加1。那么能够经过9次操作变为1的数共有
_______个。
C 例10. 一只蚂蚁从A出发，沿着八面体的棱行进，要求恰好经过每个顶点各一次，问共
有 种走法；
D
E F B
A
例11. 游乐园的门票1元1张，每人限购1张．现在有10个小朋友排队购票，其中5个小朋友只有1元的钞票，另
外5个小朋友只有2元的钞票，售票员没有准备零钱．问有 种排队方法，使售票员总能找得开零钱；
