排列組合基礎知識點

基本概念排列：從\(n\)個不同元素中取出\(m\)（\(m\leqn\)）個元素，按照一定的順序排成一列，叫做從\(n\)個不同元素中取出\(m\)個元素的一個排列。排列數用符號\(A_{n}^m\)表示，計算公式為\(A_{n}^m=n(n-1)(n-2)\cdots(n-m+1)=\frac{n!}{(n-m)!}\)，其中\(zhòng)(n!=n\times(n-1)\times\cdots\times1\)，規(guī)定\(0!=1\)。例如，從\(5\)個不同元素\(a\)、\(b\)、\(c\)、\(d\)、\(e\)中取出\(3\)個元素的排列，如\(abc\)、\(acb\)、\(bac\)等都是不同的排列。計算\(A_{5}^3=5\times4\times3=60\)。組合：從\(n\)個不同元素中取出\(m\)（\(m\leqn\)）個元素并成一組，叫做從\(n\)個不同元素中取出\(m\)個元素的一個組合。組合數用符號\(C_{n}^m\)表示，計算公式為\(C_{n}^m=\frac{A_{n}^m}{A_{m}^m}=\frac{n!}{m!(n-m)!}\)。例如，從\(5\)個不同元素中取出\(3\)個元素的組合，\(abc\)、\(abd\)等是不同組合。計算\(C_{5}^3=\frac{5!}{3!(5-3)!}=\frac{5\times4\times3!}{3!\times2\times1}=10\)?；驹砑臃ㄔ恚和瓿梢患?，有\(zhòng)(n\)類辦法，在第\(1\)類辦法中有\(zhòng)(m_1\)種不同的方法，在第\(2\)類辦法中有\(zhòng)(m_2\)種不同的方法……在第\(n\)類辦法中有\(zhòng)(m_n\)種不同的方法，那么完成這件事共有\(zhòng)(N=m_1+m_2+\cdots+m_n\)種不同的方法。例如，從甲地到乙地，乘火車有\(zhòng)(3\)種方法，乘汽車有\(zhòng)(2\)種方法，那么從甲地到乙地共有\(zhòng)(3+2=5\)種方法。乘法原理：完成一件事，需要分成\(n\)個步驟，做第\(1\)步有\(zhòng)(m_1\)種不同的方法，做第\(2\)步有\(zhòng)(m_2\)種不同的方法……做第\(n\)步有\(zhòng)(m_n\)種不同的方法，那么完成這件事共有\(zhòng)(N=m_1\timesm_2\times\cdots\timesm_n\)種不同的方法。例如，從\(A\)地到\(C\)地，中間要經過\(B\)地，從\(A\)到\(B\)有\(zhòng)(2\)條路，從\(B\)到\(C\)有\(zhòng)(3\)條路，那么從\(A\)到\(C\)共有\(zhòng)(2\times3=6\)條路。排列組合的性質組合數的性質：1.\(C_{n}^m=C_{n}^{n-m}\)。例如\(C_{6}^2=\frac{6!}{2!(6-2)!}=\frac{6\times5}{2\times1}=15\)，\(C_{6}^4=C_{6}^{6-4}=C_{6}^2=15\)。2.\(C_{n+1}^m=C_{n}^m+C_{n}^{m-1}\)。這一性質在計算組合數時可簡化運算，例如計算\(C_{7}^3\)，可利用\(C_{7}^3=C_{6}^3+C_{6}^2\)，\(C_{6}^3=\frac{6!}{3!(6-3)!}=20\)，\(C_{6}^2=\frac{6!}{2!(6-2)!}=15\)，所以\(C_{7}^3=20+15=35\)。常見題型及解法相鄰問題——捆綁法：對于要求某些元素必須相鄰的問題，可先將相鄰元素看作一個整體與其他元素進行排列，然后再對相鄰元素內部進行排列。例如，\(A\)、\(B\)、\(C\)、\(D\)、\(E\)五個人站成一排，\(A\)、\(B\)必須相鄰，先將\(A\)、\(B\)看作一個整體，與\(C\)、\(D\)、\(E\)全排列，有\(zhòng)(A_{4}^4\)種排法，\(A\)、\(B\)內部有\(zhòng)(A_{2}^2\)種排法，所以共有\(zhòng)(A_{4}^4\timesA_{2}^2=48\)種排法。不相鄰問題——插空法：對于要求某些元素不能相鄰的問題，可先將其他元素排好，然后將不相鄰元素插入到這些元素形成的空位中。例如，\(A\)、\(B\)、\(C\)、\(D\)、\(E\)五個人站成一排，\(A\)、\(B\)不能相鄰，先排\(C\)、\(D\)、\(E\)，有\(zhòng)(A_{3}^3\)種排法，\(C\)、\(D\)、\(E\)排好后形成\(4\)個空位，從中選\(2\)個空位排\(A\)、\(B\)，有\(zhòng)(A_{4}^2\)種排法，所以共有\(zhòng)(A_{3}^3\timesA_{4}^2=72\)種排法。分組分配問題：1.平均分組：將\(n\)個不同元素平均分成\(m\)組，若分組后無順序要求，分組方法數為\(\frac{C_{n}^{n/m}C_{n-n/m}^{n/m}\cdotsC_{n/m}^{n/m}}{m!}\)。例如將\(6\)個人平均分成\(3\)組，方法數為\(\frac{C_{6}^2C_{4}^2C_{2}^2}{3!}=15\)種。2.非平均分組：將\(n\)個不同元素分成\(m\)組，每組元素個數不同，分組方法數為\(C_{n}^{a}C_{n-a}^\cdotsC_{n-a-b\cdots}^{z}\)（\(a+b+\cdots+z=n\)）。例如將\(6\)個人分成\(1\)人、\(2\)人、\(3\)人三組，方法數為\(C_{6}^1C_{5}^2