数论经典习题系列之求重集组合数（一）

2018-10-18  本文已影响0人  汪汪小增

title: 数论经典习题系列（一）
categories:

经典练习题

例题1

n个没有区别的球放入r个有标志的盒子里面（n>=r）,每个盒子只允许放一个球，请问有多少种放法？

每个盒子只能放一个球，所以方法为排列数，P（n，r）;

例题2

n个没有区别的球放入r个有标志的盒子里面（n>=r）,每个盒子至少放一个球，请问有多少种放法？

方法一

分两个步骤完成：

（1）首先每个盒子放一个球，因为球是没有区别的，所以这样的方法是1

（2）然后再n-r个球放到r个盒子里面，每个盒子放置的球数没有限制，比如把所有的球都装到其中一个盒子，所以盒子相当于是一个重集：
{\infty\cdot a_{1},\infty\cdot a_{2},\infty\cdot a_{3},\cdot \cdot \cdot ,\infty\cdot a_{n}}。
结果就是相当于在重集里面取出n-r个元素的组合

其实就是F（r，n-r）= \binom{r+n-r-1}{r-1}=\binom{r+n-r-1}{n-r}=\binom{n-1}{r-1}

（1）（2）使用乘法定理之后，结果等于\binom{n-1}{r-1}

方法2

直接一个步骤完成，要求盒子不能为空，根据隔板法（可以wiki一下）
r个盒子，n个球，相当于要把n个球划分为r堆，
因为n个球有n-1的缝隙，要划分为r堆，就需要找r-1个缝隙。
所以就是在n-1个缝隙里面找出r-1个缝隙就好了
答案就是\binom{n-1}{r-1}

上一篇下一篇

猜你喜欢

热点阅读