集合的概念與表示法

關(guān)于集合的概念與表示法24.04.202424.04.20243.1集合的概念與表示法3.1.1集合的概念

集合作為數(shù)學(xué)的一個基本而又簡單的原始概念，是不能精確定義的。一般我們把一些確定的互不相同的對象的全體稱為集合，集合中的對象稱為集合的元素。通常用大寫字母(如A、B等)表示集合，用小寫字母(如a、b)表示集合中的元素。給定一個集合A和一個元素a，可以判定a是否在集合A中。如果a在A中，我們稱a屬于A，記為a∈A。否則，稱a不屬于A，記為a

A。例如，某大學(xué)計(jì)算機(jī)系的全體學(xué)生、所有自然數(shù)等都是集合。第2頁,共82頁，2024年2月25日，星期天24.04.2024由集合的概念可知，集合中的元素具有確定性、互異性、無序性和抽象性的特征。其中：(1)確定性是指：一旦給定了集合A，對于任意元素a，我們就可以準(zhǔn)確地判定a是否在A中，這是明確的。(2)互異性是指：集合中的元素之間是彼此不同的。即集合{a，b，b，c}與集合{a，b，c}是一樣的。(3)無序性是指：集合中的元素之間沒有次序關(guān)系。即集合{a，b，c}與集合{c，b，a}是一樣的。(4)抽象性是指：集合中的元素是抽象的，甚至可以是集合。如A＝{1，2，{1，2}}，其中{1，2}是集合A的元素。第3頁,共82頁，2024年2月25日，星期天24.04.2024集合是多種多樣的，我們可以根據(jù)集合中元素的個數(shù)對其進(jìn)行分類。集合中元素的個數(shù)稱為集合的基數(shù)，記為|A|。當(dāng)|A|有限時，稱A為有限集合；否則，稱A為無限集合。下面將本書中常用的集合符號列舉如下：N：表示全體自然數(shù)組成的集合。Z：表示全體整數(shù)組成的集合。Q：表示全體有理數(shù)組成的集合。R：表示全體實(shí)數(shù)組成的集合。Zm：表示模m同余關(guān)系所有剩余類組成的集合。第4頁,共82頁，2024年2月25日，星期天24.04.20243.1.2集合的表示法

表示一個集合通常有兩種方法：列舉法和謂詞表示法。

1.列舉法(或枚舉法)

列舉法就是將集合的元素全部寫在花括號內(nèi)，元素之間用逗號分開。例如：A＝{a，b，c}，B＝{0，1，2，3，…}。列舉法一般用于有限集合和有規(guī)律的無限集合。

2.謂詞表示法(或描述法)

謂詞表示法是用謂詞來概括集合中元素的屬性。通常用{x|p(x)}來表示具有性質(zhì)p的一些對象組成的集合。例如：{x|1≤x≤6∧x為整數(shù)}為由1、2、3、4、5、6組成的集合。下面討論集合之間的關(guān)系。第5頁,共82頁，2024年2月25日，星期天24.04.20243.1.3集合的包含與相等

包含與相等是集合間的兩種基本關(guān)系，也是集合論中的兩個基本概念。兩個集合相等是按照下述原理定義的。外延性原理兩個集合A和B是相等的，當(dāng)且僅當(dāng)它們有相同的元素。記為A＝B。例如，若A＝{2，3}，B＝{小于4的素?cái)?shù)}，則A＝B。定義3.1

設(shè)A和B為兩個集合，若對于任意的a∈A必有a∈B，則稱A是B的子集，也稱A包含于B或B包含A，記作A

B。如果B不包含A，記作AB。B包含A的符號化表示為：A

B

x(x∈A→x∈B)。例如，若A＝{1，2，3，4}，B＝{1，2}，C＝{2，3}，則B

A且C

A，但CB。第6頁,共82頁，2024年2月25日，星期天24.04.2024定理3.1集合A和B相等當(dāng)且僅當(dāng)這兩個集合互為子集。即：A＝B

A

B∧B

A。證明若A＝B，則A和B具有相同的元素，于是

x(x∈A→x∈B)、

x(x∈B→x∈A)都為真，即A

B且B

A。反之，若A

B且B

A，假設(shè)A≠B，則A與B元素不完全相同。不妨設(shè)有某個元素x∈A但x

B，這與A

B矛盾，所以A＝B。這個定理非常重要，是證明兩個集合相等的基本思路和依據(jù)。第7頁,共82頁，2024年2月25日，星期天24.04.2024定理3.2設(shè)A、B和C是三個集合，則：(1)A

A。(2)A

B∧B

C

A

C。證明

(1)由定義顯然成立。(2)A

B∧B

C

x(x∈A→x∈B)∧

x(x∈B→x∈C)

x((x∈A→x∈B)∧(x∈B→x∈C))

x(x∈A→x∈C)

A

C。定義3.2

設(shè)A和B是兩個集合，若A

B且B中至少有一個元素b使得b

A，則稱A是B的真子集，也稱A真包含于B或B真包含A，記作A

B。否則，記作A

B。B真包含A的符號化表示：第8頁,共82頁，2024年2月25日，星期天24.04.2024A

B

x(x∈A→x∈B)∧

x(x∈B∧x

A)。若兩個集合A和B沒有公共元素，我們說A和B是不相交的。例如，若A＝{a，b，c，d}，B＝{b，c}，則B是A的真子集，但A不是A的真子集。需要指出的是，∈與

表示元素和集合的關(guān)系，而

、

與＝表示集合和集合的關(guān)系。例如，若A＝{0，1}，B＝{0，1，{0，1}}，則A

B且A

B。定理3.3設(shè)A、B和C是三個集合，則(1)

(A

A)。(2)A

B

(B

A)。(3)A

B∧B

C

A

C。第9頁,共82頁，2024年2月25日，星期天24.04.2024證明僅證(2)和(3)(2)A

B

x(x∈A→x∈B)∧

x(x∈B∧x

A)

x(x

A∨x∈B)∧

x(x∈B∧x

A)

x(x∈A∧x

B)∧

x(x

B∨x∈A)

x(x∈A∧x

B)∨

x(x∈A∨x

B)

(

x(x∈A∧x

B)∧

x(x∈A∨x

B))

(

x(x∈A∧x

B)∧

x(x∈B→x∈A))

(B

A)。(3)A

B∧B

C

(

x(x∈A→x∈B)∧

x(x∈B∧x

A))∧(

x(x∈B→x∈C)∧

x(x∈C∧x

B))

x(x∈A→x∈B∧x∈B→x∈C)∧(

x(x∈B∧x

A)∧

x(x∈C∧x

B))

x(x∈A→x∈C)∧(

x(x∈C∧x

A)

A

C。第10頁,共82頁，2024年2月25日，星期天24.04.20243.1.4空集、集族、冪集和全集定義3.3沒有任何元素的集合稱為空集，記作

。以集合為元素的集合稱為集族。例如，{x|x≠x}是空集；{x｜x是某大學(xué)的學(xué)生社團(tuán)}是集族。定理3.4

空集是任何集合的子集。證明任給集合A，則

A

x(x∈

→x∈A)。由于x∈

是假的，所以

x(x∈

→x∈A)為真，于是有

A為真。推論空集是惟一的。對于任一集合A，我們稱空集

和其自身A為A的平凡子集。第11頁,共82頁，2024年2月25日，星期天24.04.2024特別要注意

與{

}的區(qū)別，

是不含任何元素的集合，是任意集合的子集，而{

}是含有一個元素

的集合。定義3.4

一個集合A的所有子集組成的集合稱為A的冪集，記作P(A)或2A。例1

求冪集P(

)、P({

})、P({

，{

}})、P({1，{2，3}})。解

P(

)＝{

}P({

})＝{

，{

}}P({

，{

}})＝{

，{

}，{{

}}，{

，{

}}}P({1，{2，3}})＝{

，{1}，{{2，3}}，{1，{2，3}}}。第12頁,共82頁，2024年2月25日，星期天24.04.2024定理3.5

若|A|＝n，則|P(A)|＝2n。證明因?yàn)锳的m個元素的子集的個數(shù)為Cnm，所以|P(A)|＝Cn0＋Cn1＋…＋Cnn＝2n。定理3.6設(shè)A和B是兩個集合，則：(1)B∈P(A)

B

A。(2)A

B

P(A)

P(B)。(3)P(A)＝P(B)

A＝B。(4)P(A)∈P(B)

A∈B。(5)P(A)∩P(B)＝P(A∩B)。(6)P(A)∪P(B)

P(A∪B)。第13頁,共82頁，2024年2月25日，星期天24.04.2024定義3.5

所要討論的集合都是某個集合的子集，稱這個集合為全集，記作U或E。全集是一個相對的概念。由于所研究的問題不同，所取的全集也不同。例如，在研究整數(shù)間的問題時，可把整數(shù)集Z取作全集。在研究平面幾何的問題時，可把整個坐標(biāo)平面取作全集。第14頁,共82頁，2024年2月25日，星期天24.04.20243.1.5有限冪集元素的編碼表示為便于在計(jì)算機(jī)中表示有限集，可對集合中的元素規(guī)定一種次序，在集合和二進(jìn)制之間建立對應(yīng)關(guān)系。設(shè)U＝{a1，a2，…，an}，對U的任意子集A，A與一個n位二進(jìn)制數(shù)b1b2…bn對應(yīng)，其中bi＝1當(dāng)且僅當(dāng)ai∈A。對于一個n位二進(jìn)制數(shù)b1b2…bn，使之對應(yīng)一個集合A＝{ai|bi＝1}。例如，若A＝{a，b，c}，則A的冪集為P(A)＝{Ai|i∈J}，其中J＝{i|i是二進(jìn)制數(shù)且000≤i≤111}，其中A000＝

，A011＝{b，c}等。一般地P(A)＝{Ai|i∈J}，其中J＝{i|i是二進(jìn)制數(shù)且≤i≤}。第15頁,共82頁，2024年2月25日，星期天24.04.20243.2集合的運(yùn)算與性質(zhì)3.2.1集合的交、并、補(bǔ)

定義3.6

設(shè)A和B為兩個集合，A和B的交集A∩B、并集A∪B分別定義如下：A∩B＝{x|x∈A∧x∈B}A∪B＝{x|x∈A∨x∈B}

顯然，A∩B是由A和B的公共元素組成的集合，A∪B由A和B的所有元素組成的集合。例如，若A＝{1，2，3}，B＝{1，4}，則A∩B＝{1}，A∪B＝{1，2，3，4}。集合的交與并可以推廣到n個集合的情況，即A1∩A2∩…∩An＝{x|x∈A1∧x∈A2∧…∧x∈An}A1∪A2∪…∪An＝{x|x∈A1∨x∈A2∨…∨x∈An}第16頁,共82頁，2024年2月25日，星期天24.04.2024例1設(shè)A和B為兩個集合，且A

B，則A∩C

B∩C。證明對任意的x∈A∩C，則有x∈A且x∈C。而A

B，由x∈A得x∈B，則x∈B且x∈C，從而x∈B∩C。所以，A∩C

B∩C。例2設(shè)A和B為兩個集合，則A

B

A∪B＝B

A∩B＝A。證明對任意的x∈A∪B，則x∈A或x∈B。又A

B，所以x∈B，于是A∪B

B。又顯然有B

A∪B，故A∪B＝B。反之，若A∪B＝B，因A

A∪B，所以A

B。同理可證A

B

A∩B＝A。第17頁,共82頁，2024年2月25日，星期天24.04.2024定義3.7

設(shè)A和B為兩個集合，所有屬于A而不屬于B的元素組成的集合稱為B對于A的補(bǔ)集，或相對補(bǔ)。記作A－B＝{x|x∈A∧x

B}。A－B也稱為A和B的差集。例如，若A＝{1，2，3}，B＝{1，4}，則A－B＝{2，3}，B－A＝{4}。定義3.8

設(shè)U為全集，集合A關(guān)于U的補(bǔ)集U－A稱為集合A的絕對補(bǔ)或余集，記為(或～A或Ac)。即＝{x|x∈U且x

A}。例3

設(shè)A和B為兩個集合，則A－B＝A∩。證明因?yàn)閤∈A－B

x∈A∧x

B

x∈A∧x∈

x∈A∩，所以A－B＝A∩。第18頁,共82頁，2024年2月25日，星期天24.04.2024定理3.7

對于任意3個集合A、B和C，其交、并、補(bǔ)滿足下面10個定律：(1)冪等律A∩A＝A，A∪A＝A(2)結(jié)合律(A∪B)∪C＝A∪(B∪C)，(A∩B)∩C＝A∩(B∩C)(3)交換律A∪B＝B∪A，A∩B＝B∩A(4)分配律A∪(B∩C)＝(A∪B)∩(A∪C)，A∩(B∪C)＝(A∩B)∪(A∩C)(5)同一律A∪

＝A，A∩U＝A第19頁,共82頁，2024年2月25日，星期天24.04.2024(6)零律A∪U＝U，A∩

＝

(7)互補(bǔ)律A∪＝U，A∩＝

(8)吸收律A∪(A∩B)＝A，A∩(A∪B)＝A(9)德·摩根律＝∩，＝∪，A－(B∪C)＝(A－B)∩(A－C)，A－(B∩C)＝(A－B)∪(A－C)(10)雙重否定律＝A以上等式的證明主要用到命題演算的等價式，即欲證集合A＝B，只需證明x∈A

x∈B。也可利用已有的公式證明。第20頁,共82頁，2024年2月25日，星期天24.04.2024定理3.8

任意集合A和B，B＝

A∪B＝U且A∩B＝

。證明如B＝，則A∪B＝A∪＝U，A∩B＝A∩＝

。反之，若A∪B＝U且A∩B＝

，則B＝B∩U＝B∩(A∪)＝(B∩A)∪(B∩)＝

∪(B∩)＝(A∩)∪(B∩)＝(A∪B)∩＝U∩＝。例4

證明A∩(B∪C)＝(A∩B)∪(A∩C)。證明因?yàn)閤∈A∩(B∪C)

x∈A∧x∈(B∪C)

x∈A∧(x∈B∨x∈C)

(x∈A∧x∈B)∨(x∈A∧x∈C)

x∈(A∩B)∨x∈(A∩C)

x∈(A∩B)∪(A∩C)，所以A∩(B∪C)＝(A∩B)∪(A∩C)。第21頁,共82頁，2024年2月25日，星期天24.04.2024例5

證明＝∩。證明因?yàn)閤∈

x

A∪B

x

A∧x

B

x∈∧x∈

x∈∩，所以＝∩。例6

證明A－(B∪C)＝(A－B)∩(A－C)。證明因?yàn)閤∈A－(B∪C)

x∈A∧x

(B∪C)

x∈A∧(x

B∧x

C)

(x∈A∧x

B)∧(x∈A∧x

C)

x∈(A－B)∧x∈(A－C)

x∈(A－B)∩(A－C)，所以A－(B∪C)＝(A－B)∩(A－C)。第22頁,共82頁，2024年2月25日，星期天24.04.2024例7

證明A∩(B－C)＝(A∩B)－(A∩C)。證明

A∩(B－C)＝A∩(B∩)＝(A∩B∩)∪(A∩B∩)＝(A∩B)∩(∪)＝(A∩B)∩＝(A∩B)－(A∩C)。例8

已知A∪B＝A∪C，A∩B＝A∩C，試證B＝C。證明

B＝B∩(A∪B)＝B∩(A∪C)＝(B∩A)∪(B∩C)＝(A∩C)∪(B∩C)＝(A∪B)∩C＝(A∪C)∩C＝C。第23頁,共82頁，2024年2月25日，星期天24.04.20243.2.2集合的對稱差定義3.9

集合A和B的對稱差定義為A

B＝(A－B)∪(B－A)。例如，若A＝{0，{0}}，則P(A)

A＝(P(A)－A)∪(A－P(A))＝{

，0，{{0}}，{0，{0}}}。定理3.9設(shè)A、B和C為三個集合，則：

(1)A

B＝B

A。

(2)(A

B)

C＝A

(B

C)。

(3)A∩(B

C)＝(A∩B)

(A∩C)。第24頁,共82頁，2024年2月25日，星期天24.04.2024(4)A

＝A；A

U＝；A

A＝

；A

＝U。

(5)A

B＝(A∪B)－(A∩B)。

證明僅證(5)A

B＝(A－B)∪(B－A)＝(A∩)∪(B∩)＝((A∩)∪B)∩((A∩)∪)＝(A∪B)∩(∪B)∩(A∪)∩(∪)＝(A∪B)∩(∪)＝(A∪B)－(A∩B)。第25頁,共82頁，2024年2月25日，星期天24.04.20243.2.3廣義并、廣義交運(yùn)算定義3.10

集合A的所有元素的元素組成的集合稱為A的廣義并。符號化表示為：∪A＝{x|

B(B∈A∧x∈B)}。定義3.11集合A的所有元素的公共元素組成的集合稱為A的廣義交。符號化表示為：∩A＝{x|

B(B∈A

x∈B)}。例如，若A＝{{a，b，c}，{a，d，e}，{a，f}}，則∪A＝{a，b，c，d，e，f}，∩A＝{a}。由定義可知，廣義交和廣義并是針對集族而言的，對于非集族來說，其廣義交和廣義并均為空集。第26頁,共82頁，2024年2月25日，星期天24.04.2024定理3.10設(shè)A和B為兩個集合，則：(1)∪{A}＝A。(2)∪(A∪B)＝(∪A)∪(∪B)。證明

(1)因?yàn)閤∈∪{A}

B(B∈{A}∧x∈B)

A∈{A}∧x∈A

x∈A，所以∪{A}＝A(2)因?yàn)閤∈∪(A∪B)

C(C∈A∪B∧x∈C)

C((C∈A∨C∈B)∧x∈C)

C((C∈A∧x∈C)∨(C∈B∧x∈C))

C(C∈A∧x∈C)∨

C(C∈B∧x∈C)

x∈∪A∨x∈∪B

x∈(∪A)∪(∪B)，所以∪(A∪B)＝(∪A)∪(∪B)。第27頁,共82頁，2024年2月25日，星期天24.04.2024定理3.11設(shè)A和B為兩個集合，則：(1)∩{A}＝A。(2)∩{A，B}＝A∩B。證明

(1)因?yàn)閤∈∩{A}

B(B∈{A}

x∈B)

A∈{A}

x∈A

x∈A，所以∩{A}＝A。(2)因?yàn)閤∈∩{A，B}

C(C∈{A，B}

x∈C)

(A∈{A，B}

x∈A)∧(B∈{A，B}

x∈B)

x∈A∧x∈B

x∈A∩B，所以∩{A，B}＝A∩B。第28頁,共82頁，2024年2月25日，星期天24.04.20243.2.4集合的文氏圖集合之間的相互關(guān)系和運(yùn)算還可以用文氏圖來描述，它有助于我們理解問題，有時對解題也很有幫助。在不要求有求解步驟的題目中，我們可以使用文氏圖求解，但它不能用于題目的證明。在文氏圖中，用矩形表示全集U，矩形內(nèi)部的點(diǎn)均為全集中的元素，用圓或橢圓表示U的子集，其內(nèi)部的點(diǎn)表示不同集合的元素，并將運(yùn)算結(jié)果得到的集合用陰影部分表示。圖3-1表示了集合的5種基本運(yùn)算，陰影部分表示經(jīng)過相應(yīng)運(yùn)算得到的。第29頁,共82頁，2024年2月25日，星期天24.04.2024第30頁,共82頁，2024年2月25日，星期天24.04.20243.3集合的劃分與覆蓋在集合的研究中，除了進(jìn)行集合之間的比較外，還要對集合的元素進(jìn)行分類。這一節(jié)將討論集合的劃分問題。定義3.12

設(shè)S＝{A1，A2，…，An}是集合A的某些非空子集組成的集合，若＝A，則稱S為集合A的一個覆蓋。定義3.13

設(shè)

＝{A1，A2，…，An}是集合A的某些非空子集組成的集合，若＝A，且Ai∩Aj＝

(i≠j)，則稱

為A的一個劃分，稱

中的元素為A的劃分塊。第31頁,共82頁，2024年2月25日，星期天24.04.2024由定義知，劃分一定是覆蓋，但反之則不然。例如，S＝{{a}，{b，c}，{c}}是A＝{a，b，c}的覆蓋，但不是A的劃分。例1設(shè)有整數(shù)集Z，res5(x)表示整數(shù)x被5除后所得的余數(shù)。令A(yù)i＝{x|x∈Z∧res5(x)＝i∧i∈Z5}，則{A0，A1，A2，A3，A4}作成Z的一個劃分。解由題設(shè)得：A0＝{…，－10，－5，0，5，10，…}，A1＝{…，－9，－4，1，6，11，…}，A2＝{…，－8，－3，2，7，12，…}，A3＝{…，－7，－2，3，8，13，…}，A4＝{…，－6，－1，4，9，14，…}。于是，＝Z，且Ai∩Aj＝

(i≠j)。所以，{A0，A1，A2，A3，A4}是Z的一個劃分。第32頁,共82頁，2024年2月25日，星期天24.04.2024例2

求集合A＝{a，b，c}的所有不同的劃分。解其不同的劃分共有5個：

1＝{{a}，，{c}}，

2＝{{a}，{b，c}}，

3＝{{a，c}，}，

4＝{{a，b}，{c}}，

5＝{{a，b，c}}。定理3.12

設(shè){A1，A2，…，Ar}和{B1，B2，…，Bs}是同一集合A的兩種劃分，則其所有Ai∩Bj≠

組成的集合也是原集合的一種劃分。定義3.14

設(shè){A1，A2，…，Ar}和{B1，B2，…，Bs}是同一集合A的兩種劃分，則稱其所有Ai∩Bj≠

組成的集合為原來兩劃分的交叉劃分。第33頁,共82頁，2024年2月25日，星期天24.04.2024定義3.15

給定A的兩個劃分{A1，A2，…，Ar}和{B1，B2，…，Bs}，若對于每個Aj都有Bk使得Aj

Bk，則稱{A1，A2，…，Ar}為{B1，B2，…，Bs}的加細(xì)。定理3.13

任何兩種劃分的交叉劃分，都是原來各劃分的一種加細(xì)。證明設(shè){A1，A2，…，Ar}和{B1，B2，…，Bs}的交叉劃分為T，對于T中任意元素Ai∩Bj必有Ai∩Bj

Ai和Ai∩Bj

Bj，故T必是原劃分的加細(xì)。例3

設(shè)A1、A2和A3是全集U的子集，則形如Ai

(Ai

為Ai或)的集合稱為由A1、A2和A3產(chǎn)生的小項(xiàng)。試證由A1、A2和A3所產(chǎn)生的所有非空小項(xiàng)的集合構(gòu)成全集U的一個劃分。第34頁,共82頁，2024年2月25日，星期天24.04.2024證明小項(xiàng)共8個，設(shè)有r個非空小項(xiàng)s1、s2、…、sr(r≤8)。對任意的a∈U，則a∈Ai或a∈，兩者必有一個成立，取Ai

為包含元素a的Ai或，則a∈Ai

，即有a∈si，于是U

si。又顯然有si

U，所以U＝si。任取兩個非空小項(xiàng)sp和sq，若sp≠sq，則必存在某個Ai和分別出現(xiàn)在sp和sq中，于是sp∩sq＝

。綜上可知，{s1，s2，…，sr}是U的一個劃分。第35頁,共82頁，2024年2月25日，星期天24.04.20243.4排列與組合3.4.1加法與乘法原理在組合計(jì)數(shù)的計(jì)算和研究中，加法原理和乘法原理是兩個最常用也是最基本的原理。加法原理若事件的有限集合S＝S1∪S2∪…∪Sn，且S1、S2、…、Sn兩兩不相交，則|S|＝|S1|＋|S2|＋…＋|Sn|

乘法原理若事件的有限集合S是依次取自有限集合S1、S2、…、Sn中事件的序列的集合，則|S|＝|S1|×|S2|×…×|Sn|第36頁,共82頁，2024年2月25日，星期天24.04.2024例1

求由數(shù)字1、2、3、4、5組成的小于1000的數(shù)(每個數(shù)字都允許重復(fù)出現(xiàn))的個數(shù)。解在三位數(shù)中，每一個數(shù)位上的數(shù)字都有5種不同的選取法，由乘法原理知，滿足條件的三位數(shù)的個數(shù)是53個。同理可知，滿足條件的二位數(shù)和一位數(shù)的個數(shù)分別為52個和5個。再由加法原理知，滿足條件的自然數(shù)總共有53＋52＋5＝155個。第37頁,共82頁，2024年2月25日，星期天24.04.20243.4.2排列和組合

1.排列定義3.16集合S有n個元素，從中選取r個元素作有序排列，且在排列中不允許任何元素重復(fù)出現(xiàn)，則稱這種排列為S的r―無重復(fù)排列。當(dāng)r＝n時，稱其為全排列。S的所有r―無重復(fù)排列的個數(shù)記為P(n，r)或Pnr。定理3.14

n個元素的r―無重復(fù)排列的個數(shù)為：P(n，r)＝n(n－1)(n－2)…(n－r＋1)。當(dāng)r＝n時，P(n，n)＝n!

證明在從n個不同的元素中按順序取出r個元素時，第一個元素有n種不同的選法，第2個元素有n－1種不同的選法，…，第r個元素從剩下的n－r＋1個元素中選取，有n－r＋1種不同的選法。根據(jù)乘法原理，順序選取r個元素共有的不同選取方法數(shù)為：P(n，r)＝n(n－1)(n－2)…(n－r＋1)。第38頁,共82頁，2024年2月25日，星期天24.04.2024例2

從1、2、…、9中選取數(shù)字構(gòu)成3位數(shù)，如要求每個數(shù)字都不相同，問共有多少種方法？解從1、2、…、9中選取百位數(shù)，共9種選法，再從剩下的數(shù)字中選取十位數(shù)，共8種選法，最后從剩下的數(shù)字中選取個位數(shù)，共7種選法。因此，從1、2、…、9中選取數(shù)字構(gòu)成3位數(shù)共有9×8×7＝504種方法。定義3.17r―無重復(fù)排列可以看作是將選出的r個元素排列在一條直線上的排列，這時也稱為r―線狀排列。如果把這r個元素排列在一個圓周上，則這種排列稱為S的r―圓排列。對兩個圓排列，若其中一個圓排列可以由另一個圓排列通過旋轉(zhuǎn)而得到，則認(rèn)為這兩個圓排列在本質(zhì)上是同一個圓排列。于是有下面的結(jié)論成立。第39頁,共82頁，2024年2月25日，星期天24.04.2024定理3.15

n個元素的r―圓排列的個數(shù)N(n，r)為證明為了得到n個元素的r―無重復(fù)排列，可以先從n個元素中選取r個元素作r―圓排列，這種圓排列的個數(shù)是N(n，r)。然后，將這個r―圓排列斷開后即可得到線狀的r―無重復(fù)排列。因?yàn)閺膔個不同的位置處斷開，由乘法原理可得P(n，r)＝rN(n，r)，即例3

有8個人圍著圓桌進(jìn)餐，如果要求每餐坐的順序不同，那么他們在一起最多能共進(jìn)幾天餐？解首先8－圓排列數(shù)為8!/8，又一日三餐，故他們一起能共餐8!/(8×3)＝1680天。第40頁,共82頁，2024年2月25日，星期天24.04.20242.組合定義3.18集合S有n個元素，從中選取r個元素，若不考慮它們的排列順序，且在選取中不允許元素重復(fù)出現(xiàn)，稱這種選取方式為S的r―無重復(fù)組合。S的所有r―無重復(fù)組合的個數(shù)記為C(n，r)或Cnr。定理3.16n個元素的r―無重復(fù)組合的個數(shù)為C(n，r)＝＝。證明為了得到n個元素的r―無重復(fù)排列，可以先從n個元素中選取r個元素作r―無重復(fù)組合，這種無重復(fù)組合的個數(shù)是C(n，r)，然后將這r個取出的元素作r―無重復(fù)排列，這種r―無重復(fù)排列的個數(shù)是P(r，r)＝r!。由乘法原理可得P(n，r)＝r!C(n，r)，即C(n，r)＝＝。第41頁,共82頁，2024年2月25日，星期天24.04.2024例4

從1、2、…、300之中任取3個數(shù)，使得它們的和能被3整除，問有多少種方法？解把1、2、…、300分成A、B和C三組，A＝{3k＋1|k∈Z}，B＝{3k＋2|k∈Z}，C＝{3k|k∈Z}。任取三個數(shù)i、j、k，那么選取是無序的且滿足i＋j＋k能被3整除。將選法分為兩類：都取自同一組，方法數(shù)3C(100，3)。分別取自A、B和C，方法數(shù)(C(100，1))3。由加法原則，總?cè)?shù)為3C(100，3)＋(C(100，1))3＝1485100。第42頁,共82頁，2024年2月25日，星期天24.04.20243.4.3排列與組合的生成

1.排列的生成排列的生成算法有詞典順序法、逆序法和遞歸排序法等。在這里僅介紹詞典順序法。設(shè)S＝{1，2，…，n}，(a1，a2，…，an)和(b1，b2，…，bn)是S的兩個排列，若存在i∈{1，2，…，n}，使得對一切j＝1，2，…，i有aj＝bj而ai＋1＜bi＋1，則稱排列(a1，a2，…，an)字典序小于(b1，b2，…，bn)，并記為(a1，a2，…，an)(b1，b2，…，bn)。若(a1，a2，…，an)(b1，b2，…，bn)，且不存在異于(a1，a2，…，an)和(b1，b2，…，bn)的排列(c1，c2，…，cn)，使得(a1，a2，…，an)(c1，c2，…，cn)(b1，b2，…，bn)，則稱(b1，b2，…，bn)為(a1，a2，…，an)的下一個排列。第43頁,共82頁，2024年2月25日，星期天24.04.2024定理3.17對S的兩個排列，(b1，b2，…，bn)是(a1，a2，…，an)的下一個排列的充要條件是：(1)存在m∈{1，2，…，n}，使得對一切i＝1，2，…，m－1有ai＝bi，am＜bm，am＜am＋1且am＋1＞am＋2＞…＞an；(2)bm＝min{aj|aj＞am，j＝m＋1，m＋2，…，n}；(3)bm＋1＜bm＋2＜…＜bn。由此定理可建立生成所有排列的算法：步1：置(a1，a2，…，an)＝(1，2，…，n)步2：設(shè)已有排列(a1，a2，…，an)，置i＝n；步2.1：若ai＞ai－1，則記m＝i－1，令bm＝min{aj|aj＞am，j＝i，i＋1，…，n}，并將(am，am＋1，…，an)\{bm}第44頁,共82頁，2024年2月25日，星期天24.04.2024中的元素由小到大排起來，記這個排列為(bm＋1，am＋2，…，an)。置(a1，a2，…，am－1，am，am＋1，…，an)＝(a1，a2，…，am－1，bm，bm＋1，…，bn)然后返回步2。步2.2：若ai＜ai－1，則當(dāng)i－1＞1時，置i＝i－1，返回步2.1。當(dāng)i－1＝1時，算法終止。例5S＝{1，2，3，4}，求其全排列。解1234

1243

1324

1342

1423

1432

2134

2143

2314

2341

2413

2431

3124

3142

3214

3241

3412

3421

4123

4132

4213

4231

4312

4321。第45頁,共82頁，2024年2月25日，星期天24.04.20242.組合的生成定理3.18(a1，a2，…，ar)和(b1，b2，…，br)是S的兩個不同的r－子集，則(b1，b2，…，br)是(a1，a2，…，ar)的下一個子集的充要條件是：(1)存在1≤m≤r，使得對一切i＝1，2，…，m－1有ai＝bi，對一切i＞m有am＝n－r＋i；(2)bm＝am＋1；(3)對于m≤j≤r－1，有bj＋1＝bj＋1。由此定理可建立生成所有子集的算法：步1：設(shè)S＝{1，2，…，n}，取(a1，a2，…，ar)＝(1，2，…，r)第46頁,共82頁，2024年2月25日，星期天24.04.2024步2：設(shè)已有S的r子集(a1，a2，…，ar)，置i＝r；步2.1：若ai＜n－r＋i，則令bi＝ai＋1，并且對j＝i，i＋1，…，r－1，置bj＋1＝bj＋1。然后置(a1，a2，…，ar)＝(a1，a2，…，ai－1，bi，bi＋1，…，br)，然后返回步2。步2.2：若ai＝n－r＋i，則當(dāng)i＞1時，置i＝i－1，返回步2.1。當(dāng)i＝1時，算法終止。例6

S＝{1，2，3，4，5，6}，求其所有4元素子集。解

1234

1235

1236

1245

1246

1256

1345

1346

1356

1456

2345

2346

2356

2456

3456。第47頁,共82頁，2024年2月25日，星期天24.04.20243.5歸納原理

3.5.1結(jié)構(gòu)歸納原理設(shè)集合A是歸納定義的集合，現(xiàn)欲證A中所有元素具有性質(zhì)P，即證：對于任意x∈A有P(x)為真?？蛇M(jìn)行如下證明：

(1)(歸納基礎(chǔ))證明歸納定義基礎(chǔ)條款中規(guī)定的A的基本元素x均使P(x)為真。

(2)(歸納推理)證明歸納定義的歸納條款是“保性質(zhì)P的”。即在假設(shè)歸納條款中已確定元素x1、x2、…、xn使P(xi)(i＝1，2，…，n)真的前提下，證明用歸納條款中的操作g所生成元素g(x1，x2，…，xn)依然具有性質(zhì)P，即P(g(x1，x2，…，xn))為真。第48頁,共82頁，2024年2月25日，星期天24.04.2024由于A僅由(1)和(2)條款所確定的元素組成，因此當(dāng)上述證明過程完成時，“A中所有元素具有性質(zhì)P”得證。這種推理原理稱為歸納原理，應(yīng)用這一原理進(jìn)行證明的方法稱為歸納法。為區(qū)別通常所說的數(shù)學(xué)歸納法，它又稱為“結(jié)構(gòu)歸納法”。數(shù)學(xué)歸納法是其一種特例。第49頁,共82頁，2024年2月25日，星期天24.04.20243.5.2數(shù)學(xué)歸納原理將上述原理應(yīng)用到自然數(shù)集上進(jìn)行歸納推理，就是我們所說的數(shù)學(xué)歸納法。

1.第一數(shù)學(xué)歸納法用第一數(shù)學(xué)歸納法證明所有自然數(shù)具有性質(zhì)P時，只要如下推理：

(1)歸納基礎(chǔ)：證P(0)真，即證明數(shù)0具有性質(zhì)P。

(2)歸納過程：對任意k(≥0)，假設(shè)P(k)真(歸納假設(shè)“k滿足性質(zhì)P”)時，推出P(k＋1)真。

(3)結(jié)論：所有自然數(shù)具有性質(zhì)P。第50頁,共82頁，2024年2月25日，星期天24.04.2024例1

用歸納法證明：對任意的自然數(shù)n，有(0＋1＋2＋…＋n)2＝03＋13＋23＋…＋n3。證明當(dāng)n＝0時，n2＝03。假設(shè)n＝k時，(0＋1＋2＋…＋k)2＝03＋13＋23＋…＋k3，那么n＝k＋1時，(0＋1＋2＋…＋k＋k＋1)2＝(0＋1＋2＋…＋k)2＋2(0＋1＋2＋…＋k)(k＋1)＋(k＋1)2

＝03＋13＋23＋…＋k3＋k(k＋1)2＋(k＋1)2＝03＋13＋23＋…＋k3＋(k＋1)3所以，對任意自然數(shù)結(jié)論成立。第51頁,共82頁，2024年2月25日，星期天24.04.20242.第二數(shù)學(xué)歸納法用第二數(shù)學(xué)歸納法證明所有自然數(shù)具有性質(zhì)P時，只要如下推理：(1)歸納基礎(chǔ)：證P(0)真，即證明數(shù)0具有性質(zhì)P。(2)歸納過程：對任意k(≥0)，假設(shè)P(i)真，k＞i≥0(歸納假設(shè)“0，1，…，k－1滿足性質(zhì)P”)時，推出P(k)真。(3)結(jié)論：所有自然數(shù)具有性質(zhì)P。例2

有數(shù)目相同的兩堆棋子(每堆棋子數(shù)為n)，甲、乙兩人玩取棋子游戲。規(guī)定兩人輪流取棋子，每次兩人取子數(shù)相同，不能不取，也不能同時在兩堆中取子，取得最后一枚棋子者為勝者。求證：后取者必勝。第52頁,共82頁，2024年2月25日，星期天24.04.2024證明不妨設(shè)甲為先取者，乙為后取者。當(dāng)n＝1時，兩堆各有一枚棋子，甲必先從一堆中取走一枚棋子，余下最后一枚棋子必被乙取走，乙勝。假設(shè)n＜k時乙必勝。下證n＝k時也是乙必勝。設(shè)第一輪取子時，甲從一堆中取走r枚棋子，余下k－r＜k枚棋子，那么，乙從另一堆中也取走r枚棋子，亦留下k－r＜k枚棋子。若(1)r＝k，那么乙取走最后一枚棋子，乙勝。(2)1＜r＜k，那么1＜k－r＜k。對留下的兩堆棋子，每一堆為k－r枚，由歸納假設(shè)，在以后甲乙的搏奕中乙必勝。因此全局也是乙必勝。第53頁,共82頁，2024年2月25日，星期天24.04.20243.6容斥原理和抽屜原理3.6.1容斥原理設(shè)集合A是歸納定義的集合，現(xiàn)欲證A中所有元素具有性質(zhì)P，即證：對于任意x∈A有P(x)為真?？蛇M(jìn)行如下證明：

(1)(歸納基礎(chǔ))證明歸納定義基礎(chǔ)條款中規(guī)定的A的基本元素x均使P(x)為真。

(2)(歸納推理)證明歸納定義的歸納條款是“保性質(zhì)P的”。即在假設(shè)歸納條款中已確定元素x1、x2、…、xn使P(xi)(i＝1，2，…，n)真的前提下，證明用歸納條款中的操作g所生成元素g(x1，x2，…，xn)依然具有性質(zhì)P，即P(g(x1，x2，…，xn))為真。第54頁,共82頁，2024年2月25日，星期天24.04.2024集合的運(yùn)算，可用于有限個元素的計(jì)數(shù)問題。在有限集的元素計(jì)數(shù)問題中，容斥原理有著廣泛的應(yīng)用。定理3.19(容斥原理)

對有限集合A和B，有|A∪B|＝|A|＋|B|－|A∩B|。證明因?yàn)锳∪B＝B∪(A－B)且B∩(A－B)＝

，所以|A∪B|＝|B|＋|A－B|。又因?yàn)锳＝(A－B)∪(A∩B)且(A－B)∩(A∩B)＝

，所以|A|＝|A－B|＋|A∩B|。故|A∪B|＝|A|＋|B|－|A∩B|。定理3.20

推廣到n個集合A1，A2，…，An的情形，有：|A1∪A2∪…∪An|＝∑i|Ai|－∑i＜j|Ai∩Aj|＋∑i＜j＜k|Ai∩Aj∩Ak|－…＋(－1)n－1|A1∩A2∩…∩An|。第55頁,共82頁，2024年2月25日，星期天24.04.2024例1

一個班有50個學(xué)生，在第一次考試中得95分的有26人，在第二次考試中得95分的有21人，如果兩次考試中沒有得95分的有17人，那么兩次考試都得95分的有多少人？解設(shè)A和B分別表示在第一次和第二次考試中得95分的學(xué)生的集合。則：|A|＝26，|B|＝21，＝17。于是＝50－＝50－(|A|＋|B|－|A∩B|)，從而|A∩B|＝－50＋|A|＋|B|＝17－50＋26＋21＝14。所以，兩次考試都得95分的有14人。例2

從{1，2，3，4，5，6，7，8，9}中取7個不同的數(shù)字構(gòu)成7位數(shù)，如不允許5和6相鄰，總共有多少種方法？第56頁,共82頁，2024年2月25日，星期天24.04.2024解任取7個不同的數(shù)字構(gòu)成7位數(shù)的個數(shù)為＝9!/2，5和6相鄰的個數(shù)為6！(2！)＝6×7！，根據(jù)容斥原理，總共有9!/2－6×7!＝151200種方法。例3

某班有25名學(xué)生，其中14人會打籃球，12人會打排球，6人會打籃球和排球，5人會打籃球和網(wǎng)球，還有2人會打這三種球。而6個會打網(wǎng)球的人都會打另外一種球，求不會打這三種球的人數(shù)。解設(shè)A、B、C分別表示會打排球、網(wǎng)球和籃球的學(xué)生集合。則：第57頁,共82頁，2024年2月25日，星期天24.04.2024|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，

|B∩C|=5,|A∩B∩C|＝2，|(A∪C)∩B|＝6。因?yàn)閨(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，＝25－20＝5。故，不會打這三種球的共5人。在不要求嚴(yán)格步驟的情況下，以上各題也可通過文氏圖的方法來求解。下面以例3加以說明：設(shè)A、B、C分別表示會打排球、網(wǎng)球和籃球的學(xué)生集合。該問題的文氏圖如圖3-2所示。由題意可得：第58頁,共82頁，2024年2月25日，星期天24.04.2024|I2|＋|I3|＋|I4|＋|I5|＝12|I4|＋|I5|＋|I6|＋|I7|＝6|I1|＋|I2|＋|I5|＋|I6|＝14|I2|＋|I5|＝6|I5|＋|I6|＝5|I5|＝2|I4|＋|I5|＋|I6|＝6根據(jù)上面各等式，依次求得：第59頁,共82頁，2024年2月25日，星期天24.04.2024|I1|＝5，|I2|＝4，|I3|＝5，|I4|＝1，|I5|＝2，|I6|＝3，|I7|＝0。所以，＝25－|A∪B∪C|＝25－(|I1|＋|I2|＋|I3|＋|I4|＋|I5|＋|I6|＋|I7|)＝25－(5＋4＋5＋1＋2＋3＋0)＝5。故，不會打這三種球的共5人。第60頁,共82頁，2024年2月25日，星期天24.04.20243.6.2抽屜原理(鴿巢原理)

抽屜原理是一個十分基本、非常重要、應(yīng)用極其廣泛的數(shù)學(xué)原理，是解決數(shù)學(xué)中的一類存在性問題的基本工具。定理3.21(抽屜原理)(1)把多于n個元素的集合S分成n個子集S1、S2、…、Sn的并集，那么至少存在一個集合Si，它包含S中的兩個或兩個以上的元素。

(2)把多于mn個元素的集合S分成n個子集S1、S2、…、Sn的并集，那么至少存在一個集合Si，它包含S中的m＋1或m＋1以上的元素。證明僅證(2),反證法。

(2)若結(jié)論不成立，則對于任意子集Si，有|Si|≤m，于是|S|≤|S1|＋|S2|＋…＋|Sn|≤mn，矛盾。第61頁,共82頁，2024年2月25日，星期天24.04.2024例3

在從1到2n的整數(shù)中，任意選取n＋1個數(shù)，證明在這n＋1個數(shù)中總存在兩個數(shù)，使得其中一個數(shù)是另一個的倍數(shù)。證明設(shè)S＝{1，2，…，2n}，Si＝{a|a∈S，且存在k∈N使得a＝2k(2i－1)}，i＝1，2，…，n。于是S＝S1∪S2∪…∪Sn，則n＋1個數(shù)中必有兩個數(shù)在S的同一個子集Si中，這兩個數(shù)中的一個數(shù)是另一個的偶數(shù)倍。例4

在邊長為1的正方形內(nèi)任意放置九個點(diǎn)，證明其中必存在三個點(diǎn)，使得由它們組成的三角形(可能是退化的)面積不超過1/8。證明把邊長為1的正方形分成四個全等的小正方形，則至少有一個小正方形內(nèi)有三個點(diǎn)，它們組成的三角形(可能是退化的)面積不超過小正方形的一半，即1/8。第62頁,共82頁，2024年2月25日，星期天24.04.20243.7遞推關(guān)系

3.7.1遞推關(guān)系的概念

有些計(jì)數(shù)問題往往與求一個數(shù)列的通項(xiàng)有關(guān)。但在一些復(fù)雜的特定條件下要直接求出這個數(shù)列的通項(xiàng)公式，有時十分困難。而在同樣的條件下，寫出該數(shù)列相鄰項(xiàng)之間的關(guān)系，再利用一定的方法和技巧，卻往往能很容易的得到所要的結(jié)論。

例1

斐波那契數(shù)列(Fibonacci)問題假定一對兔子兩個月成熟后，每月生一對兔子。按照假定，一對剛出生的兔子在n個月后，共有多少對兔子？解設(shè)第n個月的兔子數(shù)為Fn，由題意得F0＝1F1＝1Fn＝Fn－1＋Fn－2，n≥2第63頁,共82頁，2024年2月25日，星期天24.04.2024例2漢諾塔(Hanoi)問題有三根立柱A、B、C以及n個大小不同的圓盤套在立柱A上，大的圓盤在下面，小的圓盤在上面，構(gòu)成一個塔形?，F(xiàn)在要把這n個圓盤移到立柱B上?？梢岳眠@三根立柱，每次只能移動一個圓盤，但不允許將它放在較小的圓盤上，問最少需移動多少次？解令Hn為完成這樣的一次移動至少必須移動圓盤的次數(shù)。為了把n個圓盤從立柱A移到立柱B，可先將n－1個圓盤從立柱A移到立柱C，留下最大的圓盤，移動的次數(shù)為Hn－1；然后再將最大的圓盤移動到立柱B，移動1次；最后將n－1個圓盤從立柱C移到立柱B，移動次數(shù)為Hn－1。第64頁,共82頁，2024年2月25日，星期天24.04.2024于是有Hn＝2Hn－1＋1，n≥2，其中H1＝1。以上的例子有一個共同的特點(diǎn)，即從我們在計(jì)數(shù)問題所得出的數(shù)列中，它的一般項(xiàng)可用它自身數(shù)列中的前面若干項(xiàng)來表達(dá)。這樣，從給定的初始值出發(fā)，利用所建立的關(guān)系式可以依次算出數(shù)列中的每一項(xiàng)。我們稱這些關(guān)系式為遞推關(guān)系。下面我們介紹遞推關(guān)系的幾種解法。第65頁,共82頁，2024年2月25日，星期天24.04.20241.遞推關(guān)系的生成函數(shù)解法設(shè){a0，a1，…，an，…}為一個無窮數(shù)列，我們稱f(t)＝a0＋a1t＋…＋antn＋…為該數(shù)列的生成函數(shù)。例3

數(shù)列{1，1，…，1，…}的生成函數(shù)為＝1＋t＋…＋tn＋…。將遞推關(guān)系代入數(shù)列的生成函數(shù)的系數(shù)中去，通過計(jì)算可以得到生成函數(shù)的顯式，然后再將它展開成冪級數(shù)就可求得數(shù)列的通項(xiàng)。例4

斐波那契數(shù)列問題解設(shè)F(x)＝為斐波那契數(shù)列的生成函數(shù)，則有第66頁,共82頁，2024年2月25日，星期天24.04.2024F(x)＝F0＋F1x＋＝1＋x＋＝1＋x＋x＋xn＝1＋x＋x(F(x)－1)＋x2F(x)從上面關(guān)系式可以解出F(x)＝＝＝＝比較等式兩邊xn的系數(shù)，得到Fn＝。第67頁,共82頁，2024年2月25日，星期天24.04.20242.常系數(shù)線性齊次遞推關(guān)系的解法我們把形如H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝0(其中H(n)、H(n－1)、…、H(n－k)是n的函數(shù))的遞推關(guān)系式稱為常系數(shù)線性齊次遞推關(guān)系，并稱xk＋b1xk－1＋b2xk－2＋…＋bk＝0為其特征方程，它的根稱為其特征根。在使用特征根方法求解遞推關(guān)系時要用到下面三個定理，其證明參見相關(guān)文獻(xiàn)。定理3.22

設(shè)q為非零的實(shí)數(shù)或復(fù)數(shù)，則H(n)＝qn是遞推關(guān)系式H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝0(k≤n，bk≠0)的解當(dāng)且僅當(dāng)q是它的一個特征根。第68頁,共82頁，2024年2月25日，星期天24.04.2024定理3.23

設(shè)q1、q2、…、qk為非零的實(shí)數(shù)或復(fù)數(shù)，則H(n)＝C1q1n＋C2q2n＋…＋Ckqkn(C1、C2、…、Ck是確定的常數(shù))是遞推關(guān)系式H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝0(k≤n，bk≠0)的解當(dāng)且僅當(dāng)q1、q2、…、qk是它的k個不同的特征根。定理3.24

設(shè)q1、q2、…、qk為非零的實(shí)數(shù)或復(fù)數(shù)，它們是遞推關(guān)系式H(n)＋b1H(n－1)＋b2H(n－2)＋…＋bkH(n－k)＝0(k≤n，bk≠0)的特征方程的t(t≤k)個不同的特征根，各有e1、e2、…、et重。則遞推關(guān)系式的一般解是H(n)＝H1(n)＋H2(n)＋…＋Ht(n)，其中Hi(n)＝C1qin＋C2nqin＋…＋qin(i＝1，2，…，t；C1，C2，…，為確定的常數(shù))。例6

斐波那契數(shù)列問題第69頁,共82頁，2024年2月25日，星期天24.04.2024解遞推關(guān)系Fn＝Fn－1＋Fn－2的特征方程為x2―x―1