“隔板法”

“隔板法”解决排列组合问题排列组合计数问题，背景各异，方法灵活，能力要求高，对于相同元素有序分组问题，采用“隔板法”可起到简化解题的功效。对于不同元素只涉及名额分配问题也可以借助隔板法来求解,下面通过典型例子加以解决。所谓隔板法，就是把隔板当成元素，再从元素里选隔板就行例1、（1）12个相同的小球放入编号为1，2，3，4的盒子中，问不同放法有多少种？（2）12个相同的小球放入编号为1，2，3，4的盒子中，问每个盒子中至少有一个小球的不同放法有多少种？（3）12个相同的小球放入编号为1，2，3，4的盒子中要求每个盒子中，要求每个盒子中的小球个数不小于其编号数，问不同的方法有多少种？解：（1）本题需要3个隔板，把3个隔板当成3个元素，共15个元素，再从15个元素里选取3个隔板，共有C153=455种（2）首先一个盒子放一小球，还剩8个小球，把8个小球放4个盒子需3个隔板，把3个隔板当成3个元素共11个元素，最后从11个元素里选3个隔板就行了，共有C113=165种。（3）先给每个盒子装上与其编号数相同的小球，还剩2个小球，2个小球装在4个盒子里需3个隔板，3个隔板看成3个元素，共5个元素，最后从5个元素里选出3个隔板就行了，共有C53=10种913111例2、（1）方程x1x2x3x410的正整数解有多少组？(2)方程x1x2x3x410的非负整数解有多少组？（3）方程2x1x2x3x103的非负整数整数解有多少组？解：（1）转化为10个相同的小球装入4个不同的盒子，每盒至少装一个，有C384种，所以该方程有84组正整数解。（2）转化为10个相同的小球装入4个不同的盒子，可以有空盒，先给每个小盒装一个，进而转化为14个相同的小球装入4个不同的盒子，每盒至少装一个，有C3286种，所以该方程有286组非负整数整数解。（3）当x10时，转化为3个相同的小球装入9个不同的盒子，可以有空盒，有C3165种。当x11时，转化为1个小球装入9个不同的盒子，可以有空盒，有C9=9种；所以该方程有165+9=174组非负整数整数解。例3、已知集合，选择的两个非空子集A,B，且A中最大的元素比B中最小的元素小，则选择方法有多少种？解：由题意知A,B的交集是空集，且A,B的并集是的子集C，所以C至少含有两个元素，将C中元素按从小到大的顺序排列，然后分为两部分，前边的给A，后边的给B，A,B至少含有1个元素，设C中有n个元素，则转化为n个相同的小球装入2个不同的盒子，则有12314151Cn种装法，故本题有C5C5C2C5C3C5C449种选择方法。总之，凡是处理与“相同元素有序分组”模型时，我们都可采用“隔板法”。若每组元素数目至少一个时，可用插“隔板”，若出现每组元素数目为0个时，向每组元素数目至少一个的模型转化，然后用“隔板”法加以解决。