排列(n>=r)

對(duì)有n個(gè)元素的集合S中的其中r個(gè)元素進(jìn)行排列(n >= r)可以用如下幾種方法來(lái)理解：

排列描述1

每次從n個(gè)元素中取r個(gè)元素出來(lái)，那么一共有C(n,r)種取法。每種取法中的r個(gè)元素按順序依次排列在r個(gè)位置上，這樣第一個(gè)位置一共有r種方法，而第二個(gè)位置有r-1個(gè)方法，第r個(gè)位置則只有1種方法了，因此一共有 r * (r-1) * (r-2) * ... * 2 * 1種方法，也就是有r!種方法。每種取法有r!種放置的方法，那么總共就有 C(n,r) * r!種排列方法，因此：

A(n,r) = C(n,r) * r!

排列描述2

把n個(gè)元素放入到r個(gè)位置里面，且每個(gè)位置只能放置1個(gè)。那么第一個(gè)位置一共有n種放法，第二個(gè)位置一共有n-1種放法，因此第r個(gè)位置一共有n-r+1種放法，這樣總共就有：n * (n-1) * (n-2) * ... * (n-r+1)種放法(或者說(shuō)第一個(gè)位置一共可以放n個(gè)元素中的任意一個(gè)，第二個(gè)位置則可以放入n-1個(gè)元素中的任意一個(gè)，依次類推第r個(gè)位置就可以放入n-r+1個(gè)元素中的任意一個(gè)，這樣排列完畢同時(shí)也只取了其中的r個(gè)元素)因此：

A(n,r) = n * (n-1)*(n-2) *...* (n-r+1)

排列描述3

如果對(duì)n個(gè)元素都進(jìn)行排列那么一共有n!種排列的方法。那么當(dāng)取r個(gè)元素進(jìn)行排列時(shí)，可以反過(guò)來(lái)假設(shè)將r個(gè)元素放入到n個(gè)位置中去，這時(shí)候必定有n-r個(gè)位置是空的，也就是n-r個(gè)位置只有1種取值。而在n!種排列中(n-r)個(gè)位置一共有(n-r)!種排列，因此去除這(n-r)!種重復(fù)的排列，只保留一種那就得到了n個(gè)元素的r排列的公式：

A(n,r) = n! / (n-r)!

這種描述還可以將n!的計(jì)算描述為先從n個(gè)元素里面取r個(gè)進(jìn)行排列，再將(n-r)進(jìn)行排列，一共有(n-r)!種方法，這樣二者相乘得到n!, 因此 A(n,r) * (n-r)! = n!

在實(shí)踐中排列的另外一個(gè)表述就是把n個(gè)元素放入r個(gè)位置(n >=r), 并且要求每個(gè)位置至只放一個(gè)元素的方法數(shù)量。同樣可以表述為將r個(gè)元素放入n個(gè)位置(n >= r),并且每個(gè)位置至多只放一個(gè)元素的方法數(shù)量。

排列(n<r)

前面考察的是將n個(gè)元素放入r的位置(n >=r)的情況，再來(lái)詳細(xì)的考察n<r的情況。因?yàn)檫@種放置會(huì)產(chǎn)生空的位置，因此不能用A(n,r)來(lái)計(jì)算(第一個(gè)位置有n+1種方法，這其中包括不放。而第二個(gè)位置的方法則要根據(jù)第一個(gè)位置的放入情況，假如第一個(gè)位置沒(méi)有放入，那么第二個(gè)位置就有n+1種放法；而假如第一個(gè)位置有放入則第二個(gè)位置有n種方法，因此這里不符合乘法規(guī)則)。這種情況下可以考慮增加(r-n)個(gè)相同的元素來(lái)填滿r個(gè)位置中，這樣就一共有r!種排列的方法了。又因?yàn)?r-n)個(gè)元素都是相同的元素，我們要去除重復(fù)的排列，一共有(r-n)!種。這樣我們就得出排列公式：

A(n,r) = r! / (r-n)! (r > n)

而當(dāng)r <= n 時(shí)則有：

A(n,r) = n!/(n-r)! (r<= n)

因此我們可以得出更加通用的排列公式：

A(n,r) = max(n,r)! / |n-r|!

上面可以看出當(dāng)r > n時(shí) 我們計(jì)算A(n,r)的排列，其實(shí)就是A(r,n)的排列計(jì)算公式。

重復(fù)排列

n個(gè)元素的r重復(fù)排列（n >=r)，也就是n個(gè)元素里面取r個(gè)元素，放置在r個(gè)位置上，每個(gè)位置至少放入一個(gè)，每個(gè)位置都可以重復(fù)放入相同的元素。這樣第一個(gè)位置就可以放入n個(gè)元素中的任意一個(gè)元素，因此一共有n種放法，而第二個(gè)位置也同樣可以放入n個(gè)元素中的任意一個(gè)元素，這樣第r個(gè)位置也可以放入n個(gè)元素中的任意一個(gè)元素。經(jīng)過(guò)r次放置后這n個(gè)元素里面最少是取了1個(gè)元素，而最多則是取了r個(gè)不同的元素。因此n的r重復(fù)排列的公式：

A(n,r) = n^r

在實(shí)踐中的重復(fù)排列，我們一般把位置作為指數(shù)，而把元素個(gè)數(shù)作為底數(shù)。

那n個(gè)元素的r位置重復(fù)排列在n<r時(shí)又是如何計(jì)算呢？如果每個(gè)位置至少放入1個(gè)元素的話那么，每個(gè)位置都有n種方法，因此重復(fù)排列的公式也是一樣的為： n^r。

對(duì)于重復(fù)排列來(lái)說(shuō)，當(dāng)考慮某個(gè)位置可以為空的情況時(shí)，那么就可以理解為我們多增加了一個(gè)元素，因此當(dāng)位置可以放置為空時(shí)的排列公式為 ：

A(n,r ) = (n+1)^r

這里依然可以用乘法公式的原因是每個(gè)位置的可放置的元素個(gè)數(shù)不依賴于前面的放置結(jié)果，每個(gè)位置都可以放置n+1種。因此對(duì)于重復(fù)排列來(lái)說(shuō)元素的個(gè)數(shù)和位置的數(shù)量無(wú)論哪個(gè)大結(jié)果的公式都是一樣的，都是 元素個(gè)數(shù)^位置個(gè)數(shù)

對(duì)于重復(fù)排列來(lái)說(shuō)這種指數(shù)關(guān)系，也可以表示為可以放回排列，比如n個(gè)元素，放入r個(gè)位置。一個(gè)位置可以放n個(gè)中的任意一個(gè)，一共有n種。而第二個(gè)位置則一樣可以放入n個(gè)中的任意一個(gè)一共也有n種。因此一共有 n ^ r 種。

舉例來(lái)說(shuō)把3個(gè)球放入4個(gè)位置，一共有多少種方法？ 這里面表面上看元素是3位置是4，但是因?yàn)榍虿豢芍貜?fù)因此不能用 3^4來(lái)描述。而且也不能用乘法因此第二個(gè)位置的放法要依賴于第一個(gè)位置，這里只能用不可重復(fù)的排列公式來(lái)進(jìn)行計(jì)算。

組合

組合其實(shí)就是從n個(gè)元素里面取出r個(gè)元素(n >=r)的方法數(shù)。

組合描述1

因?yàn)橹恍枰〕鰎個(gè)元素，因此不涉及到對(duì)r個(gè)元素進(jìn)行排列的情況。同樣組合可以看成是從一個(gè)有n個(gè)元素的集合S中取出含有r個(gè)元素的子集A的數(shù)量。我們知道從n個(gè)元素里面取r個(gè)元素進(jìn)行排列的方法一共有A(n,r)種排列，假設(shè)我們?nèi)〉搅艘粋€(gè)具有r個(gè)元素的集合A，那么在A中則一共有r!種排列方法，既然一個(gè)r元素的子集A的排列數(shù)量是r!, 而總的r個(gè)元素的排列數(shù)量是A(n,r). 那么也就是說(shuō)有A(n,r)/r!個(gè)子集，因此組合的公式：

C(n,r) = A(n,r) / r!

組合描述2

組合還可以從另外一個(gè)維度考察，就是假設(shè)有n個(gè)位置，我們要取出r個(gè)位置的取法，因?yàn)槊總€(gè)位置可以是n中的任意一個(gè)位置，但總共只有r個(gè)位置。你可以把總位置當(dāng)做元素的總數(shù)，r個(gè)位置則當(dāng)做r個(gè)不同的元素，因此組合還可以用在位置。也就是說(shuō)如果把r個(gè)相同的元素放入到n個(gè)位置里面的方法就是C(n,r)組合。而把r個(gè)不同元素放入到n個(gè)位置里面的方法就是P(n,r)排列。

這里再引申出重復(fù)排列的計(jì)算方法，假設(shè)有k種元素，每種元素的數(shù)量為ni (1 < i < k), 且 n1 + n2 + .. nk = n。 那么他的排列方式一共有幾種？ 我們知道一共有n個(gè)位置。要放置這k種元素。那么第一種元素a1 有n1個(gè)， 因?yàn)閍1的每個(gè)元素都相同因此不考慮順序問(wèn)題，這就和上面的組合的另外一個(gè)維度的考察是一樣的，因此一共有 C(n, n1)種方法。那么第二種類型a2則一共有n2個(gè)就有C(n-n1, n2)種方法，這里每一步驟都是獨(dú)立的因此可以用乘法最后的結(jié)果是：

C(n,n1) * C(n-n1, n2) * C(n-n1-...nk-1, nk) = n! / (n1! * n2! * ...nk!)

而當(dāng)只有2種元素a,b時(shí)那么就是 : C(n,n1) * (n-n1, n2) = (C,n1) = C(n,n2)*C(n-n2, n1) = C(n,n2) 。這個(gè)好理解就是假設(shè)只有2種元素時(shí)則每當(dāng)a類型的位置確定后， b類型就只有1種方法了。因此只要確定a的就OK了。

排列和組合的區(qū)別

當(dāng)把r個(gè)相同的元素放入到n個(gè)位置，每個(gè)位置至多只有一個(gè)的方法就是組合C(n,r); 而把r個(gè)不同的元素放入到n個(gè)位置，每個(gè)位置至多只有一個(gè)時(shí)的方法則是排列A(n,r)

而當(dāng)把n個(gè)不相同的元素放入r個(gè)位置， 每個(gè)位置只放置1個(gè)的方法就是A(n,r); 而把n個(gè)相同的元素放入r個(gè)位置，每個(gè)位置只放入1個(gè)的方法就是1了。 這里的原因是組合時(shí)因?yàn)槎际窍嗤亩貍€(gè)數(shù)小于位置時(shí)因?yàn)橛锌瘴凰蟹椒ㄓ卸喾N，而元素個(gè)數(shù)大于位置時(shí)因?yàn)闆](méi)有空位了所以只有一種。從而可以引申出的一個(gè)概念就是組合里面的放置方法其實(shí)就是空位數(shù)量的放置方法，因此有： C(n,r) = C(n, n-r)成立。

排列組合在實(shí)踐中的區(qū)別是，排列是把x個(gè)元素放入y個(gè)位置的計(jì)數(shù)，而組合則是x個(gè)元素中取任意y個(gè)元素的計(jì)數(shù)，因?yàn)槲恢檬怯许樞虻?，而取出的?shù)量則不需要考慮順序的情況。