组合数学.

组合数学第一章排列和组合1.1计数的基本原则相等原则：设A、B是两个有限集，如果存在由A到B上一个一一对应映射（即双射），则|A|=|B|.加法原则：设A是有限集，),,...2,1(kiAAi如果kiiAA1且jiAAφ（1≤i＜j≤k），则kiiAA1.★定理1.1已知做一件事要经过两个步骤，完成第一个步骤的方法有m种，完成第一个步骤之后，完成第二个步骤的方法有n种，则做这件事情的方法共有mn种.★定理1.2（乘法原则）：已知做一件事情要依次经过k个步骤，且在已完成前面i-1（1≤i≤k）个步骤的情况下，完成第i个步骤有in种方法，则做这件事情的方法共有kiiknnnn121种.1.2排列n元集的r-排列☻定义1.1设A是n元集，如果序列raaa21中的r个元raaa,,,21都属于A且彼此互异，则称序列raaa21是n元集A的一个r-排列，并称ka（1≤k≤r）是该r-排列的第k个元，或称ka在该r-排列中排在第k位.☻定义1.2n元集A={naaa,,,21}的n-排列称为n元集A的一个全排列，亦称为由naaa,,,21作成的一个全排列.定理1.3设n，r（n≥r）是正整数，以P(n,r)表示n元集的r-排列的个数，则)!(!)1()1(),(rnnrnnnrnP推论1.1n元集的全排列的个数为n！n元集的r-可重复排列☻定义1.3设A为n元集，如果序列raaa21的元素都属于A，则称序列raaa21是n元集A的一个r-可重复排列.★定理1.4n元集的r-可重复排列的个数为rn.多重集的排列☻定义1.4由kkananan个个个,,,2211组成的集合M记为},,,{2211kkanananM，M称为多重集，也称M是一个n-多重集，其中knnnn21.☻定义1.5设},,,{2211kkanananM，是集合},,,{21kaaaA的一个n-可重复排列且中有kkananan个个个,,,2211，则称是多重集M的一个全排列，此时也称是由kkananan个个个,,,2211作成的全排列。★定理1.5多重集},,,{2211kkanananM的全排列的个数为!!!)!(2121kknnnnnn☻定义1.6设},,,{2211kkanananM和},,,{2211kkasasasA都是多重集，且iins0（1≤i≤k），则称MA是的一个子集，如果rsssk21，则称MA是的一个r-子集.☻定义1.7设},,,{2211kkanananM是多重集，是M的某个r-子集的全排列，则称是M的一个r-排列.1.3T路的计数☻定义1.8由p×q个单位正方形拼成的长为p，宽为q的长方形叫做一个p×q棋盘.★定理1.6沿p×q棋盘上的线段，由顶点A到顶点B的最短路的条数为q!p!q)!p(.☻定义1.9在Oxy坐标平面上，横坐标与纵坐标都是整数的点叫做整点.由任一个整点（x，y）到整点（x+1，y+1）或（x+1，y-1）的有向线段叫做一个T步.☻定义1.10由整点A到整点B的一条T路是指由若干个T步组成的起点为A、终点为B的有向折线.★定理1.7如果存在由整点),(aA到整点),(bB的T路，则：①b＞a.②b-a≥│β-α│.③a+α与b+β的奇偶性相同.上述三给条件合称为T条件.★定理1.8设整点),(aA与整点),(bB满足T条件，则由A到B的T路的条数为)!22()!22()!(ababab.★定理1.9（反射定理）设整点),(aA与整点),(bB满足T条件，且,,0,0ab则由A到B且经过x轴（即与x轴有交点）的T路的条数等于由),('aA到B的T路的条数，为)!22()!22()!(ababab★定理1.10设整点),(aA与整点),(bB满足T条件，且,,0,0ab则由A到B且不经过x轴的T路的条数为)!22()!22()!()!22()!22()!(abababababab★定理1.11（1）由点O（0,0）到点V（2n，0），中途不经过x轴且位于上半平面的T路的条数为)!1(!)!22(nnn.（2）由点O（0,0）到点V（2n，0）且位于上半平面的T路的条数为!)!1()!2(nnn.令nnCnnnnC),,3,2,1()!1(!)!22(叫做Catalan（卡塔兰）数★定理1.12以nS2表示满足条件）（或njxnjjxxxnxxxjjn2,,2,110)12,,2,1(2121221的解),,,(221nxxx的集合，则)!1(!)!22(2nnnCSnn.★定理1.13以n2T表示满足条件）（或njxnjjxxxnxxxjjn2,,2,110)12,,2,1(2121221的解),,,(221nxxx的集合，则!)!1()!2(12nnnCTnn.1.4组合n元集的r-组合☻定义1.11集合A的含有r个元素的子集称为A的一个r-组合.设},,,{21naaaA是n元集，则A的任一个r-组合可表成},,,{21riiiaaa，其中riii,,,21均是整数，且niiir211.以rnC或rn表示n元集的r-组合的个数，简称为组合数.★定理1.14设n是正整数，r是非负整数，则.0,)!(!,0时当！时；当nrrnrnnrrnn元集的r-可重复组合☻定义1.12从集合A中可重复地选取r个元作成的多重集，称为集合A的一个r-可重复组合.★定理1.15n元集的r-可重复组合的个数为rrn1.推论1.2不定方程rxxxn21的非负整数解的个数为rrn1.推论1.3不定方程nrrxxxn21的正整数解的个数为nrr1.应用公式0)!(!!knknknkn，容易证明下面两个定理★定理1.16（1）0knknnkn（2）1111knknknkn（3）111knknknkn（4）111knknkknkn（5）01knknknnkn★定理1.17kmnkmknknkmmn多项式定理★定理1.18（多项式定理）设n是正整数，kxxx,,,21是任意k个实变数，则是非负整数),,2,1(2121212121!!!!)(kinnnnnnknnknkikkxxxnnnnxxx.推论1.4（二项式定理）设n是正整数，x和y是任意实数，则knknknyxknyx0)(.推论1.5设n是正整数，x是任一实数，则knknxknx0)1(.推论1.6设n是正整数，则（1）)0(20nknnnk.（2）)1(0)1(0nknnkk.1.5二项式反演公式二项式反演公式引理1.1设n，s是非负整数且sn，对于每个非负整数k)(nks，),,1,(,kssiaik是复数，则nsinikiknskksiikaa,,★定理1.18（二项式反演公式）设0nna和0nnb是两个数列，s是非负整数，如果对任意的不小于s的整数n，都有knsknbkna，则对任意的不小于s的整数n。都有knskknnaknb)1(.有限集的覆盖设A是n元集，以)(*AP表示A的全体非空子集所成之集，则12)(*nAP，)(*AP共有1212n个非空子集.☻定义1.13设A是n元集，)(*AP，如果FAF，则称是n元集A的一个覆盖.☻定义1.14如果是n元集A的一个覆盖且m，则称是n元集A的一个m-覆盖.多元二项式反演公式★定理1.20设rsss,,,21是r个给定的非负整数，又设对任意的r个非负整数),,2,1,(,,,21risnnnniir，),,,(),,,(2121rrnnngnnnf及都是实数，且),,,(),,,(211,,2,121riiririnksrkkkgknnnnfiii.则对任意r个非负整数),,2,1,(,,,21risnnnniir，有),,,()1(),,,(211,,2,121riiriknrinksrkkkfknnnngiiiii.