福建--郑定华--聚焦四类排列组合问题的公式化解法

1排列组合与数列的融合问题福建省南平市高级中学郑定华353000电子邮箱[e-mail]对于下列四类排列组合问题，当所涉及的数量较大时，仅从排列组合知识入手，相当棘手，与数列有机融合，解法优越，并且所涉及的数量越大，优越性就越大．问题13mm个人传球，第一次球从甲传出，到第n3n次球又回到甲手中的传递方式有多少种？解析用na表示到第n2n次球又回到甲手中的不同的传递方式数．当2n时，第一次球从甲传出，甲可以传给其余1m人之中的任意一个，所以有1m种不同的传递方式，在第二次传球中，传球者不是甲，所以他可以把球传给甲，且仅有一种传递方式，由分步计数原理知，1m11ma2．当2n时，第一次球从甲传出，在n次传球中，每次传球都有1m种不同的传递方式，所以传球1n次后，共有1n1m种不同的传递方式．这些不同的传递方式可分为两类：第一类是到了第1n次，球又回到甲手中，共有1na种；第二类是到了第1n次，球没回到甲手中，共有1n1na1m种．只有传球者不是甲时，才能将球传给甲，所以要使第n次球又回到甲手中，则第n次传球时，传球者必须来自第二类，并且他传给甲的方式只有1种，所以到了第n次，球又回到甲手中的传递方式有1n1nna1ma种，由此可解得m1m11mannn．例1三人踢毽子，互相传递，每人每次只能踢一下，由甲开始踢，经过4次传递后，毽子又被传递给甲，则共有种不同的传递方法？解因为3m，4n，所以共63212a444种问题2用3mm种颜色给环形排列的n3n个平面区域染色，每一个区域染上一种颜色，且相邻的两区域异色，共有多少种不同的染色方法？解析用1A、2A、3A、…、nA分别表示这n个平面区域，用na表示不同的染色方法数．2当3n时，依次对区域1A、2A、3A染色，由分步计数原理知，1m1m2m1mma33当3n时，依次对1A、2A、3A、…、nA染色，1A有m种染法，2A、3A、4A、…、nA各有1m种染法，所以一共有1n1mm种染法，这些染法分成两类：一类染法是nA与1A的颜色不同，共有na种方法，另一类是nA与1A染成同种颜色，此时，将nA与1A合并成一个区域，这样一来，就构成了用3mm种颜色给环形排列的1n个平面区域染色，每一个区域染上一种颜色，且相邻的两个区域异色的染法，共有1na种方法．于是知1n1nn1mmaa由此可解得1m11mannn例2（2015•青岛模拟）如图所示的五个区域中，中心区域是一幅图画，现有要求在其余四个区域中涂色，现有四种颜色可供选择．要求每一个区域只涂一种颜色，相邻区域所涂颜色不同，则不同的涂色方法种数为()A．64B．72C．84D．96解因为4nm，所以共有84313a444种问题3一楼梯共*Nn,1nn阶，某人上楼时，可以一步上一阶，也可以一步上两阶，该人共有种不同的上楼方法？解析设上到第n阶不同的走法为na种，则易知11a，22a．当2n时，要上到第n阶，可以分两类：第一类，第一步上一阶，要上到第n阶，还要上1n阶，所以有1na走法；第二类，先一步上两阶，要上到第n阶，还要上第2n阶，这有2na走法．于是得21nnnaaa（此为裴波那契数列的递推公式）．运用递推数列通项公式的求法，可得：31125125155nnna因为11a，22a，所以，当n的值较小时求na，用递推关系21nnnaaa更简便：1，2，3，5，8，13，21，……．例3一层楼梯共12阶，某人可以一次上一阶楼梯，也可以一次上两阶楼梯，该人共有多少种不同的上楼方法？解根据11a，22a，且当2n时，21nnnaaa，可得33a，54a……23312a问题4将编号为1，2，…，n的n个球随机装入编号为1，2，…，n的n个盒子，每个盒子装一球，球的编号与盒子的编号都不相同的装法有多少种？nkknkna2!1!种．解析设所有的球都装错盒子的方法共有na种，易知01a，12a．当2n时，可以分两步完成：第一步，将第n号球装入一个盒子，共有n-1种错装方法；第二步，考虑其余n-1个球错装方法．在第一步中，设第n号球被装入第k号盒子，此时：（1）若第k号球被装入第n号盒子，则只需考虑剩下的2n球的错装方法，共有2na种方法；（2）若第k号球未被装入第n号盒子，就把第n号盒子当作第k号盒子（说明：原第k号盒子装着第n号球，不用再考虑它），则问题就相当于1n球都装错盒子，共有1na种方法．于是知，2111nnnanana*,2Nnn，由此可得nkknkna2!1!例4某人写了6封信，并在6个信封上写下了对应的地址和收信人姓名，他把6封信随机装入信封，每个信封装一封信，则有且仅有两封信装对的情况共有多少种？解6封信中，有2封信装对信封，其余4信封全装错信封．其中，有2封信装对信封的情况有15C26，其余4信全都装错信封的情况共有96!k1!4a42kk4种．135915种．