強(qiáng)基計劃數(shù)學(xué)備考系列講座(1)
——組合與概率

王慧興

(清華大學(xué)附屬中學(xué))

1 知識技能

2 要點解析

要點1特型方程計數(shù):滿足方程x1＋x2＋…＋xn＝m(m，n∈N*)的一個有序整數(shù)組(x1，x2，…，xn)，稱為該方程的一個整數(shù)解.

(1)當(dāng)m≥n時，方程的正整數(shù)解(x1，x2，…，xn)(xi∈N*，1≤i≤n)的個數(shù)為;

(2)方程的非負(fù)整數(shù)解(x1，x2，…，xn)(xi∈N，1≤i≤n)的個數(shù)為.

證明(1)任取方程的一個正整數(shù)解(x1，x2，…，xn)(xi∈N*，1≤i≤n)，則1≤x1＜x1＋x2＜…＜x1＋x2＋…＋xn－1≤m－1，令x1＋x2＋…＋xi＝y(tǒng)i(1≤i≤m－1)，則有序正整數(shù)組(x1，x2，…，xn)與取自集合{1，2，…，n－1}遞增正整數(shù)組(y1，y2，…，yn－1)一一對應(yīng)(yn＝m－x1－x2－…－xn－1)，所以方程的正整數(shù)解(x1，x2，…，xn)的個數(shù)是.

(2)任取一個非負(fù)整數(shù)解(x1，x2，…，xn)(xi∈N，1≤i≤n)，則x1＋x2＋…＋xn＝m?(x1＋1)＋(x2＋1)＋…＋(xn＋1)＝m＋n，令xi＋1＝y(tǒng)i(1≤i≤n)，則原方程的非負(fù)整數(shù)解(x1，x2，…，xn)與方程y1＋y2＋…＋yn＝m＋n的正整數(shù)解(y1，y2，…，yn)一一對應(yīng)，所以由(1)可知原方程的非負(fù)整數(shù)解的個數(shù)是.

要點2生成函數(shù):無窮項數(shù)列{an}的生成函數(shù)是指無窮項多項式a1＋a2x＋…＋anxn－1＋…;兩個常用生成函數(shù)是

記方程x1＋x2＋…＋xn＝m(m，n∈N*，m＞n)的正整數(shù)解(x1，x2，…，xn)個數(shù)為am，由

令i＋n＝m，得i＝m－n，故所求方程的正整數(shù)解的個數(shù)為這就應(yīng)用生成函數(shù)方法再次建立了上述不定方程的正整數(shù)解個數(shù).

要點3可重元組合數(shù):給定正整數(shù)n，k，則{1，2，…，n}的可重k元組合數(shù)是.

證明任取一個這種可重k元組合{x1，x2，…，xk}(用可重元集合表示對應(yīng)的可重元組合)，不妨設(shè)x1≤x2≤…≤xk，則1≤x1＜x2＋1＜…＜xk＋k－1≤n＋k－1，所以可重k元組合{x1，x2，…，xk}與{1，2，…，n＋k－1}的不可重k元組合一一對應(yīng)，故所求可重k元組合數(shù)為

另證記可重k元組合{x1，x2，…，xk}中元素i∈{1，2，…，n}重數(shù)是yi，則可重k元組合{x1，x2，…，xk}與有序非負(fù)整數(shù)組(y1，y2，…，yn)一一對應(yīng)，故所求k元組合{x1，x2，…，xk}個數(shù)等于方程y1＋y2＋…＋yn＝k的非負(fù)整數(shù)解(y1，y2，…，yn)個數(shù).

要點4映射計數(shù):設(shè)A，B是兩個非空有限集合，映射f:A→B分類如下.

(1)如果f:A→B是滿射，則|A|≥|B|;

(2)如果f:A→B是單射，則|A|≤|B|;

(3)如果f:A→B是雙射，則|A|＝|B|(雙射轉(zhuǎn)移);

(4)如果滿射f:A→B滿足B中每個元素恰有k個原象，則|A|＝k|B|.

要點5圓排列:n元圓排列個數(shù)是(n－1)!.

證明記n元線排列集合為A，n元圓排列集合為B，把每個線排列中的元素按逆時針順序依次排在圓周的n個等分點上，則建立了n元線排列與n元圓排列的對應(yīng)關(guān)系，易知映射f:A→B是滿射，并且每個圓排列都有n個原象，所以n!＝|A|＝n|B|，故n元圓排列個數(shù)是(n－1)!.

要點6置換計數(shù):所謂置換就是指雙射f:A→A.建立計數(shù)結(jié)論，就把集合A界定為有限集(|A|＝n).接下來，我們引入圖論方法，構(gòu)造有向圖G(V，E)，其中頂點集V＝A＝{1，2，…，n}，i表示A的元素ai(1≤i≤n)，稱為點;邊集E＝{(i，j)|f(i)＝j(luò)，i，j∈V}，這里本質(zhì)上E＝{(i，f(i))|i∈V}.由雙射迭代，任意的i∈V，存在一個最小正整數(shù)ni(1≤ni≤n)，滿足fni(i)＝i，因此從i出發(fā)，按邊的指向，可以得到一個圈i→f(i)→f2(i)→…→fni－1(i)→fni(i)＝i，稱為映射圈，同時稱最小正整數(shù)ni為元素i∈V的階.這樣一個置換f:A→A的圖G(V，E)由一些獨立(無公共頂點)的映射圈構(gòu)成，弄清楚圖G(V，E)的結(jié)構(gòu)之后，就可以按(雙射)f:A→A的已有性質(zhì)(計數(shù)對象雙射并沒有完全定義)，確定映射圈的個數(shù)以及每個映射圈上的點數(shù)，據(jù)此建立集合A的劃分:A＝C1∪C2∪…∪Cr，|Ci|＝ni，圈Ci中的元素的階都是ni(1≤i≤r≤n)，且n1＋n2＋…＋nr＝n.由于每個圈上的元素結(jié)合(象與原象)關(guān)系都需要做圓排列，因此圈Ci的個數(shù)共有(ni－1)!種，r個確定的圈一起構(gòu)成一個映射圖G(V，E).

注意階ni的性質(zhì):fk(i)＝i(k∈N*)?ni|k;取t＝[n1，n2，…，nn]，則ft(i)＝i(任意的i∈A)，即迭代置換ft是恒等置換iA，因此存在最小正整數(shù)T，使得fT＝iA，這個正整數(shù)T稱為置換f:A→A的階，也有性質(zhì):fk＝iA?T|k，因此T|t.

為在計算置換f:A→A的個數(shù)中考慮重復(fù)因素，在此引入“型”的概念，記置換f:A→A含有bi個長為i的圈，稱該置換為1b12b23b3…nbn，由此，可以方便地計算置換f:A→A的個數(shù)，也就是映射圖G(V，E)的個數(shù)，即注意，其中應(yīng)用除法是因為如下兩個原因.其一，每個長為k的圈(a1→a2→…→ak→a1)作為一個圓排列，對應(yīng)于k個不同的線排列，而f:A→A共有bk個不同的長度為k的圈，這bk個圈在n!中引起重復(fù)的倍數(shù)是kbk;其二，bk個長度為k的不同圈在n!中計入bk!個不同的線排列，再引起重復(fù)的倍數(shù)bk!.

要點7更列計數(shù):給定正整數(shù)n，把1，2，…，n排成一列a1，a2，…，an，滿足ai≠i(任意的1≤i≤n)，則稱a1，a2，…，an為1，2，…，n的一個更列，記更列數(shù)為Mn，則M1＝0，M2＝1，M3＝2，M4＝9，一般地，由遞推公式Mn＝(n－1)(Mn－1＋Mn－2)(n≥3)，其通項公式是

讀者也可以應(yīng)用容斥計數(shù)原理探究Mn的算法.

要點8分組計數(shù):把n個不同元素分成m組，各組內(nèi)的元素個數(shù)分別記作n1，n2，…，nm.如果元數(shù)n1，n2，…，nm互異，則不同分組數(shù)是;如果n1＝n2＝…＝nm＝k，則不同分組數(shù)是

要點9組合極值:為求一個組合量k的最值，現(xiàn)以最大值kmax為例.

1)一方面，從極端性入手，基于合情思維捕獲一個極端例子，得到kmax≥C(常數(shù));另一方面，基于題目結(jié)構(gòu)關(guān)系，捕獲數(shù)據(jù)信息，經(jīng)組合推理，建立kmax≤C，故kmax＝C.

2)從極端性入手，基于合情思維捕獲一個k＝C－1的反例，得到kmax≥C;另一方面，再證明該組合量都滿足k≤C.故kmax＝C.

要點10點集幾何與方法:組合幾何中有一項內(nèi)容就是有限點幾何，其中典型問題之一是赫爾伯倫型極值問題，求解策略就是著名的凸包方法——一個有限點集Ω的凸包就是覆蓋Ω的最小凸多邊形.

要點11條件概率:在事件A發(fā)生的條件下事件B發(fā)生的概率記為P(B|A)，稱為事件A發(fā)生條件下事件B發(fā)生的條件概率，按定義得

特別地，兩個事件A，B互相獨立等價于P(B|A)＝P(B)或P(A|B)＝P(A)，即P(AB)＝P(A)P(B);一般地，對n個隨機(jī)事件A1，A2，…，An，有

要點12全概率公式與貝葉斯公式:先定義完備事件組的概念，稱事件空間Ω的一組事件B1，B2，…，Bn構(gòu)成一個完備事件組，是指B1∪B2∪…∪Bn＝Ω，且Bi∩Bj＝?(不可能事件，1≤i＜j≤n).

(1)全概率公式:已知事件空間Ω的一個完備事件組B1，B2，…，Bn，則對任意事件A?Ω，都有

(2)貝葉斯(Bayes)公式:條件同上，則

表1中其他知識技能，將在下文例題中滲透，在此不再贅述.

表1

3 典例精析

3.1 組合計數(shù)

應(yīng)用分類加法原理務(wù)必嚴(yán)格分類——不重不漏;應(yīng)用分步乘法原理務(wù)必嚴(yán)格分步——不斷不疊.強(qiáng)基計劃校考中組合計數(shù)試題通常兼具分步與分類技能，而且分類復(fù)雜，因此，選取一個全集，建立總控數(shù)據(jù)，基于補(bǔ)集思想，剔除對立面，得到組合計數(shù).除此之外，還有基于轉(zhuǎn)化與化歸的雙射轉(zhuǎn)移、遞推傳遞、容斥計數(shù)、生成函數(shù)、折線表征、重構(gòu)元素等其他策略.

例1(清華大學(xué))滿足A∪B?C?{1，2，…，2020}的子集組(A，B，C)個數(shù)是_________.

解析

按題意，子集組(A，B，C)條件等價于A，B?C?{1，2，…，2020}，按|C|＝i(0≤i≤2020)分類計數(shù)，由分步乘法原理，其中滿足|C|＝i的子集組(A，B，C)個數(shù)是再應(yīng)用分類加法原理與二項式定理，得滿足條件的子集組(A，B，C)個數(shù)是

點評

按題意{1，2，…，2020}＝Ω被子集組(A，B，C)劃分為五部分，按文氏圖(如圖1)可應(yīng)用分步乘法計數(shù)原理直接求解.

圖1

例2(北京大學(xué))要在6×6的方格場地中停放3輛外形完全相同的無牌照紅色新轎車與3輛外形完全相同的無牌照黑色新轎車，每一行、每一列都只停放一輛車，每輛車占一格(一個車位)，則所有不同的停放方法種數(shù)是_________.

解析

按題意，3輛外形相同的無牌照紅色新轎車與3輛外形相同的無牌照黑色新轎車分別視為同元，這為一個“不盡相異元素”的組合計數(shù)問題.

點評

也可先選位置再停車.按行分步確定位置共有6!種方法，從選定的6個位置中選出3個位置停放3輛外形相同的無牌照紅色新轎車，不同停法是，再把3輛外形相同的無牌照黑色新轎車停放在其余3個不同位置上，只有1種停放方法，所以按分步乘法計數(shù)原理，得不同的停放方法數(shù)是

例3給定正整數(shù)n，集合S＝{1，2，…，10}的所有有序子集組(A1，A2，…，An)構(gòu)成一個集合T，則

的值是______.

解析

對n＋1元組(A1，A2，…，An，a)(a∈A1∪A2∪…∪An)計數(shù):一方面，對任一有序子集組(A1，A2，…，An)，共有|A1∪A2∪…∪An|個a∈S與之一起構(gòu)成n＋1元組(A1，A2，…，An，a)，因此，所有n＋1元組(A1，A2，…，An，a)的個數(shù)為

另一方面，對任一a∈S，含這個a的所有有序子集組(A1，A2，…，An)的個數(shù)是，因此，所有n＋1元組(A1，A2，…，An，a)的個數(shù)為

由①和②，得

點評

重構(gòu)元素組是組合計數(shù)中的一種常用策略，其根本作用在于存在兩種算法視角，通過算兩次建構(gòu)等式，也是避免重復(fù)計數(shù)的一種策略.

例4方程x＋y＋z＝2022的滿足x≥y≥z的正整數(shù)解(x，y，z)個數(shù)是________.

解析

以方程x＋y＋z＝2022的所有正整數(shù)解數(shù)作為總控數(shù)據(jù)，再分析其中數(shù)據(jù)結(jié)構(gòu)，剔除對立數(shù)據(jù).

記Ω＝{(x，y，z)|x＋y＋z＝2022，x，y，z∈，其中

由B1＝{(a，a，2b′)|a＋b′＝1011，a，b′∈N*，a≠2b′}，得|B1|＝1009.

同理，|B2|＝1009＝|B3|，故|A2|＝1009×3.

記C＝{(x，y，z)∈Ω|x＞y＞z，x，y，z∈N*}，則A3＝3!·|C|.

因為|A1|＋|A2|＋|A3|＝，所以

故所求正整數(shù)解數(shù)為

3.2 概率計算

除針對基本概型(古典概型、幾何概型、條件概率)計算概率之外，在統(tǒng)計與分布等問題中也有概率計算.

例5一項“過關(guān)游戲”規(guī)則規(guī)定:在第n關(guān)要拋擲一顆骰子n次，如果這n次拋擲所出現(xiàn)的點數(shù)之和大于2n，則算過關(guān).問:

(1)某人在這項游戲中最多能過幾關(guān)?

(2)求他連過前三關(guān)的概率.

注:骰子是一個在6個面上分別標(biāo)有1，2，3，4，5，6點數(shù)的質(zhì)地均勻正方體，拋擲骰子落地靜止后，向上一面的點數(shù)為出現(xiàn)的點數(shù).

解析

(1)按題意，此人能過第n關(guān)的條件是他連續(xù)拋擲n次骰子，出現(xiàn)的點數(shù)之和應(yīng)大于2n，所以過第n關(guān)的必要條件是6n＞2n，從而n≤4，故此人至多能過第4關(guān).

(2)記過第n關(guān)的概率為Pn(n＝1，2，3)，則此人連過3關(guān)的概率P＝P1P2P3，下面分別計算P1，P2，P3.

過第一關(guān)的條件是拋擲一次骰子出現(xiàn)的點數(shù)大于2，即出現(xiàn)的點數(shù)可以是3，4，5，6，所以

過第二關(guān)的條件是連續(xù)兩次拋擲骰子出現(xiàn)的點數(shù)之和大于4，記連續(xù)兩次拋擲骰子出現(xiàn)的點數(shù)分別為x1，x2，則P2＝P(x1＋x2＞4)＝1－P(x1＋x2≤

過第三關(guān)的條件是連續(xù)三次拋擲骰子出現(xiàn)的點數(shù)之和大于8，記連續(xù)三次拋擲骰子出現(xiàn)的點數(shù)分別為x1，x2，x3，則

因為不定方程x1＋x2＋x3＝k的正整數(shù)解個數(shù)是(3≤k≤8)，所以滿足x1＋x2＋x3≤8的有序正整數(shù)組(x1，x2，x3)個數(shù)是故

點評

第(2)問直接求滿足x1＋x2＋x3＞8，即x1＋x2＋x3＝k(k＝9，10，11，…，18)是難點，因為每個變量帶有條件1≤xi≤6，所以按公式得到的不定方程的解數(shù)有不可能發(fā)生的正整數(shù)組(x1，x2，x3).因此，本題解法堅持正難則反，化難為易原則.

例6兩個相同的正四面體，四個面分別標(biāo)有1，2，3，4，某人每次同時投擲這兩個正四面體，規(guī)定每次兩底面上數(shù)字之和為所得數(shù)字，共投擲三次，則三次所得數(shù)字之積能被10整除的概率是( ).

解析

每次投擲所得數(shù)字X是一個隨機(jī)變量，X的概率分布如表2所示.

表2

記三次投擲所得數(shù)字分別為X，Y，Z，則

10|XYZ?X，Y，Z中 必有5與偶數(shù).

若X，Y，Z恰有1個5，則另兩個必有偶數(shù)，這包括另兩個都是偶數(shù)或一個是偶數(shù)，另一個是不為5的奇數(shù)，概率為

若X，Y，Z恰有2個5，則另一個必為偶數(shù)，概率為

另解直接用概率計算

例7(清華大學(xué))拋擲n次硬幣，記不連續(xù)出現(xiàn)三次正面朝上的概率為Pn.

(1)求P1，P2，P3，P4;

(2)求{Pn}的遞推公式;

解析

(2)當(dāng)n≥4時，按第n次反面朝上與正面朝上分成兩類.

當(dāng)?shù)趎次反面朝上，形如“…反”，這種結(jié)果中不出現(xiàn)連續(xù)三次正面朝上的概率等于Pn－1，但第n次出現(xiàn)反面朝上的概率是，按積事件的概率公式，可得當(dāng)?shù)趎次反面朝上時不出現(xiàn)連續(xù)三次正面朝上的概率是

當(dāng)?shù)趎次出現(xiàn)正面朝上，這種事件是兩種互斥事件“…反正”與“…反正正”的和事件，其概率是

(3)先證數(shù)列{Pn}存在極限，為此，我們證明該數(shù)列單調(diào)有界:由于0＜Pn＜1，任意的n∈N*，只需證明該數(shù)列單調(diào)遞減.

由①－②，可得，當(dāng)n≥5時，恒有Pn＝Pn－1－.任意的n∈N*，所以存在，記

點評

本題是數(shù)列、遞推與極限的典型應(yīng)用題，上述解法基于數(shù)列單調(diào)有界必有極限，通過解方程求出極限，方法通用、快捷.

例8有朋友自遠(yuǎn)方來訪，乘火車來的概率為乘船、乘汽車、乘飛機(jī)來的概率分別是已知他乘火車來遲到的概率是乘船來遲到的概率為乘汽車來遲到的概率為如果他乘飛機(jī)來就不會遲到(遲到的概率是0).在結(jié)果是遲到的情形下，求他乘火車的概率.

解析

以B表示事件“遲到”;用A1，A2，A3，A4分別表示事件:“乘火車”“乘船”“乘汽車”“乘飛機(jī)”，由Bayes公式，得

3.3 推理與證明

例9求證集合S＝{1，2，3，…，24}的任一17元子集T中都有3個元素兩兩互素.

證明作二劃分S＝B∪C，B＝{4，6，8，9，10，12，14，15，16，18，20，21，22，24}，C＝{1，2，3，5，7，11，13，17，19，23}，其 中C中 任 意3個 數(shù) 都 是 兩 兩 互素的.

任取17元子集A?S，由7＝|A|＝|S∩A|＝|A∩B|＋|A∩C|≤14＋|A∩C|，得|A∩C|≥3，所以A中至少有3個數(shù)兩兩互素，由A的任意性，命題得證.

例10把－1，1以任意方式填入一個n×n(n≥4)方格表，把位于不同行不同列的n個數(shù)之積稱作一個基本量，記所有基本量之和為S，求證:S是4的倍數(shù).

證明記第i行第j列小方格填入的數(shù)為ai，j∈{－1，1}(1≤i，j≤n)，則 基 本 量 通 式 為a1，i1a2，i2a3，i3…an，in∈{－1，1}.記所有基本量中取值為－1的個數(shù)為k，則取值為1的基本量個數(shù)為n!－k.

一方面，所有基本量之和為

另一方面，計算所有基本量之積，得

因為整數(shù)n≥4，所以2|(n－1)!，所以由②得

代入①，得S＝n!－4l≡0(mod4).

3.4 最值與構(gòu)造

例11集合S＝{1，2，3，4，5}的一組子集A1，A2，…，Ak，其中任意兩個子集都沒有包含關(guān)系，求kmax.

解析

一方面，取出S的C25＝10個2元子集，得到一個滿足題意的子集組，所以

另一方面，把S的全部25＝32個子集如下分成10組，每一組都是一個“包含鏈”:

所以，上述每一條子集鏈上至多取出1個子集，組成符合題意的子集組，從而k≤10，即kmax≤10.

綜上，得kmax＝10.

一般地，n元集合S＝{1，2，…，n}的一組子集A1，A2，…，Ak，兩兩互不包含，即Ai?Aj且Ai?Aj(任意的1≤i＜j≤n)，則

事實上，一方面，把每個Ai的元素進(jìn)行全排列，得到|Ai|!個|Ai|元排列，再把其補(bǔ)集的全部元素進(jìn)行全排列，得到(n－|Ai|)!個n－|Ai|元排列，前后對接得到|Ai|!·(n－|Ai|)!個n元排列;由組子集A1，A2，…，Ak中任意兩個子集互不包含，則對任意兩個不同子集，上面構(gòu)建的不同組的n元排列都沒有重復(fù)，所以

另一方面，取出集合S的全部元子集構(gòu)成一個符合題意的子集組，此時從 而kmax≥

例12集合S＝{1，2，3，…，n}的一組非空子集A1，A2，…，Ak，其中任意兩個要么有包含關(guān)系，要么兩者交集是空集，求kmax.

解析

一方面，集合S的子集組{1}，{1，2}，{1，2，3}，…，{1，2，…，n}，{2}，{3}，{4}，…，{n}滿足題意，此時k＝2n－1，因此kmax≤2n－1.

另一方面，下證kmax≥2n－1，即證k≤2n－1.

首先，當(dāng)n＝1時，S＝{1}符合題意的非空子集組只有1個子集，從而k≤1;當(dāng)n＝2時，S＝{1，2}符合題意的非空子集組，子集個數(shù)最多的是{1}，{2}，{1，2}，因此k≤3.

假設(shè)對n≤l，都有k≤2n－1，下證當(dāng)n＝l＋1時，也有k≤2n－1.

任取S＝{1，2，…，l，l＋1}的符合題意的子集組A1，A2，…，Ak，除其中可能有{1，2，…，l，l＋1}之外，取出其余k－1個子集中元素最多的一個子集E，則|E|≤l.再把這k－1個子集都與E比較，分成兩類.

第一類:Ai1，Ai2，…，Aix?E，其中任意兩個有包含關(guān)系或不相交，由歸納假設(shè)，可知x≤2|E|－1.

第二類:Aj1，Aj2，…，Ajy，都與E交集為空集，則這些子集都是?SE的子集，且其中任意兩個有包含關(guān)系或交集為空集，從而由歸納假設(shè)，得

故

由數(shù)學(xué)歸納法，k≤2n－1得證.

綜上，kmax＝2n－1.

例13(北京大學(xué))在(2019×2020)2019的全體正因數(shù)中選若干個，使得其中任意兩個的乘積都不是平方數(shù)，則最多可選因數(shù)個數(shù)為( ).

A.16 B.31

C.32 D.前三個答案都不對

解析

記符合條件的因子組為A(視為集合)，下證|A|max＝32.作素因子分解

記

一方面，取b的全部正約數(shù)構(gòu)成因子組B，即B＝{t∈N*|t|b}，則B是正整數(shù)a的符合題意的因子組，并且|B|＝25＝32，從而

另一方面，對正整數(shù)a的任一因子組A.

情形一:A?B，則|A|≤|B|＝32.

情形二:A?B，即存在2u3v5w101z673y∈A(u，v，w，z，y∈N)，但2u3v5w101z673y?B，亦 即max{u，v，w，z，y}＞1，不妨設(shè)u＞1，作帶余除法u＝2k＋r(k∈N*，r∈{0，1})，由

是一個完全平方數(shù)，所以2u－2k3v5w101z673y?A.再由u－2k與u奇偶性相同，以2u－2k3v5w101z673y替換A中的2u3v5w101z673y得到a的符合條件的另一因子組A1，并且|A1|＝|A|.

如果A1中仍然存在一個數(shù)，它不是正整數(shù)b的約數(shù)，再做一次上述替換，得到符合條件的另一因子組A2，并且|A2|＝|A1|.

經(jīng)有限次上述替換操作，得到一些列符合條件的a因子組A1，A2，…，Al(l∈N*)，滿足

所以|A|≤|B|＝32.

綜上，|A|≤32，由A的任意性，可得

由①和②，得|A|max＝32.

4 實戰(zhàn)演練

1.給定正整數(shù)n，正整數(shù)a，b，c為一個三角形的三條邊長，且b≤n，a≤b≤c，則這種三角形個數(shù)是_________.

2.(上海交大)任意投擲3枚骰子，則三個面朝上的點數(shù)恰好組成等差數(shù)列的概率為________.

3.設(shè)集合A＝{1，2，3，…，10}，映射f:A→A滿足下列兩條件:(1)f30(x)＝x(任意的x∈A);(2)對滿足1≤k≤29的每個整數(shù)k，至少存在一個a∈A，使得fk(a)≠a，求這種映射的個數(shù).

4.1，2，3，4，5的 排 列a1，a2，a3，a4，a5滿 足:對1≤i≤4，a1，a2，…，ai不構(gòu)成1，2，…，i的某個排列，求這種排列a1，a2，a3，a4，a5的個數(shù).

5.甲、乙等4人互相傳球，第一次由甲先把球傳出，每次傳球時，傳球者將球等可能地傳給另外3人之一.

(1)經(jīng)過2次傳球后，球在甲乙兩人手中的概率各是多少?

(2)經(jīng)過n次傳遞之后，球在甲手中的概率記為Pn(n＝1，2，…)，求Pn與{Pn}的極限.

6.某人忘記了電話號碼的最后一個數(shù)字，因此他隨意撥號，求他撥號不超過3次而接通的概率.

7.某電子設(shè)備制造廠所用元件是由三家元件制造廠提供的，過往記錄數(shù)據(jù)如表3所示.

表3

設(shè)這三家工廠的產(chǎn)品在倉庫中是均勻混合的，并且無區(qū)別標(biāo)志.

(1)在倉庫中隨機(jī)取出一只元件，求它是次品的概率;

(2)在倉庫中隨機(jī)取出一只元件，若已知取到的是次品，為分析此次品來自何廠，需求出此次品由三家工廠生產(chǎn)的概率分布是多少.

8.盒中放有12個乒乓球，其中9個是新的，第1次比賽時從中取出3個來用，比賽后放回盒中，第2次比賽時再從盒中取出3個(精確到0.001).

(1)求第2次取出的球都是新球的概率;

(2)已知第2次取出的球都是新球，求第1次取到的3球都是新球的概率.

圖2

10.(復(fù)旦大學(xué))有2個細(xì)胞，每個細(xì)胞每次分裂成2個細(xì)胞或死亡的概率均為求分裂2次后，有細(xì)胞成活的概率P.

11.某個系統(tǒng)中每個元件正常工作的概率是p(0＜p＜1)，各個元件是否正常工作相互獨立;如果系統(tǒng)中有多于一半的元件正常工作，系統(tǒng)就能正常工作;系統(tǒng)正常工作的概率稱為系統(tǒng)的可靠性.

(1)該系統(tǒng)配置有2k－1(k∈N*)個元件，求該系統(tǒng)正常工作概率的表達(dá)式;

(2)現(xiàn)為改進(jìn)系統(tǒng)性能，擬增加兩個元件，試討論增加兩個元件后，能夠提高系統(tǒng)的可靠性.

12.已知平面上n個點，其中任何3點都是直角三角形的3個頂點，求nmax.

13.在n邊形內(nèi)分布k個點，使得在以該n邊形的任意3個頂點為頂點的三角形內(nèi)都至少有1個點，求kmin.

14.在m×n的矩形方格紙上畫一條直線，記這條直線與k個小方格相交(矩形內(nèi)含有直線上一段)，求kmax.

15.將一個正方體剖分成互不重疊的k個四面體，求kmax.

16.某公司需要錄用一名秘書，共有10人報名，公司經(jīng)理決定按照求職報名的順序逐個面試，前3名面試后一定不錄用，自第4個人開始將他與前面面試過的人相比較，如果他的能力超過了前面所有已面試過的人，就錄用他，否則就不錄用，繼續(xù)面試下一個.如果前9個人都不錄用，那么就錄用最后一個面試的人.

假定這10個人的能力各不相同，可以按能力由強(qiáng)到弱排為第1，第2，…，第10，顯然該公司到底錄用哪一個人，與這10個人報名順序有關(guān).大家知道，這樣的排列共有10!種，以Ak表示能力第k的人被錄用的不同報名順序數(shù)目，以表示他被錄用的可能性.

證明:在該公司經(jīng)理的方針之下，有

(1)A1＞A2＞…＞A8＝A9＝A10;

(2)該公司有超過70%的可能性錄用到能力最強(qiáng)的3個人之一，而只有不超過10%的可能性錄用到能力最弱的3個人之一.