分球入盒问题的分类讨论

《分球入盒问题的分类讨论》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、分球入盒问题的分类讨论214046无锡旅游商贸高等职业技术学校许震宇分球入盒问题是组合数学中的一个典型问题，即把m个球放入n个盒中，求放法种数．因为需要考虑小球是否相同、盒子是否相同、当时是否允许盒子为空、当时是否允许一盒容纳多球，现将分球入盒问题进行分类讨论．1当时，m个相同的球放入n个盒中等价于正整数m分拆成n个自然数的和．定义1把正整数m表示成n个自然数的和，叫做m的一个分拆，每一个数称为分拆的一个分部，有n个分部的分拆称为n分拆．若分拆的全为正整数，则称为m的正定n分拆；若分拆的全为非负整数，则称为m的半正定n分拆．若分拆与的顺序无关，则称为m的无序n分拆；若分

2、拆与的顺序有关，则称为m的有序n分拆．1.1当时，m个相同的球放入n个相同的盒中，盒子不能为空等价于正整数m的无序正定n分拆．用表示m的无序正定n分拆的总数，显然有，，，．用表示所有m的无序正定分拆的总数，即．定理1当时，m个相同的球放到n个相同的盒中，盒子不能为空，放法种数为．证明可以这样考虑，先在n个盒中各放入1个球，再把剩余的个相同的球放入n个相同的盒中的1个盒子，或者其中的2个盒中且无空盒，…，或者全部的n个盒中且无空盒，这就等价于所有的分成至多n个分部的无序正定分拆，总数为．1.2当时，m个相同的球放入n个相同的盒中，盒子可以为空等价于正整数m的无序半正定n分

3、拆，放法种数为．证明可分为n类：第1类，空盒数为n-1，即m个相同的球放入n个相同盒中的1个盒子，有种放法；第2类，空盒数为n-2，即m个相同的球放入其中的2个盒中且无空盒，有种放法；…；第n类，空盒数为0，即m个相同的球放入n个盒中且无空盒，有种放法，根据加法原理，所有的放法种数为．1.3当时，m个相同的球放入n个不同的盒中，盒子不能为空等价于正整数m的有序正定n分拆，放法种数为．证明用挡板法，将m个相同的球排成一排，m球之间的m-1个空隙放入n-1个挡板，从而分成n份，分别对应n个不同盒，故有种放法．1.4当时，m个相同的球放入n个不同的盒中，盒子可以为空等价于正整

4、数m的有序半正定n分拆，放法种数为．证明1可分为n类：第1类，空盒数为0，即m个相同的球放入n个不同的盒中且无空盒，有种放法；第2类，空盒数为1，即m个相同的球放入其中的n-1个盒中且无空盒，有种放法；…；第n类，空盒数为n-1，即m个相同的球放入其中的1个盒中，有种放法，故所有的放法种数为．证明2可以这样考虑：若先在n个盒中各放入1个相同的球，则等价于把m+n个相同的球放到n个不同的盒中且无一空盒，根据定理1.3，放法种数为．2当时，m个不同的球放入n个盒中等价于m元集分划成n个两两互斥的子集的并．定义2设是m元集的一族子集，如果满足：(1)两两不交；(2)，则称子集

5、族是集A的一个分划，每个子集称为分划的一个分块，有n个分块的分划称为n分划．若分划的中无一空集，则称为m元集A的非空n分划；若分拆的中允许有空集，则称为m元集A的可空n分划．若分划与的顺序无关，则称为m元集A的无序n分划；若分拆与的顺序有关，则称为m元集A的有序n分划．2.1当时，m个不同的球放入n个不同的盒中，盒子可以为空等价于m元集A的有序可空n分划，放法种数为．证明根据球数分成m步，每球可放入n个盒中的任一个，故有种放法．2.2当时，m个不同的球放入n个不同的盒中，盒子不能为空等价于m元集A的有序非空n分划．用表示m元集A的有序非空n分划的总数，显然．定理2当时，

6、m个不同的球放入n个不同的盒中，盒子不能为空，放法种数等于．证明记事件A：m个不同的球放入n个不同的盒中且无一空盒，方法种数等于m元集A的有序非空n分划的总数；记事件：m个不同的球放入n个不同的盒中且盒子可以为空，有种放法，记事件：m个不同的球放入其中的n-1个盒中且盒子可以为空，有种放法，……记事件：m个不同的球放入其中的1个盒中，有种放法，根据容斥原理，，故A所有的放法种数为．特别地，推论．证明m个不同的球放入n个不同的盒中，盒子可以为空，放法种数为，可分为n类：第1类，空盒数为0，即m个不同的球放入n个不同的盒中且无空盒，有种放法；第2类，空盒数为1，即m个不同的

7、球放入其中的n-1个盒中且无空盒，有种放法；…；第n类，空盒数为n-1，即m个不同的球放入其中的1个盒中，有种放法，根据加法原理，故所有的放法种数为．2.3当时，m个不同的球放入n个相同的盒中，盒子不能为空等价于m元集A的无序非空n分划，放法种数为．证明m个不同的球放入n个不同的盒中且无空盒，方法种数为，可以分成2步完成：第1步，把m个不同的球放入n个相同的盒中且无空盒，其放法种数记为X；第2步，把n个相同的盒标上不同记号，共有种方法，根据乘法原理，，故有．2.4当时，m个不同的球放入n个相同的盒中，盒子可以为空等价于m元集A的无序可空n