组合数学八题
(题目来自朱全民老师PPT)
题目如下（样例： n=3 m=2）
A 给定N个不同的球，放进M个不同的盒子，盒子允许为空，有多少种方案？ 样例输出：8
B 给定N个不同的球，放进M个不同的盒子，盒子不允许为空，有多少种方案？ 样例输出：6
C 给定N个不同的球，放进M个相同的盒子，盒子允许为空，有多少种方案？ 样例输出：4
D 给定N个不同的球，放进M个相同的盒子，盒子不允许为空，有多少种方案？ 样例输出：3
E 给定N个相同的球，放进M个不同的盒子，盒子允许为空，有多少种方案？ 样例输出：4
F 给定N个相同的球，放进M个不同的盒子，盒子不允许为空，有多少种方案？ 样例输出：2
G 给定N个相同的球，放进M个相同的盒子，盒子允许为空，有多少种方案？ 样例输出：2
H 给定N个相同的球，放进M个相同的盒子，盒子不允许为空，有多少种方案？ 样例输出：1
因为题目顺序有点畸形，按照正常人的思维，如下做题顺序较优：
A F E G H D C B
分别辨析。
A 给定N个不同的球，放进M个不同的盒子，盒子允许为空，有多少种方案？
[分析] 每个球都可以放在任意个盒子中。
[答案] m^n
F 给定N个相同的球，放进M个不同的盒子，盒子不允许为空，有多少种方案？
[分析] 题目转化为，将n个球放在一排，在它们之间n-1个空隙选m-1个插棍子将小球分为m部分，将每部分放进盒中，问有几种分法。
[答案] 
文章图片
E 给定N个相同的球，放进M个不同的盒子，盒子允许为空，有多少种方案？
[分析] 与上题类似，但有盒子可以为空，这就意味着两根棍子可以在同一缝隙。将问题转化，先在每个盒子放一个球再来放剩下N个球，与上题类似，将n+m个球放在一排，在它们之间n-+m-1个空隙选m-1个插棍子将小球分为m部分。这样使得棍子不重合。
[答案] 
文章图片
G 给定N个相同的球，放进M个相同的盒子，盒子允许为空，有多少种方案？
[分析] 设答案为f[n][m],数值等于有空盒子的情况（f[n][m-1]，n个球放在m-1个盒子里）加上没空盒子的情况(f[m-n][m],每个盒子放一个球，剩下m-n个球随便放)。
[递推式] f[n][m]=f[n][m-1]+f[m-n][m]
[边界条件] f[i][j]=1 (i=0 || m=1) , f[i][j]=f[i][i] (j>i)
H 给定N个相同的球，放进M个相同的盒子，盒子不允许为空，有多少种方案？
[分析] 先每个盒放一个球，再如G.
[答案] 0(m>n),f[n-m][m] (n>=m,f同G中的f)
D 给定N个不同的球，放进M个相同的盒子，盒子不允许为空，有多少种方案？
[分析] 设答案为f[n][m]，答案为1*f[n-1][m-1] (第n个球放在第m个盒子，其余的放在其余的格子)+m*f[n-1][m] (第n个球任意放，乘上n-1个球放在m个盒子中的方案数)，这样能保证一定没有空盒子。
[递推式] f[n][m]=f[n-1][m-1]+m*f[n-1][m]
[边界条件] f[i][j]=1(i=j || j=1), 0(j>i)
C 给定N个不同的球，放进M个相同的盒子，盒子允许为空，有多少种方案？
[分析] 与D有联系，为n个盒子放在1~m个盒子的方案数的总和
[答案] 
文章图片
(f同D中的f)
B 给定N个不同的球，放进M个不同的盒子，盒子不允许为空，有多少种方案？
[分析] 与D有联系，为n个盒子放在1~m个盒子的方案数的总和成上m个盒子的排列总数
[答案] 
文章图片
(f同D中的f)
【组合数学八题】–By Foggy
2015.6.21组合数学经典八题
推荐阅读
- 数学大作战
- 21天|21天|羊多多组合《书都不会读，你还想成功》
- 2018-08-29|2018-08-29 - 草稿 - 草稿
- 2019.11.14号总结
- 五年级数学上册期中考试质量分析
- 思维导图让你换一种打开方式学数学
- R语言|R语言 函数
- 读《吴正宪给小学数学教师的建议》有感
- 湘潭大学“三下乡”（羊牯村采访）
- 【思维导图实战派】刻意练习计划“遇见……”|【思维导图实战派】刻意练习计划“遇见……” 1/300 人教版数学五下第三单元《正方体和长方体的认识》