资源描述：
《排列组合中分球入箱问题解法探究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、联系方式：手机013852615202E-mail:tz_zyj@163.com职称:中学一级详细地址：江苏泰州机电高等职业技术学校邮编：225300排列组合中分球入箱问题解法探究周勇俊江苏泰州机电高等职业技术学校（225300）例：（分球入箱）n个相同的球放入k个不同的箱子屮：（1）不允许有空箱,有多少种不同的方法？（2）允许有空箱，有多少种不同的方法？教材解法：（1）应用穷举法屮的对应法：无空箱，把n个球排成一列，屮间有n-l个空隙，现在用k-1块隔板把它隔成k份，求可能的隔法，这是n-l取k
2、-1的组合，因此方法总数C,：：。（2）因为允许有空箱，可以把n个球与k-l个隔板等同看待，认为共计冇n+k-1个元素，然后用k-1块隔板把它隔成k份求可能的隔法，这是n+k-1取k-1的组合，因此方法总数C：；；」。笫二问的解法学生很难理解，笔者认为此问题可以用以下三种方法来解：方法一：利用求不定方程正整数解引例：〈1〉求满足方程坷+勺+…+耳二斤S为正整数且n>k）的止整数解（和％2,…，无）的个数;<2）求满足方程州+兀2+・・・+忑=n（n为正整数且n>k）的非负整数解（兀1，兀2,…，无
3、）的个数。解：〈1〉n二1+1+・・・+1（n个1相加），用k-1个分隔符把n个1分成n段，每一个分隔方法对应一个解；n个1之间冇n-l个空隙，在其屮任选k-1处插入分隔符，冇C：：种方法，故方程共冇C：：个解。〈2〉方程的非负整数解，则州,兀2，・「勺屮可以取零的，但最多有k-1个为零，故可分为以下k类情况來讨论：联系方式：手机013852615202E-mail:tz_zyj@163.com职称:中学一级详细地址：江苏泰州机电高等职业技术学校邮编：225300排列组合中分球入箱问题解法探究周勇
4、俊江苏泰州机电高等职业技术学校（225300）例：（分球入箱）n个相同的球放入k个不同的箱子屮：（1）不允许有空箱,有多少种不同的方法？（2）允许有空箱，有多少种不同的方法？教材解法：（1）应用穷举法屮的对应法：无空箱，把n个球排成一列，屮间有n-l个空隙，现在用k-1块隔板把它隔成k份，求可能的隔法，这是n-l取k-1的组合，因此方法总数C,：：。（2）因为允许有空箱，可以把n个球与k-l个隔板等同看待，认为共计冇n+k-1个元素，然后用k-1块隔板把它隔成k份求可能的隔法，这是n+k-1取k-
5、1的组合，因此方法总数C：；；」。笫二问的解法学生很难理解，笔者认为此问题可以用以下三种方法来解：方法一：利用求不定方程正整数解引例：〈1〉求满足方程坷+勺+…+耳二斤S为正整数且n>k）的止整数解（和％2,…，无）的个数;<2）求满足方程州+兀2+・・・+忑=n（n为正整数且n>k）的非负整数解（兀1，兀2,…，无）的个数。解：〈1〉n二1+1+・・・+1（n个1相加），用k-1个分隔符把n个1分成n段，每一个分隔方法对应一个解；n个1之间冇n-l个空隙，在其屮任选k-1处插入分隔符，冇C：：种
6、方法，故方程共冇C：：个解。〈2〉方程的非负整数解，则州,兀2，・「勺屮可以取零的，但最多有k-1个为零，故可分为以下k类情况來讨论：第一类,当西，兀2,…，无中全不为零，问题转化为旺+%2+•••+Xk=/I的正整数解个数，共冇cd个；第二类，当西宀，…,耳屮有一个为零，不妨设X,=0,问题转化为x2++•••+xk=n的正整数解个数,共有个。故当兀］，兀2,…,H中有一个为零时方程共有C：C,：：个解；第三类，当西,兀2,…,"中冇两个为零，不妨设X,=x2=0,问题转化为心+兀+・・・+忑二
7、〃的正整数解个数，共冇C,：；个。故当心吃，…，耳中冇两个为零吋方程共有ClC^个解；依次类推：第k-1类,当西,兀2,…，嫌中有k-1个为零,不妨设X［二兀2=…耳产。，问题转化为X,=/7的止整数解个数，共有匚紅个。故当心兀2,…入中有两个为零时方程共有C「C紅个解。曲加法原理，满足方程禹+兀2+…+耳=n（n为正整数且n>k）的非负整数解（W••心）的个数为C：C：；+C：C,：：+C：缶+…疔1C紅=c,f设第只箱子里有尢a=i,2,…,上）个球，问题（1）化为求方程兀］+兀2+…+忑二斤
8、的正整数解（兀］,尤2,…，忑）的个数，故方法种数为C：；；问题（2）化为求方程西+勺+…+耳=〃的非负整数解的个数，故方法种数为厂上・11°方法二：利用黑白球排列问题引例：（a）n个相同的白球和m个相同的黑球排成一列，要求任意两个黑球不能相邻，且黑球不能排在首末位置，共有多少种排法？（b）n个相同的口球和m个相同的黑球排成一列，共有多少种排法？解：（a）采用插入法。先把n个相同的白球排成一列，因为黑球不能相邻且不能排在首末位置，故只能从口球产生的n-l个空隙中选ni个位置给黑球，
