【正文】 。所以，這兩種二進制數(shù)一一對應。10000111 11111000， 00011110 0001111101010110 01010111， 00111001 00111110反之，給定一個由n－1個1和n＋1個0組成的2n位數(shù)z．由于0比1多2個，故一定在某一位首次出現(xiàn)0的累計數(shù)超過1的累計數(shù)。結(jié)果整個數(shù)變成由n－1個1和n＋1個0組成的2n位數(shù)z。此時，后2(n－k)－1位上有n－k個1，n－k－1個0。132. 由n個0及n個1組成的字符串，其任意前k個字符中，0的個數(shù)不少于1的個數(shù)的字符串有多少？（解）解法一：由n個1和n個0組成的2n位二進制數(shù)共有個（2n個不盡相異元素的全排列） ，設(shè)所求的二進制數(shù)共有個，不符合要求的數(shù)有個。將分配過程分為三步：（1）從m個學生中選出2k人，有種選法；（2）將選出的2k個學生分給2號儀器，且每臺儀器k個人，有種分法；（3）將其余的名學生分給5號儀器，每臺儀器所分人數(shù)不限，有種分法。再結(jié)合（a），即得欲證的結(jié)論。又知對于不同的k，相應的串之間沒有重復?？捎蓛刹絹順?gòu)造這樣的n位串：（1） 先在n個不同的位置放入2k個相同的0，有種放法；（2） 再在其余的個位置放入1或2，其放法對應位二進制串的個數(shù)，有個。考慮諸中至少有一個為0或1的串，那么，從串的左邊開始向右掃描，總是會碰到0或1，對掃描到的第一個0（或1），將其改為1（或0），從而將偶串變成了唯一的一個奇串，或?qū)⑵娲兂闪宋ㄒ坏囊粋€偶串。(a) 0出現(xiàn)偶數(shù)次的字符串有個；(b) 其中q＝2.（證）（a）稱滿足條件的串為偶串，否則為奇串。（解）（a）視為從集合中選取n個元素，分類統(tǒng)計，共有n＋1類取法：設(shè)第k類取法是指所取的n個元素中含有k個，個其它的（每個最多取一次），則此類取法共有種。（b）在3n＋1個球中，有n個相同。129. （a）在2n個球中，有n個相同。方法三： 集合中2n個元素的全排列的總數(shù)即為其次，對，方法類似，關(guān)鍵是看出＝。（證）（a）方法一：把2n個不同的球放入n個相異的盒子中，每個盒子中恰有2個球，其分配方案數(shù)即為＝。128. （a）用組合方法證明和都是整數(shù)。125. 給出 的組合意義。（解）（1）重復排列問題，共有種不同圖象；（2）重復組合問題，共有種不同圖象；（3）不重復組合問題，共有種不同圖象。（2）Bose－Einstein假定：r個質(zhì)點完全相同，每一個盒子可以放任意個。122. 統(tǒng)計力學需要計算r個質(zhì)點放到n個盒子里去，并分別服從下列假定之一，問有多少種不同的圖象。（證）設(shè)n的標準分解式為n＝。答 119. 試求n個完全一樣的骰子能擲出多少種不同的方案？（解）等價于從6類相異元素集中可重復地選取n個元素的n－重組合數(shù)：120. 凸十邊形的任意三個對角線不共點，試求這凸十邊形的對角線交于多少個點？又把所有的對角線分割成多少段？（解）（1）求交點數(shù)：一個交點兩條對角線四個頂點。（證） 因為盒子不能空，所以每個盒子可先放一個球。余類推，這樣，無效0的總數(shù)為注意到全0時的6個0和1 000 000本身的6個0相互抵消，所以1到1 000 000之間的自然數(shù)中0出現(xiàn)的次數(shù)為＝488 895注 1出現(xiàn)的次數(shù)為（要考慮1 000 000這個數(shù)的首位1），2，3，…，9各自出現(xiàn)的次數(shù)為。因為每位數(shù)字可以有10種選擇，根據(jù)乘法法則，共有個“6位數(shù)”，又每個“6位數(shù)”由6個數(shù)字組成（包括無效0），那么共有個數(shù)字，又每個數(shù)字出現(xiàn)的概率相等， 所以0出現(xiàn)的次數(shù)應是247。（1）設(shè)特定的引擎是a，則點火的方案數(shù)為32211＝12。從m個數(shù)中取第一組數(shù)共有m－1種取法。113. 有n個不同的整數(shù)，從中取出兩組來，要求第一組數(shù)里的最小數(shù)大于第二組的最大數(shù)，問有多少種方案？（解） 設(shè)取的第一組數(shù)有a個，第二組有b個，而要求第一組數(shù)中最小數(shù)大于第二組中最大的，即只要從n個數(shù)中取出m＝a＋b個數(shù)，從大到小排序后取前a個作為第一組，剩余的為第二組，就滿足題目的要求。那么，有兩種思路：（1） 先從此n個不同的球中選出1個，放入A盒，再將其余個球放入另外兩盒，有種放法；（2） 先由n個球中選出k個，再從所選的k個球中選出1個放入A盒，將其余的k－1個球放入B盒，所剩的n－k個球放入C盒，有種放法。（證）用殊途同歸法。另一種分法是先選一人為一組，再從其余的人中選人為一組，剩下的人為一組。意義：將n個人分為3組：一組1人，一組r人，另一組人。（答） ＝＝840110. 試證任一正整數(shù)n可唯一地表成如下形式：n＝ ，0≤ai≤i， 111. 證明 nC(n－1，r)＝(r＋1)C(n，r＋1)。（答） ＝＝1008018. 求的展開式。（3）另外，設(shè)每周工作t天，每天最少工作5小時，最多工作小時，可以不按照上邊的兩步分配方法求解，而是直接計算多項式＝，中的系數(shù)，即得答案。（1）每周按7天計算，先要拿出57＝35小時平均分配到每一天，再將其余的15小時安排到7天之中，每天的小時數(shù)不受限制，則安排方案數(shù)為（2）若每周的工作日按6天計，則問題變成在平均分配完56＝30小時后，再將余下的20小時分配到這6天中，但此時每天最多只能分配19小時。但這樣計算無疑是有重復的，例如恰好選6人坐前排，其余8人全坐后排，那么上式中的就有重復。各類入坐方式互相不同，由加法法則，總的入坐方式總數(shù)為＋＋誤：先選6人坐前排，再選4人坐后排，剩下的4人坐入余下的6個座位。（解）（1）5人在前排就座，其坐法數(shù)為 ，4人在后排就座，其坐法數(shù)為 ，還空7個坐位，讓剩下的14－5－4＝5個人入坐，就座方式為 種，由乘法法則，就座方式總數(shù)為＝28 449 792 000（2）因前排至少需坐6人，最多坐8人，后排也如此。（解）（1）分類統(tǒng)計：①一位正整數(shù)有個；②兩位正整數(shù)有＝81個；③三位正整數(shù)有＝998＝648個；④千位數(shù)小于5的四位數(shù)有＝4987＝2016個；⑤千位數(shù)等于5，百位數(shù)小于4的數(shù)有＝487＝224個。反之，設(shè)任何≥2r＋1。（四） 漢明碼（1） 思想：如若與碼a的距離≤r，則認為是a的錯誤碼而予以糾正。例：(0000, 0000)＝0，(0000, 1001)＝2，(0101, 1010)＝4（二） 性質(zhì)三角不等式 （三） 檢錯碼與糾錯碼檢錯碼：奇偶校驗碼、漢明碼、BCH碼等。等號成立的條件：n＝k＋r（否則總有不全含的k＋r元子集）。一種特殊取法：先取前k個元素；再從其余的個元素中取r個，有種。結(jié)論：所求路徑數(shù)＝(0, 1)點到（m, n）點路徑數(shù)－(1, 0)點到（m, n）點路徑數(shù) N＝ ＝(m＋n－1)! ＝(m＋n－1)! ＝ （n—m）＝ 【】n, h, r都是非負整數(shù)，并且。等價于從（0, 1）點到（m, n）點的路徑數(shù)（前提：滿足條件）。1ABC8ACF15AFG22BDG29CEF2ABD9ACG16BCD23BEF30CEG3ABE10ADE17BCE24BEG31CFG4ABF11ADF18BCF25BFG32DEF5ABG12ADG19BCG26CDE33DEG6ACD13AEF20BDE27CDF34DFG7ACE14AEG21BDF28CDG35EFG結(jié)論2：科學家A的“鑰匙”的特征個數(shù)至少為C(6，3)＝＝20原因：A須有其余6人缺的鑰匙。試問該電子鎖至少應具備多少個特征？每位科學家的“鑰匙”至少應有多少種特征？（解）（秘密共享）分析：任意3個人在一起，至少缺一種特征，不能打開電子鎖。（解）（更一般的組合問題）集合A＝中取k個兩兩之差超過r的數(shù)構(gòu)成組合，設(shè)≥r＋1， 1≤i＜j≤k令 ， 則 ≥1， 1≤i＜j≤k且 1≤≤n－(k－1)r結(jié)論：從A中選k個元素的方案從集合B不重復地選取k個元素的方案（B＝）∴ 說明：r＝0，不重復組合＝1，重復組合＝1，間隔1個選＝m，間隔m個選例：【】有7位科學家從事一項機密工作，他們的工作室裝有電子鎖，每位科學家都有打開電子鎖的“鑰匙”。問題2：火車站外有100名乘客，欲從4個門排隊進入候車室，問有多少種進門的排隊方式？問題3：大樓共有19層，今有12人從一樓進入電梯上樓，每層都可能有人出電梯，且電梯的門同時只能容許一個人出入，問有多少種方式出電梯？【】把元集S劃分成個無序非空子集（n≥4），共有多少種分法？ （解）（球不同盒子相同）模型：分配問題：將n個不同的球放入n－3個相同的盒子，每個盒子最少一個球求解：分三類情況： (1) 一個子集為4元集，其余子集為一元集，等于n元集的不重復的4組合數(shù)；(2) 一個子集3元，一個子集2元，其余子集1元：n元集S的5組合數(shù)為，把5元集劃分成一個3元子集和一個2元子集的方法有＝10種，由乘法法則，此類劃分方法有10種；(3) 3個子集2元，其余子集1元：n元集的6組合數(shù)為，把6元子集劃分成3個2元子集的方法有 屬于此類的劃分方法有種。方案數(shù) n(n＋1)(n＋2)…(n＋r－1)＝＝12345…n－1n說明：不考慮盒中相異物體的次序，方案數(shù)為＝應用：A、B、C、D、E共5位同學由兩個門排隊進入教室，每個門每次只能同時進一人，問有多少種進法？答：23456＝720種前門人數(shù)后門人數(shù)方法備注0515!＝1200!5!1414!＝1201!4!232!3!＝120323!2!＝120414!1!＝120505!0!＝120若不考慮次序，總數(shù)為＝32?！尽堪裷個相異物體放入n不同的盒子里,每個盒子允許放任意個物體,而且要考慮放入同一盒中的物體的次序,求這種分配方案有多少?特點：既不是相異元素的不重復排列，也不是簡單的重復排列。思想：將問題轉(zhuǎn)化為變異一