插空法在排列组合中的应用.docVIP

插空法在排列组合中的应用经过近几年的学习总结，在解排列组合题时，有些题常常使人百思不得其解，而且做后还不知道对与错，原因是在解排列组合题时，往往会出现重复与遗漏，而对于一些分类讨论的问题，更是使人头痛。因此我积累前人研究的结果，把一些分类讨论的排列组合是，用一种简单而易懂的方法插空法来解决，希望会对广大高考考生有所帮助。下面就通过几个例子加以说明。例方程的正整数解有多少个？分析：（方法一）：我们可能用分类讨论的办法来解决，可以分为这样的几类：分为（4，1，1）（意思就是为4，1，1中的一个），这样共有3种可能；分为（3，2，1），共有6种可能（因为是3个不同的元素的一个排列）；分为（2，2，2）有1种可能。共有10种。显然这种方法，当数字很大时就很容易遗漏，出错的可能很大，而且很麻烦，因此我采取下面的方法：（方法二）：我把6个数看成是不可区分的6个数，分别用符号“”来表示排成一列，即，然后用2个挡板插入上面“”之间的空隙，将其分成3分，那么挡板的一种插法即对应着方程的一种解。例如：|的意思就是，而|的意思就是等等，这样就共有10种（因为有5个空隙，两个相同的挡板），显然这种方法简单易行，而且不容易出错。是数学化归思想的一种。再如下面的例子。例2 8封相同的信放入4个不同的信箱中，要求每个信箱至少1封，共有多少种不同的放法？分析：有了上一题所讲的方法，本题也应该不难解决，他们实际上有本质的联系。只要把8封相同用符号“”来表示并排成一列，即，然后用3个挡板插入其中的7个空隙之间，（例如：|的意思就是第一个信箱3封，第二个信箱1封，第三个信箱2封，第四个信箱2封），这样共有种不同的放法。如果本题用分类讨论的办法就很麻烦，但也不是不可行，同样可以解决，只是相比之下应用插空法要简单得多。类似的还有如下问题：例3 要从弥勒县的4所县级中学选出6人去参加数学竞赛，每校至少有1人，这6个名额有多少种不同分配方法？分析：同样，因为“名额”之间无差别，可把6个名额用符号“”来表示，然后用3个挡板去插入其中5个空隙间，共有10种不同的分配方法。到此本应该结束了，但从上面的问题中可以看出，上面的问题中都有一个至少的问题在里面，如果去掉这个条件，情况又如何。我们再来看看下面的问题：例4 方程的非负整数解有多少个？例5 8封相同的信放入4个不同的信箱中，共有多少种不同的放法？例6 要从弥勒县的4所县级中学选出6人去参加数学竞赛，这6个名额有多少种不同分配方法？下面就来解决上面的三个问题。如果我们用分类讨论的办法来解决例4，当然可以分为这样的几类：（6，0，0）；（5，1，0）；（4，2，0）；（4，1，1）；（3，3，0）；（3，2，1）；（2，2，2）。所以共有366336128种。这样解决易错，而且很繁锁，同样我们可以把6看成是6个不可区分的6个1，分别用符号“”来表示，然后也用2个挡板放入其中，现在就不是插入5个空位，而且要把两个挡板也当作元素来对待，只不过是不同于元素“”的元素，这样就一共有8个元素。（例如：“| |”这个的意思就是， “|”这个的意思就是等等），也就是8个元素有6个相同与另两个相同的一个排列，所以共有28种。同样的方法，在例5中，把8封相同的信用符号“”表示排成一列，然后用3个挡板放入其中，连同8个“”共有11个元素，根据排列组合的知道，可得结果是165种。例6的结果为84种从上面我们可以得出一般情况，把n封相同的信放入m（nm）个不同的信箱中，每个信箱至少一封信的放法有种。如果是把n封相同的信放入m