探究与发现 组合数的两个性质教学设计一等奖

第一课时 排列组合问题的解题方法（一）

教学目标：

掌握几类特殊的排列问题的解决技巧. 教学重点：掌握“条件排列”、“集团排列”、“间隔排列”、“部分顺序排列”问题的解题技巧.

教学难点：如何应用“技巧”解题．

教学过程：

【例析技巧】

一.集团排列问题：部分元素必须安排在一起（相邻）的排列问题，称之为“集团排列”问题.解决这类问题，常用“捆绑法”，其方法是先排“集团”内部的元素，再把这个大“元素”与其它元素一起排列即可.

例1 若7位同学站成一排

（1）甲、乙两同学必须相邻的排法共有多少种？

（2）甲、乙和丙三个同学都相邻的排法共有多少种？

（3）甲、乙两同学必须相邻，而且丙不能站在排头和排尾的排法有多少种？

（4）甲、乙、丙三个同学必须站在一起，另外四个人也必须站在一起的排法有多少种？

解：（1）先将甲、乙两位同学“捆绑”在一起看成一个元素与其余的5个元素（同学）6一起进行全排列有A6种方法；再将甲、乙两个同学“松绑”进行排列有A2种方法．所以这62样的排法一共有A6A21440种. 253（2）方法同上，一共有A5720种. A3（3）解法一：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，因为丙不能站在排头和排尾，所以可以从其余的5个元素中选取2个元素放在排头和排尾，2有A5种方法；将剩下的4个元素进行全排列有A4种方法；最后将甲、乙两个同学“松绑”2进行排列有A2种方法．所以这样的排法一共有A5A4A2960种方法. 2424解法二：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，若丙站5在排头或排尾有2A5种方法，所以，丙不能站在排头和排尾的排法有(A62A5)A2960652种方法.

解法三：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，因为丙1不能站在排头和排尾，所以可以从其余的四个位置选择共有A4种方法，再将其余的5个元5素进行全排列共有A5种方法，最后将甲、乙两同学“松绑”，所以，这样的排法一共有125960种方法．

A4A2A5（4）将甲、乙、丙三个同学“捆绑”在一起看成一个元素，另外四个人“捆绑”在一342起看成一个元素，时一共有2个元素，∴一共有排法种数：A3A4A2288（种）

说明：对于相邻问题，常用“捆绑法”（先捆后松）．

二. 间隔排列问题：部分元素不能安排在一起（间隔）的排列问题，称之为“间隔排列”问题.解决这类问题，常用“插空法”，其方法是先排不需要间隔的元素，再将需要间隔的元素通过插空的方式插进来即可. 例2 在一条南北方向的步行街同侧有8块广告牌，牌的底色可选用红、蓝两种颜色.若只要求相邻两块牌的底色不都为红色，则不同的配色方案共有（

）

A.55. B.56. C.46. D.45. 1解：没有红牌，一种方法；有一块红牌，让其插空，有C8种方法；有二块红牌，让其234插空，有C7种方法；有三块红牌，让其插空，有C6种方法；有四块红牌，让其插空，有C51234种方法；共有方法1C8C7C6C555种. 说明：对于不相邻问题，常用“插空法”（特殊元素后考虑）．

例3 某仪表显示屏上一排有7个小孔，每个小孔可显示出0或1，若每次显示其中三个孔，但相邻的两孔不能同时显示，则这显示屏可以显示的不同信号的种数有 种. 解：四个孔不亮，三个孔亮，相当于三个亮着的孔在四个不亮的孔之间插空，故有

3C522280种方法. 三. 部分不同元素定序与部分相同元素排列问题：

部分不同元素在排列前后的顺序固定不变（不一定相邻）的排列问题，称之为“定序排列”问题.解决这类问题的基本方法有三种. （1）“消序法”（有些地方叫“整体法”），即若有mn个元素排成一列，其中有m个mn元素之间的排列顺序不变，将这mn个元素任意排成一列，共有Amn种不同的排法，其

m中未定序的n个元素排在某一特定位置的排列的个数有Am种排法，但只有一个排列是我们mnAmn所需要的排列，因而共有种不同的排法.类似地还可推广到一般情形，如有有mAmmnk个元素排成一列，其中有m个元素之间的排列顺序不变，且另外k个元素之间的mnkAmnk排列顺序也不变，则共有m中不同的算法. kAmAk（2）逐一插空法：先将定序的元素进行排列，再将其它元素逐一插入这组元素两端及中间. （3）优序法：先将所有位置中按“特殊元素”个数选出若干位置，并把这些特殊元素按规定顺序排上去，再将普通元素在其余位置上全排列. 例4 若5男5女排成一排，按下列要求各有多少种排法

（1）男女相间；（2）女生按指定顺序排列. 5解：（1）先将男生排好，有A5种排法；再将5名女生插在男生之间的6个“空挡”（包555括两端）中，有2A5种排法.故本题的排法有N2A5；

A528800（种）10A105（2）方法1（消序法）：N5A1030240；

A5方法2（逐一插空法）：5个女生按序排列，有1中方法，5个男生逐个插空，有6,7,8,9,10种方法，共有67891030240种方法. 5方法3（优序法）：设想有10个位置，先将男生排在其中的任意5个位置上，有A10种排法；余下的5个位置排女生，因为女生的顺序已经指定，所以她们只有一种排法. 5故本题的结论为NA10130240（种）. 例5 今有2本相同的语文书，3本相同的数学书，4本相同的英语书排成一排，有多少种不同的排法？

9A9解：（消序法）有2341260种. A2A3A4例6 一个楼梯共18个台阶，12步登完，可一步登一个台阶，也可一步登两个台阶，一共有多少种不同的走法？

解：根据题意，要想12步登完，只能6个一步登一个台阶，6个一步登二个台阶.因此，

12A12把问题转化为“相同元素”的排列问题.因此有66924（种）. A6A6点评：对于部分不同元素定序排列以及相同元素的排列问题，可用优序法. 【随堂练习】

1．从5位同学中选派4位同学在星期五、星期六、星期日参加公益活动，每人一天，要求星期五有2人参加，星期六、星期日各有1人参加，则不同的选派方法共有（ B ）

A．40种

B．60种

C．100种

D．120种

2.安排3名支教老师去6所学校任教，每校至多2人，则不同的分配方案共有210种.（用数字作答）

3．用数字0，1，2，3，4，5组成没有重复数字，且比20000大的五位偶数有（

）

A.288个 B.240个 C.144个 D.126个

4．如图，用6种不同的颜色给图中的4个格子涂色，每个格

子涂一种颜色，要求最多使用3种颜色且相邻的两个格子颜色不同，

则不同的涂色方法共有

390 种（用数字作答）．

5．某校开设9门课程供学生选修，其中A,B,C三门由于上课时间相同，至多选一门，学校规定每位同学选修4门，共有

75 种不同选修方案.（用数值作答）

6．从班委会5名成员中选出3名，分别担任班级学习委员、文娱委员与体育委员，其中甲、乙二人不能担任文娱委员，则不同的选法共有 36 种．（用数字作答）

【课后作业】

1．某校安排5个班到4个工厂进行社会实践，每个班去一个工厂，每个工厂至少安排一个班，不同的安排方法共有240种．（用数字作答）

2．将数字1，2，3，4，5，6拼成一列，记第i个数为ai（i1，2，…，6），若a11，．

a33，a55，a1a3a5，则不同的排列方法有 30 种（用数字作答）解：分两步：（1）先排a1，a3，a5，当a1=2时，有2种；当a1=3时，有2种；当a1=4时，有1种，共有5种；（2）再排a2，a4，a6，共有A36种，故不同的排列方法种数为5×6=30，填30．

3.中韩两支围棋队各由8人组成，按事先排好的次序出场进行围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，……，直到有一方全部被淘汰为3

止，另一方获胜，形成一个比赛过程．

（1）已知中方动用了5名队员，取得了胜利，问这样的比赛过程有多少种？

（2）求由中方第8位选手获得最后胜利的概率.

解：（1）中方胜利时，双方共有8513名队员参加了比赛，将他们按淘汰的顺序从左向右排列，则最右为中方5号，右第二个为韩方8号，从右第三个至最左，共11个位置上，有4个位置排中方队员，其余排韩方队员，每一种排法，对应一种比赛结果，故共有4C11330种．

7C144（2）p8. C16154. 若7位同学站成一排

（1）甲、乙两同学不能相邻的排法共有多少种？

（2）甲、乙和丙三个同学都不能相邻的排法共有多少种？

762解：（1）解法一：（排除法）A7A6A23600；

5解法二：（插空法）先将其余五个同学排好有A5种方法，此时他们留下六个位置（就称2为“空”吧），再将甲、乙同学分别插入这六个位置（空）有A6种方法，所以一共有52A5A63600种方法．

（2）先将其余四个同学排好有A4种方法，此时他们留下五个“空”，再将甲、乙和丙33三个同学分别插入这五个“空”有A5种方法，所以一共有A4A5＝1440种．

44【课后记】

第二课时排列组合问题的解题方法（二）

教学目标：

掌握几类特殊的排列问题的解决技巧. 教学重点：掌握“错位排列”、“圆桌排列”、“转化命题”等问题的解题技巧.

教学难点：如何应用“技巧”解题．

教学过程：

【例析技巧】

四.错位排列问题

n个不同元素排成一排，有m个元素（mn）不排在相应位置的排列种数共有：

n1n12n23n3mnmAnCmAn1CmAn2CmAn3(1)mCmAnm. 0当nm时，规定A00!1，这个公式亦成立. 例7 五封标号为1～5的信放进5个编号为1～5的信笺里面，若信的编号与信笺的编号都不相同，一共有多少种不同放法. 解：这是著名的信封问题，很多著名数学家都研究过.瑞士数学家欧拉按一般情况给出了一个递推公式：

用A、B、C……表示写着n位友人名字的信封，a、b、c……表示n份相应的写好的信.把错装的总数记为f(n).假设把a错装进B里了，包含着这个错误的一切错装法分两类：

（1）b错装进A里，这时每种错装的其余部分都与a、b、A、B无关，应有f(n2)种错装法. （2）b错装进A、B之外的信封，这时的装信工作实际是把（除a之外的）信纸b、c……装入（除B之外的）n1个信封A、C……，显然这种错装方法有f(n1)种. 错装的其余部分都与a、b、A、B无关，应有f(n2)种错装法. 总之在a错装入B的错误之下，共有错装法f(n1)f(n2)种. 装入D……的n2种错误之下，同样都有f(n1)f(n2)种错装法. 因此f(n)(n1)[f(n1)f(n2)]，显然f(1)0，f(2)1. 由此可得f(5)44. 注意：用容斥原理亦可解决此题. 普遍结论为错排公式1：f(n)n![11111(1)n]. 1!2!3!n!错排递推公式2：

f(n)(n1)[f(n1)f(n2)]

错排公式3：AnCmAn1CmAn2CmAn3(1)CmAnm

例8

有5个人站成一排，其中A不站第一位，B不站第二位，C不站第三位，D不站n1n12n23n3mmnm

第四位，E不站第五位，共有多少种不同的站法. 解析：上面两例实际上可以看成n个不同元素中有m（mn）错位排列的问题. 而这个问题是其特殊情况，即全错位排列问题. 514233241500共有A5C5A4C5A3C5A2C5A1C5A044种（注意A00!1）

例9 同室四人各写一张贺年卡，先集中起来.然后每人从中拿一张别人送出的贺年卡.则四张贺年卡不同的分配方式有

A.6种

B.9种

C.11种

D.23种 解析：由上面公式得：

413223140A4C4A3C4A2C4A1C4A09种，∴选择B答案. 因此可得到全错位排列的公式：

n个不同元素排成一排，第一个元素不在第一位，第二个元素不在第二位，……，第n个元素不在第n位的排列数为：

n1n12n23n3n0AnCnAn1CnAn2CnAn3(1)nCnA0

nn12n23n3mnm这实际上是公式AnC1(1)mCmAnm的特殊情况.这mAn1CmAn2CmAn3个公式很有用，只要有特殊元素不站特殊位置的问题，都可以用这个公式很快得到解决，希望这个公式对大家有所帮助.

五. 圆桌排列

从n个不同元素中不重复的取出m（1mn）个元素排在一个圆周上，叫做这n个不同元素的圆排列.如果一个m-圆排列旋转可以得到另一个m-圆排列，则认为这两个圆排列是相同的. 特别的，当mn时，n个不同元素作成的圆排列总数为(n1)!. 证明：在圆周上任选一个位置排a1有n种排法，再选一个位置排a2有n1种排法，…，最后一个位置排an有1种排法.而这n个人顺时针（或逆时针）挪动n次位置都是同一种排列.所以共有n!(n1)!种排法. n例10

有5对夫妇参加一场婚宴，他们被安排在一张10个座位的圆桌就餐，但是婚礼操办者并不知道他们彼此之间的关系，只是随机安排座位。问5对夫妇恰好都被安排在一起相邻而坐的概率是多少？(

)

A. 在1‰到5‰之间 B. 在5‰到1%之间 C. 超过1% D. 不超过1‰

解：5对夫妇相邻而座，可以看做是五个大元素为桌而坐，所以有4!种坐法，而夫妇间又可以换位置，所以共有4!2222220.002. 故选：A.

9!945例11

博杰学习网竞赛小组“先进人物评比”最终圈定了n个人，需要确定最终的三个“先进人物”人选.方法是：这n个人排成一行，从第一名开始，1至3循环报数，凡报出3的就退出，余下的向前靠拢，按此规律重复进行.直到第p次报数后，只剩下3个人为止.试问：这剩下的三个人，分别在队伍最初的什么位置？

解：设n个人的编号依次为1,2，…，n.最后剩下的三个人中，第三人的编号为bn.nn个人，还剩n个人.bn向前移33b3brnn动了bnbk（kn）个人，前面淘汰了nbnrn（rn1,2）个人.故bnk.3321其中当bk为奇数时，rn1；否则，rn2，每报一次号，人数减少（除不尽时取整）.3因bn未被淘汰，故不是3的倍数.第一次报数后淘汰了计算bn逐步归纳为减小的数列，最终划归到小情况.例如n1000时，第三个人的初始位置是712. 例12 将圆分成n（n2）个扇形，现用m（m2）种颜色给这些扇形染色，每个扇形恰染一种颜色且要求相邻的扇形不同色.问有多少种不同的染色方法？

解：设染色方法数为an. （1）求初始值.当n2时，给S1染色有m种方法，给S2染色有m1种方法. 所以a2m(m1)；

（2）求递推关系. 给S1染色有m种方法，给S2染色有m1种方法，给S3染色有m1种方法，……，给Sn染色有m1种方法.共有m(m1)这种情况可以分为两类

一类是Sn与S1不同色，此时的染色方法种数是an；另一类是Sn与S1同色，Sn与S1可以合并为一个扇形，Sn1与S1不同色，染色方法种数为an1.由加法原理，得到

n1种方法. anan1m(m1)n1（n2）. （3）求an.构造等比数列.结论：共有an(m1)(1)(m1)种染色方法. nn

六.转化命题

对于一些较难的排列组合问题，通常采用转化命题的方法来解决.比如圆内弦的交点个数可转化为圆内接四边形的个数；异面直线的对数可转化为3倍的四面体的个数等. 例13 圆周上共有15个不同的点，过其中任意两点连一弦，这些弦在圆内的交点最多有多少个？

分析：若两弦有交点，则两弦应是圆内接四边形的对角线，即一个四边形对应一个交点.4所以共有C151365个交点. 小结：

1.“在”与“不在”可以相互转化.解决某些元素在某些位置上用“定位法”，解决某些元素不在某些位置上一般用“间接法”或转化为“在”的问题求解. 2.排列组合应用题极易出现“重”、“漏”现象，而“重”、“漏”错误常发生在该不该分类、有无顺序的问题上.为了更好地防“重”堵“漏”，在做题时需认真分析自己做题思路，也可改变解题角度，利用一题多解核对答案. 【作业】

1.今有8个人坐圆桌，有多少种坐法？

2.有5个男孩，3个女孩围成一圆，其中3个女孩不相邻，有多少种站法？

3.一圆型餐桌依次有A、B、C、D、E、F六个座位，现让3个大人和3个孩子入座进餐，要求任何两个小孩都不能坐在一起，则不同的作法总数为 72 .

第三课时排列组合问题的解题方法（三）

教学目标：

掌握几类特殊的排列问题的解决技巧. 教学重点：掌握“容斥原理”、“错位排列”、“圆桌排列”等问题的解题技巧.

教学难点：如何应用“技巧”解题．

教学过程：

【例析技巧】

七. 用容斥原理解排列问题

有些排列组合问题可转化为求集合的元素的个数来求.充分应用容斥原理：

n(AB)n(A)n(B)n(AB)

n(ABC)n(A)n(B)n(C)n(AB)n(BC)n(AB)n(ABC). 例14

五人站成一排，其中甲不站第一位，乙不站第二位，共有多少种不同的站法. 解：这个问题在高中很多参考书上都有，有几种解法，其中一解法是用排除法：先考虑5445个有的全排列，有A5种不同的排法，然后除去甲排第一（有A4种）与乙排第二（也有A4种），但两种又有重复部分，因此多减，必须加上多减部分，这样得到共有：

543A52A4A378种. 例15

有5个人站成一排，其中甲不站第一位，乙不站第二位，丙不站第三位，共有多少种不同的站法. 5432仿上分析可得：A53A43A3A264种. 八.均匀分组问题．

mmCCmnmnm一般地：将mn个不同元素均匀分成n组（每组m个元素），共有nAnmCm种方法．

例16 有6本不同的书，按下列要求各有多少种不同的选法：

（1）分给甲、乙、丙三人，每人2本；

（2）分为三份，每份2本；

（3）分为三份，一份1本，一份2本，一份3本；

（4）分给甲、乙、丙三人，一人1本，一人2本，一人3本；

（5）分给甲、乙、丙三人，每人至少1本. 222解：（1）根据分步计数原理得到：C6C4C290种；

222（2）分给甲、乙、丙三人，每人两本有C6C4C2种方法，这个过程可以分两步完成：第一步分为三份，每份两本，设有x种方法；第二步再将这三份分给甲、乙、丙三名同学有A33种方法．根据分步计数原理可得：CCCxC26242233，所以222C6C4C2x15．因此，3A3分为三份，每份两本一共有15种方法．

（3）这是“不均匀分组”问题，一共有C6C5C360种方法．

（4）在（3）的基础上再进行全排列，所以一共有C6C5C3A3360种方法．

1233123

（5）可以分为三类情况：

222①“2、2、2型”即（1）中的分配情况，有C6C4C290种方法；

1233②“1、2、3型”即（4）中的分配情况，有C6C5C3A3360种方法；

43③“1、1、4型”，有C6A390种方法；

所以，一共有90+360+90＝540种方法．

11C64C2C1点评：本题第（3）种类型为部分均匀分组再分配，其分组总数为．

2A2题型变换：8名球员住A、B、C三个房间，每个房间最多住3人，有多少种住宿方法？

332C8C5C23解：A3．

2A2例17 若3名飞行员和6名特勤人员分别上3架不同型号的直升飞机执行任务,每机一名飞行员和两名特勤人员，有多少种分配方法？

222111C6C4C2C3C2C133222111解：先分组，再分配，，或者AACCCC336423C2C1．

33A3A3类题：20名同学分两组，每组10人去某地社会实践，其中6名干部，每组3人，不同37C6C142分法总数是多少？答案：22A2．

A2A2九. 隔板法：将n个相同元素，分成k（nk，n，kN）组，可以看成是在n个k1元素之间的n1个空隙间插入k1块隔板.共有Cn1种方法. *例18 将六本相同的书全部发给甲、乙、丙三人. （1）每人至少分到一本书，问有多少种不同的分法？

（2）每人不一定都分到一本书，问有多少种不同的分法？

2解：（1）用“隔板法”处理，六本书之间有五个空，插入两块隔板，有C5种分法；

用“隔板站位法”处理，六本书之间有五个空，需插入两块隔板，但由于有人可能没有书，所以两块隔板站着两个位置，加上六本书，可以看着是628本书，分成3分，所22以有C6C2828种分法．

点评：〖类题〗求不定方程x1x2x36的非负整数解的个数？

题型变换一：四本不同的书，分给三个人，每人至少一本，全部分完，有几种分法？

23解：先分组，再分配有C4A3种．

题型变换二：n本不同的书，分给n1个人，每人至少1本，全部分完，有几种分法？

2n1解：先分组，再分配有CnAn1种．

题型变换三：n本相同的书，全部分给m（mn）个人. （1）每人至少分到一本书，问有多少种不同的分法？

（2）每人不一定都分到一本书，问有多少种不同的分法？

解：（1）解法一（隔板站位法）：每人先分一本书，还剩下nm本书，加上m1块隔m1板，可视为(nm)(m1)n1本书，分给m个人，所以有Cn1种方法. m1解法二（隔板法）：n本书之间有n1个空，需插入m1块隔板，所以有Cn1种方法. （2）（隔板站位法）：n本书之间，需插入m1块隔板，但是，由于有人分不到书，所以m1块隔板站着m1个位置，加上n本书，可视为nm1本书，用m1块隔板分成m1m分，所以有Cnm1种方法（这也是一个公式）. 【随堂练习】

1.（1）

四个不同的小球放入四个不同的盒中，一共有多少种不同的放法？

（2）

四个不同的小球放入四个不同的盒中且恰有一个空盒的放法有多少种？

解：（1）根据分步计数原理：一共有4256种方法；

（2）（捆绑法）第一步：从四个不同的小球中任取两个“捆绑”在一起看成一个元素有2323种方法；第二步：从四个不同的盒中任取三个将球放入有A4种方法，所以，一共有C4A4C44＝144种方法．

说明：先组合，再排列是解决问题的关键．本题亦可先将4个小球分成三组，每组分别211C4C2C13有1/1/2个，共再放入四个盒子中的三个，共有A4144种．

2A2思考：（1）四个相同的小球放入四个不同的盒子中，一共有多少种不同的放法？

解：（隔板站位法）共C43C735．

（2）10个相同的小球放入编号为1、2、3的盒子中，球数不少于编号数的放法有多少33

种？

22解：按要求放6个，其余4个按隔板站位法有C4C2615种方法．

另解：（隔板法）设1，2，3号盒子所放的球数分别为a，b，c.则有abc10. 设xa，yb1，zc2，则方程xyz7的正整数解的组数，就是放球的22方法数.所以共有C42C615种方法. 注意：这种利用“先换元，再用隔板技巧”的方法对于求有限制条件的不定方程的非负整数解的问题很有效！

【总结提炼】

均匀分组（不计组的顺序）问题不是简单的组合问题，如：将3个人分成3

组，每组111一个人，显然只有1种分法，而不是C3C2C16种

一般地，将mn个不同元素均匀分成n组，有【课后作业】

【板书设计】（略）

【教学后记】

mCmnC(mn1)mmCmAmm种分法；

第四课时排列组合问题的解题方法（四）

教学目标：

掌握几类特殊的排列问题的解决技巧. 教学重点：掌握“递推法”等问题的解题技巧.

教学难点：如何应用“技巧”解题．

教学过程：

十.穷举法：

对于一些不能直接用两个原理，且类别不多的问题，通常采用穷举法.即列举所有情况. 例19 将五个市级三好学生名额和八个区级优秀学生干部名额全部分配到辖区的两所中学，每所学校至少有一个名额，有多少种不同的分配方案？

解：分配情况用有序数组(x,y)表示：（1,12），（2,11），（3,10），（4,9），（5,8），（6,7）.

然后两校交换.所以共有分配方案数为2(234566)52种. 例20 . 十一.递推法：

对于一些较复杂的排列问题，可以建立排法之间的一个递推关系，通过递推关系求出排法种数. 例19 一个楼梯共10个台阶，如果规定一步登一个台阶或登两个台阶，一共有多少种不同的走法？

解：设上n级台阶的走法为an种，易知a11，a22，当n2时，上n级台阶的走法可分两类：第一类是最后一步跨一级，有an1种走法，第二类是最后一步跨二级，有an2种走法.由加法原理可知anan1an2，据此可得a1089种不同的走法. 例20

有五个人排成一列，现在要重新排列，要求都不能站在原来的位置，有几种不同排法？

解：我们考虑人数为n的情况，即n个人排成一列，重新站队时，各人都不站在原来的位置上.设满足这样的站队方式有an种，现在我们来通过合理分步，恰当分类找出递推关系：

第一步：第一个人不站在原来的第一个位置，有n1种站法. 第二步：假设第一个人站在第2个位置，则第二个人的站法又可以分为两类：

第一类，第二个人恰好站在第一个位置，则余下的n2个人有an2种站队方式；

第二类，第二个人不站在第一个位置，则就是第二个人不站在第一个位置，第三个人不站在第三个位置，第四个人不站在第四个位置，……，第n个人不站在第n个位置，所以有an1种站队方式. 由分步计数原理和分类计数原理，我们便得到了数列an的递推关系式：

an(n1)(an1an2)，显然，a10，a21，…，a544.故有44种不同排法. 注意：n个人排成一排后，解散后重新排队，自己不站原来的位置的排法种数可由以下公式推导得到：

（1）a10，a21，an(n1)(an1an2)（n3）；

（2）ann![11111(1)n]. 1!2!3!n!

n1n12n23n3n0（3）anAnCnAn1CnAn2CnAn3(1)nCnA0. 例21 在nm的网格中，从(0,0)点到(n,m)点，只能沿网格的边向x轴正方向或y轴正方向前进，问共有多少种不同的前进路线？

解：对任意一个非x轴、y轴上的点(x,y)，可以从点(x,y1)走来，也可以从点(x1,y)走来.因此，设(x,y)处的路线条数为f(x,y)，则有递推公式：

f(x,y)f(x,y1)f(x1,y). x下面的推理很重要：根据上述递推公式，可得f(x,y)Cxy，即从xy件物品中选出无顺序的x件（或y件）的总方案数.即f(x,y)(xy)!. x!y!小结：上述问题中把每个f(x,y)指标在对应的坐标点处，再将坐标系顺时针旋转135，你发现了什么？这是杨辉三角，f(x,y)Cxy.而我们知道，CxyCxy1Cxy1.这就是通项公式的来源. 另解：记网格横向的x条线段从左至右依次为a1、a2、…、ax，网格纵向的y条线段从下至上依次为b1、b2、…、by.从(0,0)到(x,y)的走法种数，就是a1、a2、…、ax及b1、xb2、…、by这xy个元素的一个定序排列.于是有yAxxyAxxAyy（或(xy)!）种不同走法. x!y!例22 某地决定在一个大型广场建一个同心圆形花坛，花坛分为两部分，中间小圆部分种植草坪，周围的圆环分为n（n3,nN）等份种植红、黄、蓝三色不同的花. 要求相邻两部分种植不同颜色的花. 如图①，圆环分成的3等份分别为a1，a2，a3，有6种不同的种植方法.如图②，圆环分成的4等份分别为

a1，a2，a3，a4，有18种不同的种植方法；则在图③中，圆环分成的n(n3,nN)等份分别为a1，a2，a3，种不同的种植方法. ,an, 有

a1

a1

a2

a4

②

a2

……

a1

a2

a3

a3

①

a3

an

…

③

第18题图

解：对于n的情形，总的涂法数为32n1，但是最后一块与第一块有两种情况：不同色（满足题意）与同色，同色时就是n1的情形，于是得出递推公式：an32n1an1anan1an131an11(1)

，即22n1222n12n2naF(n)6111n3111()，即F(n)2n2(1)n1. 因为3，所以3n844222（n4），变形得例23 有甲乙两队，各有7名队员，分别编号1～7，首先两队编号为1的队员对抗比赛，负者淘汰，胜者与负方的2号队员比赛，…，依次类推.直到某队全部淘汰为止.问最后有多少种不同比赛方式？

解：设f(x,y)表示甲乙两队分别由x，y名队员组成时的方式数.由于上次可能是甲、乙两队中某个被淘汰，故递推公式为：f(x,y)f(x,y1)f(x1,y).故转化为与上题相同的数学模型.即f(x,y)(xy)!

x!y!另解：记甲队7人分别为a1、a2、…、a7，乙队7人分别为b1、b2、…、b7.比赛结束时的方案数就是a1、a2、…、a7及b1、b2、…、b7这14个元素的一个定序排列.于是有1414!A14（或）种不同方案数. 777!7!A7A7小结：求排列组合递推问题时，一定要注意以下几个方面：

①初始条件；②递推关系中1，1的问题；③递推终止条件. 例24 有甲、乙、丙三人踢毽子，互相传递，每人每次只能踢一下，由甲开始踢，经过5次传递后，毽子又被踢回给甲，问有多少种不同的传递方式？

解：设k（k2）个人传递n（n2）次后回到甲处的不同传递方法数为an. 则a2k1.下面考查an1与an的关系.（如图）

甲①②③④甲

则甲①有k1种不同方法，①②有k1种不同方法，②③有k1种不同方法，……，k1种不同方法. 而第n次接毽子的人可能不是甲，也可能是甲，所以anan1(k1)n1

对于本题，令k3，则a22，由递推公式得a32，a46，a510. 注意：由anan1(k1)n1得anan111

(k1)nk1(k1)n1k1即anan1111[]，

nn1(k1)kk1(k1)kan11n2a21()[]，

(k1)nkk1(k1)2k由等比数列的通项公式知即an11n211()()，

n(k1)kk1k1kk1[(1)n(k1)n1].显然，当k3时，a510. k化简an