Discrete mathematics and its applications筆記
第三章
精彩習題
1.How many bit strings of length eight contain either three consecutive 0s or four consecutive 1s?(連續(xù)的3個0送漠，或者連續(xù)的4個1乡摹，兩者都滿足也可以)
這題用遞歸去做就很舒服
2.求證：對于任意的非零整數(shù)n,在n的倍數(shù)里面棋蚌，一定存在一個只包含0和1的數(shù)（比如10001,11110001）
4.下面這段代碼，最后得到的k是多少谷暮？
3
這也是可重復組合問題
等價的組合題目是 從n個不一樣的數(shù)字中選出r個數(shù)(可以重復)蒿往，r就是循環(huán)的層數(shù)這個比較巧妙，因為每次選出的這r個數(shù)升序排列對應循環(huán)的一種情況湿弦，（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）不同類型的物體放進不同類型的箱子里
設每個箱子放积蜻，則由乘法原理，得方法數(shù)目：
（2）不同類型的物體放進相同類型的箱子里
公式比較復雜彻消，可以用窮舉法
設
則方法數(shù)目：
（3）相同類型的物體放進不同類型的箱子里
相當于第3點中的插隔板，方法數(shù)目：
（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
