排列组合问题以其特有的魅力吸引着人们对它的研究, 很多问题都来源于生活而且老少皆宜, 不需要什么前备知识, 小学生也能乐在其中, 困在其中.
组合问题研究的是从一组对象中选择一定数量的对象的方式数问题.
组合数是指在不考虑顺序的情况下, 从给定的对象集合中选择若干个对象的方法数.
比如从某班人中任选 人参加学生代表大会, 有多少种选择方式数呢？ .
接下来我们来思考一个经典的球罐模型问题：
将 个相同的小球放入三个颜色分别为红色、黄色和蓝色的罐子中. 如果每个罐子至少要有一个球, 那么有多少种方式可以将小球放到罐子里呢？
如果允许有空罐子, 这个问题又该怎么思考呢？
没有空罐
我们将个相同的小球排成一排, 如图所示,
由于不能有空罐子, 因此每个罐子至少得有一个球. 由于小球都是相同的, 那么如何将小球分隔成份分别放入罐子中呢？这个高级的工具就是隔板.
个小球互相之间有个间隔, 任意选择个间隔分别插入一块红色隔板, 便将个小球分成了份：第一块隔板左侧的小球, 第一块和第二块隔板之间的小球, 第二块隔板右侧的小球.
如图, 就是一种分配方案, 依次将份小球放入红黄蓝个罐子, 红黄蓝罐子则分别有个小球.
按照这样的操作方法, 只在小球的间隔之间放入隔板, 并且两块隔板不能相邻, 那么每一种隔板的放置方法都对应一种小球的分配方法, 同样的, 每一种小球的分配方法都能找到对应的隔板的放置方法,
所以小球的分配方法数就是计算隔板的放置方法数, 那么总共有多少种放置隔板的方法呢？
在个位置中任意选择两个位置放置隔板, 共有种方法数.
如果我们设3个罐子中的小球数分别是, 那么这里的球罐模型问题对应的数学问题就是求不定方程有多少个正整数解的问题.
也就是说方程的正整数解的个数为.
一般的, 将个相同的小球分配到个不同的罐子中, 不允许有空罐子, 则共有种方式.
有空罐
将条件从“不能有空罐子”改成“允许有空罐子”, 这个问题还能像上文那样思考吗？肯定要有变化, 但不变的是同样的个相同的小球, 要分成3份, 隔板工具仍旧可以用.
只是现在允许有空罐子, 上文中的隔板放置的位置就要有变化.
同样需要两块隔板将小球分成份. 为了能出现空罐子, 因此隔板可以相邻放置, 这样对应的就是中间的一份小球数为, 也就是黄色罐子是空的.
隔板也可以放置到第一个小球的左侧, 对应的是红色罐子是空的,
当然隔板也可以放置到最后一个小球的右侧, 这样蓝色罐子就是空的.
所以现在隔板不能在小球放好后再插入到小球的间隔中了, 应该与小球同时放置, 也就是个小球与块隔板共需要个位置, 其中两个位置放隔板, 剩下个位置放小球.
按照这样的操作方法分配, 一旦隔板挑选个位置放好以后, 自然的就将小球分成了份, 也就是对应一种小球的分配方法, 同样的, 每一种小球的分配方法都能找到对应的隔板的放置方法, 那么总共有多少种放置隔板的方法呢？
在个位置中任意选择两个位置放置隔板, 共有种分配方案.
同样的, 如果我们设3个罐子中的小球数分别是, 那么这里的球罐模型问题对应的数学问题就是求不定方程有多少个非负整数解的问题.
也就是说方程的非负整数解的个数为.
一般的, 将个相同的小球分配到个不同的罐子中, 允许有空罐子, 则共有种方式.
所以, 同样一个球罐模型问题, 允许有空罐子, 不允许有空罐子, 条件一字之差, 计算方法可以差之毫厘, 谬以千里.
