排列組合公式

關(guān)于排列組合公式第一頁，共一百二十二頁，2022年，8月28日排列與組合從五個候選人中選出兩個代表把5本不同的書安排在書架上從五個候選人中選出兩個代表時，有10種可能的結(jié)果。把5本不同的書安排在書架上有120種方法選出-組合；安排-排列第二頁，共一百二十二頁，2022年，8月28日一、排列組合公式排列問題：從某個集合中有序地選取若干個元素的問題組合問題：從某個集合中無序地選取若干個元素的問題注意：可以重復(fù)不能重復(fù)第三頁，共一百二十二頁，2022年，8月28日排列無重排列可重排列從{1,2,…,9}中選取數(shù)字構(gòu)成四位數(shù)，使得每位數(shù)字都不同，有多少個？從{1,2,…,9}中選取數(shù)字構(gòu)成四位數(shù)，使得不同數(shù)位上的數(shù)字可以相同，有多少個？第四頁，共一百二十二頁，2022年，8月28日1、無重排列n個元素的r-無重排列數(shù)：排列的長度r計算（一般情形）：乘法原理r=n時,n個元素的全排列r=0時r>n時第五頁，共一百二十二頁，2022年，8月28日2、可重排列n個元素的r-可重排列數(shù)計算（乘法原理）第六頁，共一百二十二頁，2022年，8月28日例題在1和10,000,000,000之間的一百億個數(shù)中，有多少個數(shù)含有數(shù)碼1？又有多少個數(shù)不含數(shù)碼1？不含1:910含1:1010-910+1第七頁，共一百二十二頁，2022年，8月28日例題一個二元序列是由一些0和1所組成的序列。n碼二元序列指該序列中數(shù)碼的個數(shù)為n。試問，含有偶數(shù)個0的n碼二元序列的個數(shù)是多少？2n-1考慮n碼四元序列，即以0,1,2和3為其數(shù)碼的序列。則含0和1的總個數(shù)為偶數(shù)的序列有多少個？4n/2第八頁，共一百二十二頁，2022年，8月28日例題求n碼四元序列中含有偶數(shù)個0的個數(shù)？第九頁，共一百二十二頁，2022年，8月28日放球問題設(shè)n≥r，把r個不同的球放入n個不同的盒子，這里每一盒最多只能裝一物，允許空盒。放球的方法數(shù)為多少？第一個球有n種選法，第二個球有n-1種，等等，乘法原理P(n,r)第十頁，共一百二十二頁，2022年，8月28日放球問題把r個不同的球放入n個不同的盒子，一個盒中可以放多個球，也允許空盒。放球的方法數(shù)為多少？第一個球有n種選法，第二個球有n種，等等，乘法原理nr這里n和r的大小沒有限制第十一頁，共一百二十二頁，2022年，8月28日放球問題把r個不同的球放入n個不同的盒子，一個盒中可以放多個球，也允許空盒。考慮每個盒子中球的次序。放球的方法數(shù)為多少？把這樣一個方法設(shè)想為r個不同的球和n-1個相同的盒間板的一個有序安排。C(r+n-1,n-1)=C(r+n-1,r)=F(n,r)另解：有n種方法放第一個球，第一個球放入一個盒后，可以把這個球當(dāng)成是一個添加的隔板，它把該盒分成兩個盒，因此放第二個球有n+1種方法。等等第十二頁，共一百二十二頁，2022年，8月28日放球問題：例題今欲在五根旗桿上懸掛七面不同的旗子，全部旗都得展示出來，但并非所有的旗桿都得使用，問有多少種安排的方法？七部汽車通過五間收費亭的方式數(shù)？第十三頁，共一百二十二頁，2022年，8月28日組合無重組合可重組合從{a,b,c}中選取2個不同元素，選法數(shù)是多少？從{a,b,c}中選取5個元素，元素可以相同，選法數(shù)是多少？第十四頁，共一百二十二頁，2022年，8月28日3、無重組合（Combination）n個元素的r-無重組合數(shù)無重組合數(shù)與無重排列數(shù)的關(guān)系計算r=0時r=n時r>n時第十五頁，共一百二十二頁，2022年，8月28日組合數(shù)的推廣第十六頁，共一百二十二頁，2022年，8月28日幾個記號下階乘函數(shù)上階乘函數(shù)第十七頁，共一百二十二頁，2022年，8月28日計算第十八頁，共一百二十二頁，2022年，8月28日例題如果一個凸十邊形無三條對角線在這個十邊形的內(nèi)部交于一點，問這些對角線被它們的交點分成多少條線段？第十九頁，共一百二十二頁，2022年，8月28日多邊形第二十頁，共一百二十二頁，2022年，8月28日例題對角線的條數(shù)為C(10,2)-10=45-10=35任選兩條對角線，可能相交在多邊形內(nèi)部，可能交點為多邊形的頂點，可能無交點（交點在多邊形外）任選四個頂點，對應(yīng)一個交點，每個對角線分成兩段每個對角線是一段35+C(10,4)×2=455第二十一頁，共一百二十二頁，2022年，8月28日例題C(5,2)-5+C(5,4)×2=15C(10,2)-10+C(10,4)×2=455C(4,2)-4+C(4,4)×2=4第二十二頁，共一百二十二頁，2022年，8月28日4、可重組合n個元素的r-可重組合例子計算一一對應(yīng)的思想第二十三頁，共一百二十二頁，2022年，8月28日推論方程x1+x2+…+xn=r的非負(fù)整數(shù)解的個數(shù)。n≤r時，此方程的正整數(shù)解的個數(shù)n元集合的r-可重組合數(shù)，要求每個元素至少出現(xiàn)一次。正整數(shù)r的n-長有序分拆的個數(shù)求x1+x2+x3+x4=20的整數(shù)解的數(shù)目，其中x1≥

3,x2≥1,x3≥0,x4≥5。第二十四頁，共一百二十二頁，2022年，8月28日例題從為數(shù)眾多的一分幣、二分幣、一角幣和二角幣中，可以有多少種方法選出六枚來？F(4,6)=C(4+6-1,6)=C(9,6)=84第二十五頁，共一百二十二頁，2022年，8月28日例題某糕點廠將8種糕點裝盒，若每盒有一打糕點，求市場上能買到多少種該廠出品的盒裝糕點？某糕點廠將8種糕點裝盒，若每盒有一打糕點，且要求每種糕點至少放一塊。求市場上能買到多少種該廠出品的盒裝糕點？第二十六頁，共一百二十二頁，2022年，8月28日例題搖三個不同的骰子的時候，可能的結(jié)果的個數(shù)是多少？63=216。如果這三個骰子是沒有區(qū)別的，則可能結(jié)果的個數(shù)是多少？從1,2,3,4,5,6這六個數(shù)中允許重復(fù)地選出三個數(shù)。F(6,3)=C(6+3-1,3)=56將r個骰子擲一次，總共可以擲出多少種不同結(jié)果？F(6,r)=C(6+r-1,r)=C(r+5,r)=C(r+5,5)第二十七頁，共一百二十二頁，2022年，8月28日有約束條件的排列：引例用兩面紅旗、三面黃旗依次懸掛在一根旗桿上，問可以組成多少種不同的標(biāo)志？第二十八頁，共一百二十二頁，2022年，8月28日5、有約束條件的排列設(shè)有k個元素a1，a2，…，ak，由它們組成一個n-長的排列，其中對1≤i≤k，ai出現(xiàn)的次數(shù)為ni，n1+n2+…

+nk=n，求排列的總數(shù)。求解方法1求解方法2第二十九頁，共一百二十二頁，2022年，8月28日例題五條短劃和八個點可以安排成多少種不同的方式？如果只用這十三個短劃和點中的七個，則有多少種不同的方式？第三十頁，共一百二十二頁，2022年，8月28日例題證明對任意正整數(shù)k,(k!)!能被(k!)(k-1)!整除。提示：k!個物體，其中k個物體屬于第一類，k個物體屬于第二類，…，k個物體屬于第(k-1)!類。第三十一頁，共一百二十二頁，2022年，8月28日推論多項式(x1+x2+…+xr)n的展開式中有

項，其中項的系數(shù)為

。第三十二頁，共一百二十二頁，2022年，8月28日例題數(shù)1400有多少個正因數(shù)？1400=23×

52×

7(3+1)(2+1)(1+1)=24第三十三頁，共一百二十二頁，2022年，8月28日放球問題設(shè)n≥r，把r個相同的球放入n個不同的盒子使得每盒至多裝一個球，方法數(shù)？選盒子即可C(n,r)第三十四頁，共一百二十二頁，2022年，8月28日放球問題把r個相同的球放入n個不同的盒子，每盒可以裝任意多個球，方法數(shù)？放這r個球，等價于從n個盒中選出r個來裝這r個球而允許諸盒重復(fù)選取。F(n,r)=C(n+r-1,r)另解：把分配這r個球入n個盒子設(shè)想為這r個球和n-1個隔板的一個排列。球是相同的，隔板也是相同的。C(n+r-1,r)第三十五頁，共一百二十二頁，2022年，8月28日放球問題設(shè)r≥n，把r個相同的球放入n個不同的盒子中，盒子中可以放入任意多個球，但不允許空盒，方法數(shù)？現(xiàn)在每個盒中放入一個球，再放剩下的r-n個球C((r-n)+n-1,r-n)=C(r-1,r-n)=C(r-1,n-1)第三十六頁，共一百二十二頁，2022年，8月28日放球問題設(shè)r≥n，把r個相同的球放入n個不同的盒子中，要求每一盒至少包含q個球，方法數(shù)？現(xiàn)在每個盒中放入q個球，再放剩下的r-qn個球C((r-qn)+n-1,r-qn)=C(n-nq+r-1,r-nq)=C(n-nq+r-1,n-1)第三十七頁，共一百二十二頁，2022年，8月28日放球問題：例題今有五封不同的信要經(jīng)由一個訊道傳送。又有總共15個空白要插在這些信之間而使得每兩封信之間至少有三個空白。有多少種方法安排這些信和空白？信的安排5！對一種信的安排，有4個信件位置，安排15個空白，要求每個信件位置至少有三個空白。5！C(4-4×3+15-1,4-1)=5!×C(6,3)第三十八頁，共一百二十二頁，2022年，8月28日放球問題有n個球，其中第一種顏色n1個，第二種顏色n2個，…，第k種顏色nk個。將這n個球放入n個不同的盒中，每一個盒裝一個球。問分配方案數(shù)？等價于這n個球的排列數(shù)。另解：選盒子裝每種顏色的球。第三十九頁，共一百二十二頁，2022年，8月28日放球問題有r個球，其中第一種顏色n1個，第二種顏色n2個，…，第k種顏色nk個。將這r個球放入n個不同的盒中，每一個盒裝一個球（r≤n）。問分配方案數(shù)？方法一：先選盒子，再分配球。方法二：針對每種顏色的球選盒子。第四十頁，共一百二十二頁，2022年，8月28日多重集合通常的“集合”具有無重性。在多重集中，同一個元素可以出現(xiàn)多次。{1,2,3}是一個集合，而{1,1,1,2,2,3}不是一個集合，而是一個多重集，簡記為{3·1,2·2,1·3}。計算多重集的勢時，出現(xiàn)多次的元素則需要按出現(xiàn)的次數(shù)計算。上面多重集的勢為6?？芍亟M合與可重排列可以看作是多重集的組合與排列問題。第四十一頁，共一百二十二頁，2022年，8月28日可重排列與可重組合n個元素{a1,a2,…,an}的r-無重組合(排列)可以看做多重集{1·a1,1·a2,…,1·an}的r-組合(排列)。n個元素{a1,a2,…,an}的r-可重組合(排列)可以看做多重集{∞·a1,∞·a2,…,∞·an}的r-組合(排列)。有限制的排列問題可以看做多重集{n1·a1,n2·a2,…,nk·ak}的全排列。第四十二頁，共一百二十二頁，2022年，8月28日分組與分堆固定分組：無序分組：分堆不定分組固定分組與分堆的區(qū)別是講不講組間的次序，只在各組元素個數(shù)相等時有區(qū)別固定分組與不定分組的區(qū)別是每個組的元素個數(shù)是不是確定，只在各組元素個數(shù)不等時才有區(qū)別。第四十三頁，共一百二十二頁，2022年，8月28日區(qū)分將12本書平均分給A,B,C,D四個學(xué)生，每人三本，有多少種分法？將12本書平均分成四堆有多少種分法？將12本書平均分給A,B,C,D四個學(xué)生，使得每人各得三本，有多少種分法？第四十四頁，共一百二十二頁，2022年，8月28日區(qū)分將12本書分給四個學(xué)生，使得A,B各得四本，C,D各得2本，有多少種分法？將12本書分成四堆，有兩堆各4本，另外兩堆各2本，有多少種分法？將12本書分給A,B,C,D四個學(xué)生，使得有兩個學(xué)生各得4本，有兩個學(xué)生各得2本，有多少種分法？第四十五頁，共一百二十二頁，2022年，8月28日區(qū)分將12本書分給四個學(xué)生，A得5本，B得4本，C得2本，D得1本，有多少種分法？將12本書分成四堆，其本數(shù)分別為5,4,2,1，有多少種分法？將12本書分給A,B,C,D四個學(xué)生，使得有1人得5本，有一人得4本，有1人得兩本，有1人得1本，有多少種分法？第四十六頁，共一百二十二頁，2022年，8月28日限距組合：引例書架上有1-24共24卷百科全書，從其中選5卷使得任何兩卷都不相繼，這樣的選法有多少種？第四十七頁，共一百二十二頁，2022年，8月28日6、限距組合設(shè)A={1,2,…,n}，它的任一r-無重組合均可以依自然順序排出a1,a2,…,ar，其中a1<a2<…<ar。設(shè)k是非負(fù)整數(shù)，用f(k,n,r)表示A的一切滿足條件ai+1-ai≥k+1(1≤i≤r-1)的r-無重組合數(shù)，求f(k,n,r)。求解思想：一一對應(yīng)k=0時第四十八頁，共一百二十二頁，2022年，8月28日例題書架上有1-24共24卷百科全書，從其中選5卷使得任何兩卷都不相繼，這樣的選法有多少種？第四十九頁，共一百二十二頁，2022年，8月28日7、圓排列n個元素的r-無重圓排列數(shù)圓排列與線排列的區(qū)別計算第五十頁，共一百二十二頁，2022年，8月28日例題例1把20個不同的釘子釘在鼓表面一周，訂釘子的方式有

種。例2把20個不同的珍珠串成項鏈，串項鏈的方式有

種。項鏈問題第五十一頁，共一百二十二頁，2022年，8月28日例從1到300間取出3個不同的數(shù)，使它們的和被3整除，有多少種取法？提示：將1到300這300個整數(shù)按照除以3的余數(shù)分成3組，考慮選出的3個數(shù)屬于哪些組。第五十二頁，共一百二十二頁，2022年，8月28日例下圖中有多少個矩形？第五十三頁，共一百二十二頁，2022年，8月28日映射的個數(shù)n元集X到m元集A的映射的個數(shù)將X看作物件的集合，A看作盒子的集合。則一個映射表示把物件放入盒子的一種安排。要求(1)每個物體都要放入某個盒子；(2)一個物體不得放入兩個盒子；(3)允許多個物體放入同一盒子；(4)可以剩有空盒子。若將X看作有標(biāo)號的位置的集合，A看作排在這些位置的字母的組合，則一個映射對應(yīng)一個長為n的字。則(1)字長必須為n；(2)一個位置只能放一個字母；(3)多個位置可以重復(fù)出現(xiàn)同一字母；(4)有些字母有可能不出現(xiàn)。第五十四頁，共一百二十二頁，2022年，8月28日例題n元集合X到m元集合A的映射的個數(shù)？將n個物體放在m個的盒子中的不同放法？n元集合X到m元集合A的單射的個數(shù)？把n個物體放入m個盒子，每個盒子至多放一個物體的安排有多少種？3個物體分放到4個不同的盒子中，要求每個盒子至多放一個物體的放法數(shù)？第五十五頁，共一百二十二頁，2022年，8月28日映射設(shè)映射f：{1,2,…,n}→{1,2,…,m}(n≤m)(1)若f是嚴(yán)格遞增的，則不同的f有多少個？(2)若f是不減的，則不同的f有多少個？第五十六頁，共一百二十二頁，2022年，8月28日例題1、從A={a,b,c}中任取兩個不同的字母構(gòu)成的字共有多少個？2、m元集合的n元子集的個數(shù)？3、平面上任三點都不共線的25個點，可形成多少條直線？可形成多少個三角形？第五十七頁，共一百二十二頁，2022年，8月28日例題用26個英文字母能構(gòu)成多少個含有3個、4個或5個元音的長為8位的單詞？（其中，一個字母出現(xiàn)在單詞中的次數(shù)不限）第五十八頁，共一百二十二頁，2022年，8月28日例題從一副52張撲克牌中任取13張得一手牌，在每一手牌中不考慮這13張牌的次序，則總共有多少手不同的牌？把一副52張撲克牌分給4個人，每人得13張，則總共有多少種不同的牌局？第五十九頁，共一百二十二頁，2022年，8月28日例題用4個a，4個b，2個c和2個d這12個字母能組成多少個具有12個字母的字？用字母a，b，c組成5個字母的字，每個字中a至多出現(xiàn)2次，b至多出現(xiàn)1次，c至多出現(xiàn)3次。這種字的個數(shù)是多少？第六十頁，共一百二十二頁，2022年，8月28日例題單詞mississippi中字母的排列數(shù)為？求多重集{3·a,2·b,4·c}的8排列的個數(shù)？第六十一頁，共一百二十二頁，2022年，8月28日例題求26個英文字母的全排列中，任意兩個元音字母都不相鄰的方案數(shù)？第六十二頁，共一百二十二頁，2022年，8月28日例題Banach火柴盒問題：某數(shù)學(xué)家隨身攜帶A,B兩盒火柴，要用火柴時就隨意從其中一盒中取出一根。假定開始兩個火柴盒各放有n根火柴，問在某一次當(dāng)數(shù)學(xué)家發(fā)現(xiàn)拿出的那一個火柴盒變空時，另一盒中尚剩p(p<n)根火柴的概率是多少？第六十三頁，共一百二十二頁，2022年，8月28日例題10個人排成一排，其中有2個人不愿彼此挨著，求所有不同的排列的數(shù)目。10！-2×9！或8！A(9,2)=290304010個人圍一圓桌入座，其中有2個人不愿彼此挨著就座，求所有不同的圓排列的數(shù)目。9!-2×8!或7！A(8,2)=282240第六十四頁，共一百二十二頁，2022年，8月28日例題安排10個男生和5個女生排成一排，使任意2個女生都不相鄰的排法有多少種？A(10,10)A(11,5)安排10個男生和5個女生圍成圓圈入座，使任意2個女生都不相鄰的坐法有多少種？第六十五頁，共一百二十二頁，2022年，8月28日例從給定的6種不同的顏色中選不同的顏色將一個正方體的六個面染色，要求每個面染一種顏色，具有相同棱的面染成不同的顏色，則不同的染色方案有多少種？分析：一種顏色？兩種顏色？三種顏色？相對的面染成相同的顏色,只有一種方式C(6,3)第六十六頁，共一百二十二頁，2022年，8月28日四種顏色：五種顏色：六種顏色：C(6,4)C(4,2)C(6,5)C(5,1)3！/2C(6,6)C(5,1)3！第六十七頁，共一百二十二頁，2022年，8月28日例試求由1,3,5,7組成的數(shù)字不重復(fù)出現(xiàn)的整數(shù)的總和。分析：一位數(shù)1，3，5，7兩位數(shù)個(十)位數(shù)為1的兩位數(shù)的個數(shù)三位數(shù)個(十、百)位數(shù)為1的三位數(shù)的個數(shù)四位數(shù)個(十、百、千)位數(shù)為1的四位數(shù)的個數(shù)第六十八頁，共一百二十二頁，2022年，8月28日例假定把全部的5碼數(shù)印刷在紙條上，而一張紙條上印一個數(shù)。所謂5碼數(shù)是由0,1,2,…,9這十個數(shù)字中的5個數(shù)字組成的數(shù)，開頭的一個或者幾個可以為0，例如00102,00000都是5碼數(shù)，顯然有100000個這樣的5碼數(shù)。然而由于數(shù)字0,1,6,8,9被倒過來就成了0,1,9,8,6。而一張紙條可以從上下兩個方向正看和倒看，所以有些5碼數(shù)可以共用一張紙條，如89166與99168。于是我們的問題是要用多少個不同的紙條才能做出這些5碼數(shù)？第六十九頁，共一百二十二頁，2022年，8月28日01234567890101倒過來

886996第七十頁，共一百二十二頁，2022年，8月28日1357813578倒過來

89166681898916668189不是5碼數(shù)仍是5碼數(shù)仍是5碼數(shù)但不是自己而且是自己第七十一頁，共一百二十二頁，2022年，8月28日5碼數(shù)共105個倒過來仍是5碼數(shù)的有55個倒過來不再是5碼數(shù)的有105—55個一個數(shù)一張紙條倒過來是自己的有3x52個倒過來不是自己的有55—3x52個一個數(shù)一張紙條兩個數(shù)共用一張紙條第七十二頁，共一百二十二頁，2022年，8月28日所以紙條的個數(shù)為(105—55)+3x52+(55—3x52)/2105—(55—3x52)/2=98475第七十三頁，共一百二十二頁，2022年，8月28日例甲、乙兩方各有7名隊員，按事先排好的順序出場參加圍棋擂臺賽。雙方先由1號參加比賽，負(fù)者被淘汰，勝者再與對方2號隊員比賽，…，直到有一方全部被淘汰，另一方獲得勝利，形成一種比賽過程。那么所有可能出現(xiàn)的比賽過程的種數(shù)為多少？第七十四頁，共一百二十二頁，2022年，8月28日甲乙箭頭指向誰，表示誰負(fù)甲方贏：這是的一個7-可重組合第七十五頁，共一百二十二頁，2022年，8月28日甲乙第七十六頁，共一百二十二頁，2022年，8月28日甲乙第七十七頁，共一百二十二頁，2022年，8月28日甲乙第七十八頁，共一百二十二頁，2022年，8月28日例某車站有6個進(jìn)站口，今有9人進(jìn)站，有多少種不同的進(jìn)站方法？進(jìn)站口人2ABCDEF13456789任務(wù)：給每個人選擇進(jìn)站口，選擇進(jìn)站的次序？第七十九頁，共一百二十二頁，2022年，8月28日安排：ABCDEF16種方式1安排：27種方式222安排：38種方式3333安排：914種方式進(jìn)站方式種數(shù)為方法一：第八十頁，共一百二十二頁，2022年，8月28日123456取213456789的一個全排列，和5個213456789對應(yīng)的進(jìn)站方式為：913456872方法二：第八十一頁，共一百二十二頁，2022年，8月28日ABCDEF進(jìn)站方式為：913456872213456789對應(yīng)的排列為：第八十二頁，共一百二十二頁，2022年，8月28日進(jìn)站方式種數(shù)為213456789的排列5個或14個位置取5個放方框(不講順序)，剩下的放人(將順序)第八十三頁，共一百二十二頁，2022年，8月28日方法三：先選車站，ABCDEF的9-可重組合AAACCDEEF再排人，213456789的排列213456789對應(yīng)的進(jìn)站方式為：ABCDEF913456872第八十四頁，共一百二十二頁，2022年，8月28日對比例某車站有6個進(jìn)站口，今有9人進(jìn)站，有多少種不同的進(jìn)站方法？今欲在六根旗桿上懸掛九面不同的旗子，全部旗都得展示出來，但并非所有的旗桿都得使用，問有多少種安排的方法？第八十五頁，共一百二十二頁，2022年，8月28日例8個人兩兩配對分成4組有多少種方式？方法一給每個人配對方法二一對一對地選，注意會重復(fù)推廣：2n個人兩兩配對分成n組有多少種方式？第八十六頁，共一百二十二頁，2022年，8月28日非降路徑問題從點到達(dá)點的非降路徑第八十七頁，共一百二十二頁，2022年，8月28日非降路徑數(shù)由(0,0)到(m,n)的非降路徑數(shù)為

。由(a,b)到(m,n)的非降路徑數(shù)為

。由(0,0)到(m,n),再到(a,b)的非降路徑數(shù)

。第八十八頁，共一百二十二頁，2022年，8月28日例題從點(0,0)到達(dá)點(m,n)，其中m<n，要求中間所經(jīng)過的路程上的點(a,b)都滿足a<b。問有多少種不同的路徑？第八十九頁，共一百二十二頁，2022年，8月28日分析從(0,0)到(m,n)

的非降路徑

過對角線必過對角線一一對應(yīng)：反射(0,0)→(0,1)→(m,n)(0,0)→(1,0)→(m,n)不過對角線第九十頁，共一百二十二頁，2022年，8月28日反射：從上向下看，找路徑與對角線交點的第一個點，關(guān)于對角線反射左下邊路徑，與右上的路徑組合成一條路徑。第九十一頁，共一百二十二頁，2022年，8月28日例題求從點(0,0)到達(dá)點(n,n)且不與直線y=x相交的非降路徑數(shù)？分析：上一例題的特殊情況第九十二頁，共一百二十二頁，2022年，8月28日例題一場音樂會的票價為50元/張，排隊買票的顧客中有n位持有50元的鈔票，m位持有100元的鈔票，售票處沒有準(zhǔn)備50元的零錢。試問有多少種排隊的方法，使購票能順利進(jìn)行，不出現(xiàn)找不開錢的狀況，假定每位顧客限買一張，每位顧客僅買票一張，而且n≥m。第九十三頁，共一百二十二頁，2022年，8月28日例題用(m+n)維0,1-行向量(a1,a2,…,am+n)表示一種購票排隊狀態(tài)，其中ai=1表示第i位持50元的鈔票，ai=0表示第i人持100元的鈔票。這樣的行向量有m個0，n個1，所以這樣的行向量共有C(m+n,m)個，每個行向量可以對應(yīng)從點(0,0)到點(m,n)的非降路徑。當(dāng)ai=1時，對應(yīng)路徑中的第i步沿y軸向上走一格，當(dāng)ai=0時，對應(yīng)路徑中的第i步沿x軸向右走一格。為了使購票順利進(jìn)行，每個路徑中的點(a,b)應(yīng)滿足a≤b。也就是每個路徑在直線y=x的上方且不穿過直線y=x，可以有交點。第九十四頁，共一百二十二頁，2022年，8月28日由于n≥m，也就是在直線y=x-1上方的所有路徑。從(0,0)到(m,n)的在直線y=x-1上方的非降路徑從(0,1)到(m,n+1)的在直線y=x上方的非降路徑從(0,0)到(m,n+1)的在直線y=x上方的非降路徑第n個Catalan數(shù)第九十五頁，共一百二十二頁，2022年，8月28日Catalan數(shù)第n個Catalan數(shù)第九十六頁，共一百二十二頁，2022年，8月28日Catalan數(shù)的組合學(xué)意義第九十七頁，共一百二十二頁，2022年，8月28日例題n個+1和n個-1所組成的序列中所有其前k項(k=1,2,…,2n)之和不小于0的序列的數(shù)目是多少？滿足條件的序列為好序列，不滿足條件的為壞序列。好序列數(shù)=序列總數(shù)-壞序列數(shù)。n個+1和n個-1所組成的壞序列與n+1個+1和n-1個-1所組成的序列一一對應(yīng)。第九十八頁，共一百二十二頁，2022年，8月28日例題對每個壞序列，總可以找到最小的正奇數(shù)，使得ak=-1且ak之前的+1和-1的個數(shù)相等。將這個壞序列中前k項的每一項取反號，其余部分保持不變。所得序列為n+1個+1和n-1個-1組成的序列。-1,-1,1,1,-1,1變?yōu)?,-1,1,1,-1,1反之，對任一由n+1個+1和n-1個-1組成的序列，從左到右掃描，當(dāng)+1的個數(shù)第一次比-1的個數(shù)多1時就把這些掃描到的項全部取反號，其余項不變，結(jié)果得到滿足要求的壞序列。1,-1,1,1,-1,1變?yōu)?1,-1,1,1,-1,1第九十九頁