论文部分内容阅读
中学数学中的排列组合是一类思考方式较为独特的问题。它对分析能力要求较高，解法也非常灵活，是高考的难点之一。因此，恰当地选择思考方法，对于解决排列组合问题至关重要。分类计数，分步计数两个原理是解决排列、组合问题的基本方法，利用该两个原理及课堂中学习的常规解法如：特殊元素、特殊位置、插空法、捆绑法等解决某些问题总感觉较难或者解答较繁。针对该现象，本文列举几例介绍解排列组合问题的非常规解题思路。
一、列举法
把符合条件的安排不重复、不遗漏的一一列举出来，是最简单、最原始但也是最基本的计数方法。教材中多次应用到，高考中也常用枚举法解决问题。
例1，某电脑用户计划使用不超过500元的资金购买单价分别为60元、70元的单片软件和盒装磁盘，根据需要，软件至少买3片，磁盘至少买2盒，则不同的选购方法有（ ）。
A、5种 B、6种 C、7种 D、8种
解析：根据所给选项数字较小，不难用枚举法解决。
单片买3张，磁盘买2盒，花费320元；单片买3张，磁盘买3盒，花费390元；单片买3张，磁盘买4盒，花费460元；单片买4张，磁盘买2盒，花费380元；单片买4张，磁盘买3盒，花费450元；单片买5张，磁盘买2盒，花费440元；单片买6张，磁盘买2盒，花费500元。故选购方式有7种，选A。
例2，从1到100的一百个自然数中，每次取出兩个数，使其和大于100，这样的取法共有多少种？
解：从1到100的一百个自然数中，每次取出两个数，其中必有一个是较小的。我们先按较小的一数枚举，而当较小的数取定以后，使和超过100的另一个相应较大的数不难一一例举，所有情况如下表：
所以共有：1+2+3+…+49+50+49+…+1=2500种不同的取法。
利用枚举法解题，直观性强，是处理排列组合问题的好方法。
二、“正难则反”
解决问题，当正面难以解决时，不妨从反面、侧面思考，顺繁则逆、正难则反。
例3，有五张卡片，他们的正反面分别写有0与1，2与3，4与5，6与7，8与9，将其中任意三张排放在一起组成三位数，共可组成多少个不同的三位数？
解析：①0不能做百位，但可以作十位或个位。②0与1在同张卡片上，因此直接分类既要考虑0又要考虑1分类较复杂。于是先不考虑任何情况算出总数，然后减去0在左边第一位的号码即为所求。由于任取三张可以组成不同的三个数的号码有：C35·23·A33，其中0在左边第一位的号码有：c；-2。-Ai，故所求的不同三位数共有：C35·23·A33-C24·22·A22=432个。
例4，从1，2，3，……，1995，这1995个自然数中，取出9个互不相邻的自然数，有多少种方法？
解析：由于符合题意的条件错综复杂，正面进攻思维受阻，此时采用反面去考虑问题。
问题相当于“9个女生不相邻地插入站成一列横队的1986个男生之间（包括首尾外侧），有多少种方法？”
任意相邻2个男生之间最多站1个女生，队伍中的男学生首尾两侧最多也可各站1个女学生，于是，这就是1987个位置中任选9个位置的组合问题，共有C91987种方法。
三、利用映射关系解题
就是运用集合的概念、逻辑语言、运算、图形来解决数学问题或非纯数学问题的思想方法。
例5，圆上有10个点，每两点连成一条线段，这些线段在圆内最多有多少个交点？以这些交点为顶点的三角形最多有多少个？
解析：该题如果用枚举法显然很困难；同样用基本极数原理先算出弦的总数，然后算出交点，在减去圆外和圆上的交点个数亦很困难，利用映射关系，化难为易。
一个交点s是由两条线段p，q相交而得，反之，依题意，两条在圆内相交的线段p，q确定一个交点s，即s与（p，q）可建立一一对应关系，两条线段p，q分别是由圆上的两对点A，B与C，D连接而成。故又可在（p，q）与（A，B，C，D）之间建立一一对应关系。因此，若令M={S|题中线段的交点}，N={（A，B，C，D}110个点中，任意四个不同的点组}，则M与N中的元素构成一一对应关系，从而有|M|=|N|但N中元素个数显然为C410=210，所以题中交点为210个。同样的考虑，圆内一个三角形与圆上6个点之间构成一一对应关系，因此，题中所求三角形的个数为C610=210个。
四、利用递推关系解题
例6，有一楼梯共10级，每步只能跨上1级或2级，问要登上最后一级共有多少种走法？
解析：因为每步只能跨上1级或2级，所以最后一步可能从第9级也可能从第8级跨上第10级，向前递推关系不变。设登上第k级有ak种走法，显然a1=1，a2=2，当k>2时，登上第k级台阶的走法可以分两种情况得到：从第k-1级台阶跨一级登上第k级，或从第k-2级台阶，一步跨两级登上第k级。故当k≥3时，有ak=ak-1+2k-2。
∴a10=a9+a8=2a8+a7=……=34a2+21a1=89 例7，把圆分成10个不相等的扇形，并且用红、黄、蓝三种颜色给扇形染色，但不允许相邻的扇形有相同的颜色，问共有多少种染色法？
解析：前9个扇形依次染色并不难，但第10个扇形既与第九个相邻也与第1个相邻，这两个扇形颜色可能相同也可能不相同，所以直接用记数原理有困难，但建立递推关系并不难。
设将圆分成n个不相等的扇形时，满足题设的染法有an种。依次记n个扇形为s1，……sn。显然a1=3，当n=2时，先对s1染色，有3种方法；s1染色后再对s2染色，有2种方法，故a2=6，当n≥3时，我们依次对s1，s2，……sn染色。对s1染色，有3种方法，对s1染色后再对s2染色有2种方法，同样的对s3，s4……，sn分别有2种方法，由乘法原理共有3·2n-1种染色方法。但这样做sn与s1有可能同色。即在3·2n-种染色方法中包含了sn与s1同色的染色方法。对于sn与s1同色的情形，拆去sn与s1的边界使sn与s1合并，便得到将圆分为n-1个扇形时，同色不相邻的染色方法，这样的情况有an-1种。故an=3·2n-1-an-1（n≥3）。所以a10=3·29-a9=3·29-3·28+a8=3·29-3·28+3·27-a7=……=3.29-3.28+3.27-3.26+3.25-3·24+3·23-3·22+3.21=210+2=1026。
五、利用对称性解题
对称是美的一种形式，对称思想在数学中有广泛的应用，挖掘数学问题中隐含的对称性，运用对称思想解题，往往得到出人意料的简捷解法。
例8，A，B，C，D，E五人站成一排，若B必须站在A的右边（A，B可以不相邻）的不同站法有（ ）。
A、24種 B、60种 C、90种 D、120种
解：∵B站在A的右边与B站在A的左边一样多，由对称分析得1/2A55=60种，选B。
应用对称性简捷明快，给人以美的享受。
六、利用不等式（方程）组解题
在解决某些数学问题时，先设定一些未知数。然后把它们当作已知数，根据题设本身各量间的制约，列出等式，解方程即可。
例9，一个口袋内有4个不同的红球，6个不同的白球，若取一个红球记2分，取一个白球记1分，从中任取5个球，使总分不少于7分的取法有多少种？
例10，将10个完全相同的小球放人编号为1，2，3的三个盒子内，要求放入盒子的球数不小于它的编号数，则不同的放法有（ ）。
A、20种 B、15种 C、14种 D、12种
解：设编号为1，2，3的三个盒子中分别放入x，y，z个小球，于是题中不同的放法即为方程：x+y+z=10，且x≥1，y≥2，z≥3的非负整数解的个数。令u=x-1，v=y-2，w=z-3，得u+v+w=4，所以该方程的非负整数解的个数即为所求的放法数目C44+3+1=15，故选B。
七、等价转换、构造模型解题
例11，马路上有编号为1，2，3，4，5，6，7，8，9的九只路灯，现要关掉其中的3盏，但不能关掉相邻的2盏或3盏，也不能关掉两端的2盏，求满足条件的关灯方法有多少种？
解：把此问题当作一个排队模型：在6盏亮灯的5个空隙中插入3盏熄灯有C35种。
例12，某排共有10个座位，若4人就坐，每人左右两边都有空位，那么不同的坐法有多少种？
解：等价于4人插5空模型：A45。
一些不易理解的排列组合题，如果能转化为非常熟悉的模型，如占位填空模型、排队模型、装盒模型等，可使问题直观解决！
八、多排问题改为直排解题
一般地，元素分成多排的排列问题，可归结为一排考虑，再分段研究。
例13，8人排成前后两排，每排4人，其中甲乙在前排，丁在后排，共有多少排法？
解：8人排前后两排，相当于8人坐8把椅子，可以把椅子排成一排。先在前4个位置排甲乙两个特殊元素有A24种，再排后4个位置上的特殊元素有A14种，其余的5人在5个位置上任意排列有A55q种，则共有A24A14A53种。
学习数学的过程是知识建构的过程，是思维训练的过程。本文列举了几种特殊的解题方法，归纳规律，构造数学模型，掌握分类的数学思想和化归的方法。
一、列举法
把符合条件的安排不重复、不遗漏的一一列举出来，是最简单、最原始但也是最基本的计数方法。教材中多次应用到，高考中也常用枚举法解决问题。
例1，某电脑用户计划使用不超过500元的资金购买单价分别为60元、70元的单片软件和盒装磁盘，根据需要，软件至少买3片，磁盘至少买2盒，则不同的选购方法有（ ）。
A、5种 B、6种 C、7种 D、8种
解析：根据所给选项数字较小，不难用枚举法解决。
单片买3张，磁盘买2盒，花费320元；单片买3张，磁盘买3盒，花费390元；单片买3张，磁盘买4盒，花费460元；单片买4张，磁盘买2盒，花费380元；单片买4张，磁盘买3盒，花费450元；单片买5张，磁盘买2盒，花费440元；单片买6张，磁盘买2盒，花费500元。故选购方式有7种，选A。
例2，从1到100的一百个自然数中，每次取出兩个数，使其和大于100，这样的取法共有多少种？
解：从1到100的一百个自然数中，每次取出两个数，其中必有一个是较小的。我们先按较小的一数枚举，而当较小的数取定以后，使和超过100的另一个相应较大的数不难一一例举，所有情况如下表：
所以共有：1+2+3+…+49+50+49+…+1=2500种不同的取法。
利用枚举法解题，直观性强，是处理排列组合问题的好方法。
二、“正难则反”
解决问题，当正面难以解决时，不妨从反面、侧面思考，顺繁则逆、正难则反。
例3，有五张卡片，他们的正反面分别写有0与1，2与3，4与5，6与7，8与9，将其中任意三张排放在一起组成三位数，共可组成多少个不同的三位数？
解析：①0不能做百位，但可以作十位或个位。②0与1在同张卡片上，因此直接分类既要考虑0又要考虑1分类较复杂。于是先不考虑任何情况算出总数，然后减去0在左边第一位的号码即为所求。由于任取三张可以组成不同的三个数的号码有：C35·23·A33，其中0在左边第一位的号码有：c；-2。-Ai，故所求的不同三位数共有：C35·23·A33-C24·22·A22=432个。
例4，从1，2，3，……，1995，这1995个自然数中，取出9个互不相邻的自然数，有多少种方法？
解析：由于符合题意的条件错综复杂，正面进攻思维受阻，此时采用反面去考虑问题。
问题相当于“9个女生不相邻地插入站成一列横队的1986个男生之间（包括首尾外侧），有多少种方法？”
任意相邻2个男生之间最多站1个女生，队伍中的男学生首尾两侧最多也可各站1个女学生，于是，这就是1987个位置中任选9个位置的组合问题，共有C91987种方法。
三、利用映射关系解题
就是运用集合的概念、逻辑语言、运算、图形来解决数学问题或非纯数学问题的思想方法。
例5，圆上有10个点，每两点连成一条线段，这些线段在圆内最多有多少个交点？以这些交点为顶点的三角形最多有多少个？
解析：该题如果用枚举法显然很困难；同样用基本极数原理先算出弦的总数，然后算出交点，在减去圆外和圆上的交点个数亦很困难，利用映射关系，化难为易。
一个交点s是由两条线段p，q相交而得，反之，依题意，两条在圆内相交的线段p，q确定一个交点s，即s与（p，q）可建立一一对应关系，两条线段p，q分别是由圆上的两对点A，B与C，D连接而成。故又可在（p，q）与（A，B，C，D）之间建立一一对应关系。因此，若令M={S|题中线段的交点}，N={（A，B，C，D}110个点中，任意四个不同的点组}，则M与N中的元素构成一一对应关系，从而有|M|=|N|但N中元素个数显然为C410=210，所以题中交点为210个。同样的考虑，圆内一个三角形与圆上6个点之间构成一一对应关系，因此，题中所求三角形的个数为C610=210个。
四、利用递推关系解题
例6，有一楼梯共10级，每步只能跨上1级或2级，问要登上最后一级共有多少种走法？
解析：因为每步只能跨上1级或2级，所以最后一步可能从第9级也可能从第8级跨上第10级，向前递推关系不变。设登上第k级有ak种走法，显然a1=1，a2=2，当k>2时，登上第k级台阶的走法可以分两种情况得到：从第k-1级台阶跨一级登上第k级，或从第k-2级台阶，一步跨两级登上第k级。故当k≥3时，有ak=ak-1+2k-2。
∴a10=a9+a8=2a8+a7=……=34a2+21a1=89 例7，把圆分成10个不相等的扇形，并且用红、黄、蓝三种颜色给扇形染色，但不允许相邻的扇形有相同的颜色，问共有多少种染色法？
解析：前9个扇形依次染色并不难，但第10个扇形既与第九个相邻也与第1个相邻，这两个扇形颜色可能相同也可能不相同，所以直接用记数原理有困难，但建立递推关系并不难。
设将圆分成n个不相等的扇形时，满足题设的染法有an种。依次记n个扇形为s1，……sn。显然a1=3，当n=2时，先对s1染色，有3种方法；s1染色后再对s2染色，有2种方法，故a2=6，当n≥3时，我们依次对s1，s2，……sn染色。对s1染色，有3种方法，对s1染色后再对s2染色有2种方法，同样的对s3，s4……，sn分别有2种方法，由乘法原理共有3·2n-1种染色方法。但这样做sn与s1有可能同色。即在3·2n-种染色方法中包含了sn与s1同色的染色方法。对于sn与s1同色的情形，拆去sn与s1的边界使sn与s1合并，便得到将圆分为n-1个扇形时，同色不相邻的染色方法，这样的情况有an-1种。故an=3·2n-1-an-1（n≥3）。所以a10=3·29-a9=3·29-3·28+a8=3·29-3·28+3·27-a7=……=3.29-3.28+3.27-3.26+3.25-3·24+3·23-3·22+3.21=210+2=1026。
五、利用对称性解题
对称是美的一种形式，对称思想在数学中有广泛的应用，挖掘数学问题中隐含的对称性，运用对称思想解题，往往得到出人意料的简捷解法。
例8，A，B，C，D，E五人站成一排，若B必须站在A的右边（A，B可以不相邻）的不同站法有（ ）。
A、24種 B、60种 C、90种 D、120种
解：∵B站在A的右边与B站在A的左边一样多，由对称分析得1/2A55=60种，选B。
应用对称性简捷明快，给人以美的享受。
六、利用不等式（方程）组解题
在解决某些数学问题时，先设定一些未知数。然后把它们当作已知数，根据题设本身各量间的制约，列出等式，解方程即可。
例9，一个口袋内有4个不同的红球，6个不同的白球，若取一个红球记2分，取一个白球记1分，从中任取5个球，使总分不少于7分的取法有多少种？
例10，将10个完全相同的小球放人编号为1，2，3的三个盒子内，要求放入盒子的球数不小于它的编号数，则不同的放法有（ ）。
A、20种 B、15种 C、14种 D、12种
解：设编号为1，2，3的三个盒子中分别放入x，y，z个小球，于是题中不同的放法即为方程：x+y+z=10，且x≥1，y≥2，z≥3的非负整数解的个数。令u=x-1，v=y-2，w=z-3，得u+v+w=4，所以该方程的非负整数解的个数即为所求的放法数目C44+3+1=15，故选B。
七、等价转换、构造模型解题
例11，马路上有编号为1，2，3，4，5，6，7，8，9的九只路灯，现要关掉其中的3盏，但不能关掉相邻的2盏或3盏，也不能关掉两端的2盏，求满足条件的关灯方法有多少种？
解：把此问题当作一个排队模型：在6盏亮灯的5个空隙中插入3盏熄灯有C35种。
例12，某排共有10个座位，若4人就坐，每人左右两边都有空位，那么不同的坐法有多少种？
解：等价于4人插5空模型：A45。
一些不易理解的排列组合题，如果能转化为非常熟悉的模型，如占位填空模型、排队模型、装盒模型等，可使问题直观解决！
八、多排问题改为直排解题
一般地，元素分成多排的排列问题，可归结为一排考虑，再分段研究。
例13，8人排成前后两排，每排4人，其中甲乙在前排，丁在后排，共有多少排法？
解：8人排前后两排，相当于8人坐8把椅子，可以把椅子排成一排。先在前4个位置排甲乙两个特殊元素有A24种，再排后4个位置上的特殊元素有A14种，其余的5人在5个位置上任意排列有A55q种，则共有A24A14A53种。
学习数学的过程是知识建构的过程，是思维训练的过程。本文列举了几种特殊的解题方法，归纳规律，构造数学模型，掌握分类的数学思想和化归的方法。