排列组合典型问题选讲

1、一.集团排列问题：部分元素必须安排在一起（相邻）的排列问题，称之为“集团排列”问题.解决这类问题，常用“捆绑法”，其方法是先排“集团”内部的元素，再把这个大“元素”与其它元素一起排列即可.例1若7位同学站成一排（1）甲、乙两同学必须相邻的排法共有多少种？（2）甲、乙和丙三个同学都相邻的排法共有多少种？（3）甲、乙两同学必须相邻，而且丙不能站在排头和排尾的排法有多少种？（4）甲、乙、丙三个同学必须站在一起，另外四个人也必须站在一起的排法有多少种？解：（1）先将甲、乙两位同学“捆绑”在一起看成一个元素与其余的5个元素（同学）一起进行全排列有A6种方法；再将甲、乙两个同学“松绑”进行排列有A；种方法

2、.所以这样的排法一共有A 6=1440种.（2）方法同上，一共有 A5 A =720种.（3）解法一：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，因为丙不能站在排头和排尾，所以可以从其余的 5个元素中选取2个元素放在排头和排尾，有 A2种方法；将剩下的4个元素进 行全排列有 A：种方法；最后将甲、乙两个同学“松绑”进行排列有A；种方法.所以这样的排法一共有-2 - 4 - 2.、.A5 A4 A2 =960 种方法.解法二：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，若丙站在排头或排尾有_5.,_6_5、_22A5种方法，所以，丙不能站在排头和排尾的排法有（

3、A6 -2A5） A； =960种方法.解法三：将甲、乙两同学“捆绑”在一起看成一个元素，此时一共有6个元素，因为丙不能站在排头和排尾，所以可以从其余的四个位置选择共有A：种方法，再将其余的5个元素进行全排列共有 A5种方法，最后将甲、乙两同学“松绑”，所以，这样的排法一共有 A4 A55 A： =960种方法.（4）将甲、乙、丙三个同学“捆绑”在一起看成一个元素，另外四个人“捆绑”在一起看成一个元素， 时一共有2个元素，一共有排法种数：A3A4A2 =288 （种）说明：对于相邻问题，常用“捆绑法”（先捆后松）.二.间隔排列问题：部分元素不能安排在一起（间隔）的排列问题，称之为“间隔排列”问

4、题.解决这类问题，常用“插空法”，其方法是先排不需要间隔的元素，再将需要间隔的元素通过插空的方式插进来即可.例2在一条南北方向的步行街同侧有8块广告牌，牌的底色可选用红、蓝两种颜色.若只要求相邻两块牌的底色不都为红色，则不同的配色方案共有（）A.55.B.56.C.46.D.45.解：没有红牌，一种方法；有一块红牌，让其插空，有c；种方法；有二块红牌，让其插空，有c。种方法； 有三块红牌，让其插空，有c；种方法；有四块红牌，让其插空，有c54种方法；共有方法 1+C； +Cy +C；+C； =55 种.说明：对于不相邻问题，常用“插空法”（特殊元素后考虑）例3某仪表显示屏上一排有 7个小孔，每

5、个小孔可显示出 0或1,若每次显示其中三个孔，但相邻的两 孔不能同时显示，则这显示屏可以显示的不同信号的种数有 种.解：四个孔不亮，三个孔亮，相当于三个亮着的孔在四个不亮的孔之间插空，故有c53 M 2 M 2 M 2 =80 种方法.三.部分不同元素定序与部分相同元素排列问题：部分不同元素在排列前后的顺序固定不变（不一定相邻）的排列问题，称之为“定序排列”问题.解决这类问题的基本方法有三种（1） “消序法”（有些地方叫“整体法”），即若有m+n个元素排成一列，其中有 m个元素之间的排列顺序不变，将这 m + n个元素任意排成一列，共有Am：种不同的排法，其中未定序的n个元素排在某一特定位置的

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

7、2种排法；再将5名女生插在男生之间的 6个“空挡”（包括两端）中，有2A5种排法.故本题的排法有 N =2A5 A5 =28800 （种）；A10 .(2)方法 1 (消序法)：N =Af = A50 =30240； A方法2 （逐一插空法）：5个女生按序排列，有 1中方法，5个男生逐个才1空，有 6,7,8,9,10 种方法，共 有 6 M 7 M8 M 9父 10 = 30240 种方法.方法3 （优序法）：设想有10个位置，先将男生排在其中的任意5个位置上，有 A50种排法；余下的5个位置排女生，因为女生的顺序已经指定，所以她们只有一种排法故本题的结论为 N = A0父1 =30240

8、（种）.例5今有2本相同的语文书，3本相同的数学书，4本相同的英语书排成一排，有多少种不同的排法？a9解：（消序法）有 2A3 4 =1260种.A2A3A4例6 一个楼梯共18个台阶，12步登完，可一步登一个台阶，也可一步登两个台阶，一共有多少种不同的走法？解：根据题意，要想12步登完，只能6个一步登一个台阶，6个一步登二个台阶.因此，把问题转化为“相 同元素”的排列问题.因此有一A4 =924 （种）A6A6点评：对于部分不同元素定序排列以及相同元素的排列问题，可用优序法【随堂练习】1 .从5位同学中选派4位同学在星期五、星期六、星期日参加公益活动，每人一天，要求星期五有2人参加，星期六、

9、星期日各有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.1264 .如图，用6种不同的颜色给图中的 4个格子涂色，每个格子涂一种颜色，要求最多使用3种颜色且相邻的两个格子颜色不同，则不同的涂色方法共有390种（用数字作答）5 .某校开设9门课程供学生选修，其中 A,B,C三门由于上课时间相同，至多选一门，

10、学校规定每位同学选修4门，共有 75种不同选修方案.（用数值作答）6 .从班委会5名成员中选出3名，分别担任班级学习委员、文娱委员与体育委员，其中甲、乙二人不能担任文娱委员，则不同的选法共有36种.（用数字作答）【课后作业】1 .某校安排5个班到4个工厂进行社会实践，每个班去一个工厂，每个工厂至少安排一个班，不同的安排方法共有240种.（用数字作答）2 .将数字 1,2, 3, 4, 5, 6拼成一列，记第 i 个数为 a (i=1, 2,，6),若 &#1, %#3, a5#5, a1 <a3 <% ,则不同的排列方法有 30 种（用数字作答）解：分两步：（1）先排a1,

11、 a3, a5,当a1 =2时，有2种；当a1 =3时，有2种；当& =4时，有1种,共有5种；（2）再排a2,%，%,共有 A =6种，故不同的排列方法种数为 5X6=30,填30.3 .中韩两支围棋队各由 8人组成，按事先排好的次序出场进行围棋擂台赛，双方先由 1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，直到有一方全部被淘汰为止，另一方获胜，形成一个比赛过程.（1）已知中方动用了 5名队员，取得了胜利，问这样的比赛过程有多少种？（2）求由中方第8位选手获得最后胜利的概率 .解：（1）中方胜利时，双方共有 8 + 5 = 13名队员参加了比赛，将他们按淘汰的顺序从左向右排列，

12、则最右为中方5号，右第二个为韩方 8号，从右第三个至最左，共 11个位置上，有4个位置排中方队员，其余排韩方队员，每一种排法，对应一种比赛结果，故共有C： =330种.(2)PC86 154 .若7位同学站成一排（1）甲、乙两同学不能相邻的排法共有多少种？（2）甲、乙和丙三个同学都不能相邻的排法共有多少种?解：（1）解法一：（排除法）A； A6八；=3600；解法二：（插空法）先将其余五个同学排好有A5种方法，此时他们留下六个位置（就称为“空”吧），再将甲、乙同学分别插入这六个位置（空）有A2种方法，所以一共有 A：A2 =3600种方法.（2）先将其余四个同学排好有A4种方法，此时他们留下五

13、个“空”，再将甲、乙和丙三个同学分别插入这五个“空”有 A；种方法，所以一共有 A4 A3 = 1440种.【课后记】四.错位排列问题n个不同元素排成一排，有 m个元素（mWn）不排在相应位置的排列种数共有:An C1 An 4' !：；'C2An-2 -C3 An -3 . （ 1）mCmAn mAn CmAn 4 CmAn -2 CmAn -3（ 1） CmAn 用.当n = m时，规定A0 =0! =1 ,这个公式亦成立.例7五封标号为15的信放进5个编号为15的信笺里面，若信的编号与信笺的编号都不相同，一共有多少种不同放法.解：这是著名的信封问题，很多著名数学家都研究过

14、.瑞士数学家欧拉按一般情况给出了一个递推公式：用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(n1)种.错装的其余部分都与 a、b、A、B无关，应有f(n-2)种错装法.总之在a错装入B的错误之下，共有错装法f (n-1)+f(n-2)种.装入D的n2种错误

15、之下，同样都有f (n1)十f(n2)种错装法.因此 f(n) =(n -1)f (n 1) + f (n 2),显然 f (1) = 0 , f (2) =1.由此可得f (5) -44.注意：用容斥原理亦可解决此题.111c 1W遍结论为专日排公式 1： f(n)=n!1 + + ,+(1).1! 2! 3!n!错排递推公式 2：f(n)=(n-1)f (n-1)+ f(n-2)错排公式3: A ©An： CmAnnj -CmAnn - (-1)mC：An；m例8有5个人站成一排，其中 A不站第一位，B不站第二位，C不站第三位，D不站第四位，E不站第五位，共有多少种不同的站法.解

16、析：上面两例实际上可以看成n个不同元素中有 m (mWn)错位排列的问题.而这个问题是其特殊情况，即全错位排列问题共有 A5 -C5A4 +CIA33 -C3A22 +C54A1 -C；A0=44种(注意 A0=0!=1)例9同室四人各写一张贺年卡，先集中起来.然后每人从中拿一张别人送出的贺年卡.则四张贺年卡不同的分配方式有A.6 种B.9 种C.11 种D.23 种解析：由上面公式得:a4 c4A +c：8 -c43A1 +c4a0 =9种，选择 b答案.因此可得到全错位排列的公式：n个不同元素排成一排，第一个元素不在第一位，第二个元素不在第二位，第n个元素不在第n位的排列数为：A -cnA

17、ni+cX -c3An + +（-i）nc：A这实际上是公式a -cmAni十cmwj2 此耳+ +（i）mcmAn比的特殊情况.这个公式很有用，只要有特殊元素不站特殊位置的问题，都可以用这个公式很快得到解决，希望这个公式对大家有所帮助五.圆桌排列从n个不同元素中不重复的取出 m （iMmWn）个元素排在一个圆周上，叫做这 n个不同元素的圆排列.如果一个m-圆排列旋转可以得到另一个 m-圆排列，则认为这两个圆排列是相同的.特别的，当 m = n时，n个不同元素作成的圆排列总数为（n-1）!.证明：在圆周上任选一个位置排 2_,有口种排法，再选一个位置排 22有门-1种排法，最后一个位置排n!a

18、n有1种排法.而这n个人顺时针（或逆时针）挪动 n次位置都是同一种排列.所以共有一=（n -1）!种排法. n例10有5对夫妇参加一场婚宴，他们被安排在一张10个座位的圆桌就餐，但是婚礼操办者并不知道他们彼此之间的关系，只是随机安排座位。问5对夫妇恰好都被安排在一起相邻而坐的概率是多少？（）4!种坐法，而夫妇间又可以换位置，所A.在1%o到5%o之间 B.在5%o到1%之间 C.超过1% D.不超过1%o解：5对夫妇相邻而座，可以看做是五个大元素为桌而坐，所以有.4! 2 2 2 2 229459!n个人，需要确定最终的三个“先进人物”人以共有 4. 2 2 2 2 2 0.002.故选：A.

19、例11博杰学习网竞赛小组“先进人物评比”最终圈定了选.方法是：这n个人排成一行，从第一名开始，1至3循环报数，凡报出 3的就退出，余下的向前靠拢，按此规律重复进行.直到第p次报数后，只剩下 3个人为止.试问：这剩下的三个人，分别在队伍最初的什么位置？解：设n个人的编号依次为 1,2,，n.最后剩下的三个人中，第三人的编号为bn.因bn未被淘汰，故不是3的倍数.第一次报数后淘汰了 一个人，还剩n -个人.bn向前移动了 bn-bk （k = n-"n）个人，前面 333淘汰了 bn =bn rn（rn=1,2 ）个人.故bn=3bk一rn.其中当bk为奇数时，rn =1 ；否则，rn=

20、 2,每报一次321号，人数减少-（除不尽时取整）.计算bn逐步归纳为减小的数列，最终划归到小情况.例如n =1000时，第3三个人的初始位置是 712.例12 将圆分成n ( n圭2)个扇形，现用 m ( m至2)种颜色给这些扇形染色，每个扇形恰染一种颜色 且要求相邻的扇形不同色.问有多少种不同的染色方法？解：设染色方法数为 an.(1)求初始值.当n=2时，给§染色有m种方法，给 &染色有m-1种方法.所以 a2 =m(m -1)；(2)求递推关系.给§染色有m种方法，给 &染色有m-1种方法，给S染色有m-1种方法，给Sn染色有m-1种方法.共有m(m

21、-1)n种方法.这种情况可以分为两类一类是Sn与S,不同色，此时的染色方法种数是an ；另一类是Sn与S同色，Sn与S可以合并为一个扇形，与S不同色，染色方法种数为 an.由加法原理，得到n 1an +an=m(m1)( n >2).(3)求an.构造等比数列.结论：共有an =(m1)n+(1)n(m1)种染色方法.六.转化命题对于一些较难的排列组合问题，通常采用转化命题的方法来解决.比如圆内弦的交点个数可转化为圆内接四边形的个数；异面直线的对数可转化为3倍的四面体的个数等.例13圆周上共有15个不同的点，过其中任意两点连一弦，这些弦在圆内的交点最多有多少个？分析：若两弦有交点，则两弦

22、应是圆内接四边形的对角线，即一个四边形对应一个交点.所以共有C15 =1365个交点.小结：1 . “在”与“不在”可以相互转化.解决某些元素在某些位置上用“定位法”，解决某些元素不在某些位置上一般用“间接法”或转化为“在”的问题求解2 .排列组合应用题极易出现“重”、“漏”现象，而“重”、“漏”错误常发生在该不该分类、有无顺序的问 题上.为了更好地防“重”堵“漏”，在做题时需认真分析自己做题思路，也可改变解题角度，利用一题多解核 对答案.【作业】1 .今有8个人坐圆桌，有多少种坐法？2 .有5个男孩，3个女孩围成一圆，其中 3个女孩不相邻，有多少种站法？3 . 一圆型餐桌依次有 A、B、C、

23、D、E、F六个座位，现让 3个大人和3个孩子入座进餐，要求任何两个小孩都不能坐在一起，则不同的作法总数为72 .七.用容斥原理解排列问题有些排列组合问题可转化为求集合的元素的个数来求.充分应用容斥原理：n(A IjB) =n(A) n(B) -n(ApB)n(A LB LC)=n(A) n(B) n(C) -n(ApB) -n(BDc)-n(ApB) n(AB! C).例14五人站成一排，其中甲不站第一位，乙不立第二位，共有多少种不同的站法解：这个问题在高中很多参考书上都有，有几种解法，其中一解法是用排除法：先考虑5个有的全排列,544有A5种不同的排法，然后除去甲排第一(有 A种)与乙排第二

24、(也有 A种)，但两种又有重复部分，因此多减，必须加上多减部分，这样得到共有：A -2A4 +a =78种.例15 有5个人站成一排，其中甲不站第一位，乙不站第二位，丙不站第三位，共有多少种不同的站法.仿上分析可得： A5 -3A4 +3A3 - A； =64种.八.均匀分组问题.般地：将mn个不同元素均匀分成n组(每组m个元素)，共有Cm CmCmCmn Cmn -mCm种方法.例16 有6本不同的书，按下列要求各有多少种不同的选法：(1)分给甲、乙、丙三人，每人 2本；(2)分为三份，每份2本；(3)分为三份，一份 1本，一份2本，一份3本；(4)分给甲、乙、丙三人，一人 1本，一人2本，

25、一人3本;(5)分给甲、乙、丙三人，每人至少1本.解：(1)根据分步计数原理得到：C；C2C； =90种；(2)分给甲、乙、丙三人，每人两本有Cf2C42C2种方法，这个过程可以分两步完成：第一步分为三份,每份两本，设有X种方法；第二步再将这三份分给甲、乙、丙三名同学有A；种方法.根据分步计数原理可得:c；c2c；= xC，所以 x = C62c干2 =15.A因此，分为三份，每份两本一共有15种方法.(3)这是“不均匀分组”问题，一共有C6C；C； =60种方法.653(4)在(3)的基础上再进行全排列，所以一共有C6C；C；A； =360种方法.(5)可以分为三类情况：“2、2、2型”即(

26、1)中的分配情况，有 C2C42CI =90种方法;“1、2、3型”即(4)中的分配情况，有 C6C；C；A3 =360种方法;“1、1、4型”，有C：A； =90种方法；所以，一共有 90+360+90= 540种方法.点评：本题第(3)种类型为部分均匀分组再分配，其分组总数为C&G1A2题型变换：8名球员住A、B、C三个房间，每个房间最多住 3人，有多少种住宿方法?解：A3.例17 若3名飞行员和6名特勤人员分别上 3架不同型号的直升飞机执行任务，每机一名飞行员和两名特勤人员，有多少种分配方法?解：先分组，再分配,2 2 2 1 1 1 一 一C6C4 c2 C3C2c133A F

27、 A A3 或者 c62c：c2 Cc；c；.类题：20名同学分两组，每组10人去某地社会实践，其中 6名干部，每组3人，不同分法总数是多少？ 37答案:C6与A2 .A2 A九.隔板法：将n个相同元素，分成k (n之k, n, k= N )组，可以看成是在 n个元素之间的n-1个 空隙间插入k -1块隔板.共有C：种方法.例18 将六本相同的书全部发给甲、乙、丙三人 .(1)每人至少分到一本书，问有多少种不同的分法？(2)每人不一定都分到一本书，问有多少种不同的分法？解：(1)用“隔板法”处理，六本书之间有五个空，插入两块隔板，有C；种分法；用“隔板站位法”处理，六本书之间有五个空，需插入两

28、块隔板，但由于有人可能没有书，所以两块隔板站着两个位置，加上六本书，可以看着是6+2 =8本书，分成3分，所以有CjnC： =28种分法.点评：类类题1求不定方程Xi +X2 +X3 =6的非负整数解的个数?题型变换一：四本不同的书，分给三个人，每人至少一本，全部分完，有几种分法？解：先分组，再分配有 c：a3种.题型变换二：n本不同的书，分给 n-1个人，每人至少1本，全部分完，有几种分法？解：先分组，再分配有 C12Al二种.题型变换三：n本相同的书，全部分给 m (m<n)个人.(1)每人至少分到一本书，问有多少种不同的分法？(2)每人不一定都分到一本书，问有多少种不同的分法？解：

29、(1)解法一(隔板站位法)：每人先分一本书，还剩下n-m本书，加上 m-1块隔板，可视为(n -m)+(m -1) = n -1本书，分给m个人，所以有Cm：种方法.解法二(隔板法)：n本书之间有n-1个空，需插入 m-1块隔板，所以有 Cmf种方法.(2)(隔板站位法)：n本书之间，需插入 m-1块隔板，但是，由于有人分不到书，所以 m-1块隔板站 着m-1个位置，加上n本书，可视为n+m-1本书，用m-1块隔板分成 m分，所以有Cnmm种方法(这也 是一个公式).【随堂练习】1. (1)四个不同的小球放入四个不同的盒中，一共有多少种不同的放法？(2)四个不同的小球放入四个不同的盒中且恰有一

30、个空盒的放法有多少种？解：(1)根据分步计数原理：一共有 44 =256种方法；(2)(捆绑法)第一步：从四个不同的小球中任取两个“捆绑”在一起看成一个元素有C42种方法；第二步：从四个不同的盒中任取三个将球放入有A：种方法，所以，一共有 C42 A43 = 144种方法.说明：先组合，再排列是解决问题的关键.本题亦可先将4个小球分成三组，每组分别有 1/1/ 2个，共再放入四个盒子中的三个，共有 C4C2C1 a3 =144种.A2思考：(1)四个相同的小球放入四个不同的盒子中，一共有多少种不同的放法?解：(隔板站位法)共C：+=C3=35.(2) 10个相同的小球放入编号为 1、2、3的盒

31、子中，球数不少于编号数的放法有多少种？解：按要求放6个，其余4个按隔板站位法 有C：w =C： =15种方法.另解：(隔板法)设1, 2, 3号盒子所放的千数分别为 a, b, c.则有a + b + c = 10.设乂 = 2, y=b-1, z = c-2,则方程x + y+z = 7的正整数解的组数，就是放球的方法数.所以共有22C4 H2 =C6 =15种方法.注意：这种利用“先换元，再用隔板技巧”的方法对于求有限制条件的不定方程的非负整数解的问题很有效！【总结提炼】均匀分组(不计组的顺序)问题不是简单的组合问题，如：将3个人分成3组，每组一个人，显然只有1种分法，而不是=6种.cmc

32、mcm一般地，将 m n个不同元素均匀分成 n组，有()： 一m种分法；Am十.穷举法：对于一些不能直接用两个原理，且类别不多的问题，通常采用穷举法.即列举所有情况.例19将五个市级三好学生名额和八个区级优秀学生干部名额全部分配到辖区的两所中学，每所学校至少有一个名额，有多少种不同的分配方案？解：分配情况用有序数组 (x, y)表示:(1,12), (2,11 ), (3,10), (4,9), (5,8), (6,7).然后两校交换所以共有分配方案数为 2 M(2 + 3+4十5十6+6)=52种.例20 .十一.递推法：对于一些较复杂的排列问题，可以建立排法之间的一个递推关系，通过递推关系

33、求出排法种数例19 一个楼梯共10个台阶，如果规定一步登一个台阶或登两个台阶，一共有多少种不同的走法？解：设上n级台阶的走法为an种，易知a1 =1, a2 = 2 ,当n至2时，上n级台阶的走法可分两类：第一类是最后一步跨一级，有an q种走法，第二类是最后一步跨二级，有ani种走法.由加法原理可知an=an4+an/，据此可得a10=89种不同的走法.例20 有五个人排成一列，现在要重新排列，要求都不能站在原来的位置，有几种不同排法？.设满足这解：我们考虑人数为 n的情况，即n个人排成一列，重新站队时，各人都不站在原来的位置上样的站队方式有an种，现在我们来通过合理分步，恰当分类找出递推关

34、系：第一步：第一个人不站在原来的第一个位置，有 n1种站法.第二步：假设第一个人站在第2个位置，则第二个人的站法又可以分为两类：第一类，第二个人恰好站在第一个位置，则余下的n2个人有an/种站队方式；第二类，第二个人不站在第一个位置，则就是第二个人不站在第一个位置，第三个人不站在第三个位置, 第四个人不站在第四个位置，第n个人不站在第n个位置，所以有an_1种站队方式.由分步计数原理和分类计数原理，我们便得到了数列K的递推关系式：an =(n 1)3,+an/),显然，2=0, a2=1,，a5=44.故有 44种不同排法.注意：n个人排成一排后，解散后重新排队，自己不站原来的位置的排法种数可

35、由以下公式推导得到:(1) & =0, %=1, an=(n - 1)(an* an_2)( n - 3 );(2)an1= n!1 -1!11n 1(1)-. 2! 3!n! an =a -cnA+cnx-Cn3AnE+(-1)ncnx.例21在n=<m的网格中，从(0,0)点到(n, m)点，只能沿网格的边向 x轴正方向或y轴正方向前进，问共有多少种不同的前进路线？解：对任意一个非 x轴、y轴上的点(x,y),可以从点(x,y1)走来，也可以从点(x 1,y)走来.因此,设(x, y)处的路线条数为f(x, y),则有递推公式:f(x, y) - f(x, y -1) f (

36、x -1, y).下面的推理很重要：根据上述递推公式，可得f (x, y) =cxx+y,即从x + y件物品中选出无顺序的 x件(或(x y)!y件)的总方案数.即f (x, y) = (纥.x!y!小结：上述问题中把每个f(x,y)指标在对应的坐标点处，再将坐标系顺时针旋转135°,你发现了什么？这是杨辉三角，f (x, y) =Cx4y.而我们知道，C： = CL +C：”这就是通项公式的来源.另解：记网格横向的x条线段从左至右依次为a1、a2、ax,网格纵向的y条线段从下至上依次为 b、b2、by.从(0,0)至U(x, y)的走法种数，就是为、a?、ax及b、b2、by这x+y个元素的一个N y定序排列.于是有 m (或(x+y)!)种不同走法.Ax Ayx!y!例22某地决定在一个大型广场建一个同心圆形花坛，花坛分为两部分，中间小圆部分种植草坪