排列組合（組合學(xué)最基本的概念）

排列組合（組合學(xué)最基本的概念）

排列組合 （組合學(xué)最基本的概念） 次瀏覽 | 2022.04.16 16:15:03 更新 來源 ：互聯(lián)網(wǎng) 精選百科 本文由作者推薦 排列組合組合學(xué)最基本的概念

排列組合是組合學(xué)最基本的概念。所謂排列，就是指從給定個數(shù)的元素中取出指定個數(shù)的元素進(jìn)行排序。組合則是指從給定個數(shù)的元素中僅僅取出指定個數(shù)的元素，不考慮排序。排列組合的中心問題是研究給定要求的排列和組合可能出現(xiàn)的情況總數(shù)。排列組合與古典概率論關(guān)系密切,是進(jìn)一步學(xué)習(xí)的基礎(chǔ)。

中文名

排列組合

外文名

Permutation and Combination

應(yīng)用學(xué)科

數(shù)學(xué)

適用領(lǐng)域范圍

概率論

發(fā)展歷程

雖然數(shù)數(shù)始于結(jié)繩計數(shù)的遠(yuǎn)古時代，由于那時人的智力的發(fā)展尚處于低級階段，談不上有什么技巧。隨著人們對于數(shù)的了解和研究，在形成與數(shù)密切相關(guān)的數(shù)學(xué)分支的過程中，如數(shù)論、代數(shù)、函數(shù)論以至泛函的形成與發(fā)展，逐步地從數(shù)的多樣性發(fā)現(xiàn)數(shù)數(shù)的多樣性，產(chǎn)生了各種數(shù)數(shù)的技巧。

由此觀之，組合學(xué)與其他數(shù)學(xué)分支有著必然的密切聯(lián)系。它的一些研究內(nèi)容與方法來自各個分支也應(yīng)用于各個分支。當(dāng)然，組合學(xué)與其他數(shù)學(xué)分支一樣也有其獨(dú)特的研究問題與方法，它源于人們對于客觀世界中存在的數(shù)與形及其關(guān)系的發(fā)現(xiàn)和認(rèn)識。例如，中國古代的《易經(jīng)》中用十個天干和十二個地支以六十為周期來記載月和年，以及在洛書河圖中關(guān)于幻方的記載，是人們至今所了解的最早發(fā)現(xiàn)的組合問題甚或是架構(gòu)語境學(xué)。

歐拉基本簡介

排列分類：選排列和全排列，可重復(fù)排列，不盡相異元素的全排列，環(huán)狀排列

組合分類：通常意義的組合，可重復(fù)排列

公式

排列的定義及其計算公式：從n個不同元素中，任取m(m≤n,m與n均為自然數(shù),下同）個元素按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的一個排列；從n個不同元素中取出m(m≤n）個元素的所有排列的個數(shù)，叫做從n個不同元素中取出m個元素的排列數(shù)，用符號A(n,m）表示。A(n,m)=n(n-1）（n-2）……（n-m+1）=n!/(n-m)!此外規(guī)定0!=1

組合的定義及其計算公式：從n個不同元素中，任取m(m≤n）個元素并成一組，叫做從n個不同元素中取出m個元素的一個組合；從n個不同元素中取出m(m≤n）個元素的所有組合的個數(shù)，叫做從n個不同元素中取出m個元素的組合數(shù)。用符號C(n,m)表示。C(n,m)=A(n,m）∧2/m!=A(n,m)/m！；C(n,m)=C(n,n-m）。（其中n≥m)

其他排列與組合公式從n個元素中取出m個元素的循環(huán)排列數(shù)=A(n,m)/m=n!/m(n-m)!.n個元素被分成k類，每類的個數(shù)分別是n1,n2,...nk這n個元素的全排列數(shù)為n!/(n1！×n2！×...×nk!).k類元素，每類的個數(shù)無限，從中取出m個元素的組合數(shù)為C(m+k-1,m）。

符號

C-Combination組合數(shù)

A-Arrangement排列數(shù)（在舊教材為P-Permutation）

N-元素的總個數(shù)

M-參與選擇的元素個數(shù)

！-階乘

基本計數(shù)原理

⑴加法原理和分類計數(shù)法

⒈加法原理：做一件事，完成它可以有n類辦法，在第一類辦法中有m1種不同的方法，在第二類辦法中有m2種不同的方法，……，在第n類辦法中有mn種不同的方法，那么完成這件事共有N=m1+m2+m3+…+mn種不同方法。

⒉第一類辦法的方法屬于集合A1，第二類辦法的方法屬于集合A2，……，第n類辦法的方法屬于集合An，那么完成這件事的方法屬于集合A1UA2U…UAn。

⒊分類的要求：每一類中的每一種方法都可以獨(dú)立地完成此任務(wù)；兩類不同辦法中的具體方法，互不相同（即分類不重）；完成此任務(wù)的任何一種方法，都屬于某一類（即分類不漏）。

⑵乘法原理和分步計數(shù)法

⒈乘法原理：做一件事，完成它需要分成n個步驟，做第一步有m1種不同的方法，做第二步有m2種不同的方法，……，做第n步有mn種不同的方法，那么完成這件事共有N=m1×m2×m3×…×mn種不同的方法。

⒉合理分步的要求

任何一步的一種方法都不能完成此任務(wù)，必須且只須連續(xù)完成這n步才能完成此任務(wù)；各步計數(shù)相互獨(dú)立；只要有一步中所采取的方法不同，則對應(yīng)的完成此事的方法也不同。

二項式定理

(a+b)^n=Σ（0->n)C(in)a^(n-i)b^i

通項公式：a_(i+1）=C(in)a^(n-i)b^i

二項式系數(shù)：C(in)

楊輝三角：右圖。兩端是1，除1外的每個數(shù)是肩上兩數(shù)之和。

系數(shù)性質(zhì)：⑴和首末兩端等距離的系數(shù)相等。

⑵當(dāng)冪指數(shù)是奇數(shù)時，中間兩項最大且相等。

⑶當(dāng)冪指數(shù)是偶數(shù)時，中間一項最大。

⑷奇數(shù)項和偶數(shù)項總和相同，都是2^(n-1）。

⑸所有系數(shù)總和是2^n。

著名問題

計算一些物品在特定條件下分組的方法數(shù)目。這些是關(guān)于排列、組合和整數(shù)分拆的。

地圖著色問題：對世界地圖著色，每一個國家使用一種顏色。如果要求相鄰國家的顏色相異，是否總共只需四種顏色？這是圖論的問題。

船夫過河問題：船夫要把一匹狼、一只羊和一棵白菜運(yùn)過河。只要船夫不在場，羊就會吃白菜、狼就會吃羊。船夫的船每次只能運(yùn)送一種東西。怎樣把所有東西都運(yùn)過河？這是線性規(guī)劃的問題。

中國郵差問題：由中國組合數(shù)學(xué)家管梅谷教授提出。郵遞員要穿過城市的每一條路至少一次，怎樣行走走過的路程最短？這不是一個NP完全問題，存在多項式復(fù)雜度算法：先求出度為奇數(shù)的點，用匹配算法算出這些點間的連接方式，然后再用歐拉路徑算法求解。這也是圖論的問題。

任務(wù)分配問題（也稱婚配問題）：有一些員工要完成一些任務(wù)。各個員工完成不同任務(wù)所花費(fèi)的時間都不同。每個員工只分配一項任務(wù)。每項任務(wù)只被分配給一個員工。怎樣分配員工與任務(wù)以使所花費(fèi)的時間最少？這是線性規(guī)劃的問題。

如何構(gòu)作幻方。

大樂透

概述排列組合公式定義

公式P是指排列，從N個元素取R個進(jìn)行排列(即排序)。

公式C是指組合，從N個元素取R個，不進(jìn)行排列（即不排序）。

排列：從N個不同元素中，任取M（M<=N）個元素，按照一定的順序排成一列，叫做從N個不同元素中取出M個元素的一個排列。

排列數(shù)：從N個不同元素中取出M（M<=N）個元素的所有排列的個數(shù)，叫做從N個不同元素中取出M個元素的排列數(shù)。記作：Pmn

排列數(shù)公式：Pmn=n(n-1)(n-2)...(n-m1)

全排列：N個不同元素全部取出的一個排列，叫做N個不同元素的一個全排列。

自然數(shù)1到N的連乘積，叫做N的階乘。記作：n!（0!=1）

全排列公式：PNN=n!

排列數(shù)公式還可寫成：Pmn=n!/(n-m)!

加法原理：做一件事，完成它可以有N類加法，在第一類辦法中有M1種不同的方法，在第二類辦法中有M2種不同的方法，...，在第N類辦法中有MN種不同的方法。那么完成這件事共有N=M1M2...MN種不同的方法。

乘法原理：做一件事，完成它需要分成N個步驟，做第一步有M1種不同的方法，做第二步有M2種不同的方法，...，做第N步有MN種不同的方法，那么完成這件事共有N=M1×M2×...×MN種不同的方法。

C-組合數(shù)

P-排列數(shù)

N-元素的總個數(shù)

R參與選擇的元素個數(shù)

！-階乘，如5！=5*4*3*2*1=120

組合：從N個不同元素中，任取M（M<=N）個元素并成一組，叫做從N個不同元素中取出M個元素的一個組合。

排列與元素的順序有關(guān)，組合與元素的順序無關(guān)。

組合數(shù)：從N個不同元素中取出M（M<=N）個元素的所有組合的個數(shù)，叫做從N個不同元素中取出M個元素的組合數(shù)。記作：Cmn

組合數(shù)公式：Cmn=Pmn/Pmm=n(n-1)(n-2)...(n-m1)/m!=n!/m!/(n-m)!

組合性質(zhì)1：Cmn=Cn-mn(C0n=1)

組合性質(zhì)2：Cmn1=CmnCm-1n

C-Combination組合

P-Permutation排列

排列的變化

排列的變化，排列數(shù)“P”現(xiàn)在已成了“A”，P是舊用法，現(xiàn)在教材上多用A，即Arrangement也就是說，“P33”已成了“A33”.高考、中考也是這樣，希望大家改過來！

小學(xué)排列組合公式

1、“Cmn”=“Cm（m-n）”

2、“Cm0（m大于0）”=1

3、“Cm0”“Cm1”......“Cm10”=2的m次方

舉例分析

排列、組合的概念具有廣泛的實際意義，解決排列、組合問題，關(guān)鍵要搞清楚是否與元素的順序有關(guān)。復(fù)雜的排列、組合問題往往是對元素或位置進(jìn)行限制，因此掌握一些基本的排列、組合問題的類型與解法對學(xué)好這部分知識很重要。

排列與組合的區(qū)別與聯(lián)系：與順序有關(guān)的為排列問題，與順序無關(guān)的為組合問題。

解決排列組合問題要講究策略，首先要認(rèn)真審題，弄清楚是排列(有序)還是組合(無序)，還是排列與組合混合問題。其次，要抓住問題的本質(zhì)特征，準(zhǔn)確合理地利用兩個基本原則進(jìn)行“分類與分步”。

加法原理的特征是分類解決問題，分類必須滿足兩個條件：①類與類必須互斥(不相容)，②總類必須完備(不遺漏)；乘法原理的特征是分步解決問題，分步必須做到步與步互相獨(dú)立，互不干擾并確保連續(xù)性。分類與分步是解決排列組合問題的最基本的思想策略，在實際操作中往往是“步”與“類”交叉，有機(jī)結(jié)合，可以是類中有步，也可以是步中有類。

參考資料