Discrete mathematics and its applications笔记
第三章
精彩习题
1.How many bit strings of length eight contain either three consecutive 0s or four consecutive 1s?(连续的3个0，或者连续的4个1，两者都满足也可以)
这题用递归去做就很舒服
2.求证：对于任意的非零整数n,在n的倍数里面，一定存在一个只包含0和1的数（比如10001,11110001）
4.下面这段代码，最后得到的k是多少？
3
这也是可重复组合问题
等价的组合题目是 从n个不一样的数字中选出r个数(可以重复)，r就是循环的层数这个比较巧妙，因为每次选出的这r个数升序排列对应循环的一种情况，（n=3时）比如1，2，1说明
然后2，2，1说明
所以最后答案是
新知
1.笛卡尔积满足
2.容斥原理（principle of inclusion-exclusion,也叫作subtraction principle）
3.从n个元素（元素各不相同）中选出r个可以重复的元素 的方法
有：种
（可以想象要选出r本书，我们放入n-1个立书架（隔板））
比如r=6,n=4时：
** | * | | ***
3个隔板把书分成4种类型，上图中表示从第一种类型中选2本，从第二种类型中选1本，从第四种类型中选3本。
4.假设有n个物体，k个箱子（箱子可以空）
（1）不同类型的物体放进不同类型的箱子里
设每个箱子放，则由乘法原理，得方法数目：
（2）不同类型的物体放进相同类型的箱子里
公式比较复杂，可以用穷举法
设
则方法数目：
（3）相同类型的物体放进不同类型的箱子里
相当于第3点中的插隔板，方法数目：
（4）相同类型的物体放进相同类型的箱子里
这个也是穷举法呀（无奈）
比如把6个相同类型的物体放进4个相同类型的箱子
可以如下穷举：
6
5 1
4 2
4 1 1
3 3
3 2 1
3 1 1 1
2 2 2
2 2 1 1
