排列組合公式

1、排列組合公式1分類計數(shù)原理（加法原理）N m m2 L mn2 分步計數(shù)原理（乘法原理）N m m2 L mn3.排列數(shù)公式A： _ n(n1)(n m 1) = (nm).(n , m n*，且 m n )注:規(guī)定0!1.4 排列恒等式Am (1)、n m1)Am1;5Am(2)nAmin mAn 15AmfnA：11;5叭“.n 1An 1A：.5Am1mm 1AnmAn1! 2 2! 33! L n n!(n1)! 15 組合數(shù)公式Amn(n1)(n m 1)n!Cn = Am =1 2 m =m! (nm)!(n n* , m N，且 mn)6 組合數(shù)的兩個性質(zhì)(1)Cmnn _ Cn

2、Cmm 1n + Cn注:規(guī)定Cn17 組合恒等式(1)cmnmcn 1 n mcmncnn(4) r 0= 2 ;C； C；1 Crr2(5)cnC0 C1C2(6) CnCnCncncn 2n cn c3 c：c0 cC：2門1(8)cn 2C： 3Cn3nC；n2n 1r 0 r 1 1(9) CmCnCm Cncmrc；cm n.0 2 1 2(1)(Cn)(6)2 2(Cn)(C；)2C2n&排列數(shù)與組合數(shù)的關(guān)系A(chǔ)mmi cm.9 單條件排列以下各條的大前提是從（1）在位”與不在位”n個元素中取m個元素的排列Am 1某（特）元必在某位有n 1種;某（特）元不在某位有A aS1 （補(bǔ)集

3、思想） 冗小畀（著眼位置）Am A1 Am 1An 11Al 1 (著眼元素)種.（2）緊貼與插空（即相鄰與不相鄰）定位緊貼:k（k m n）個元在固定位的排列有 AkAn k種.浮動緊貼:An k 1Akn個元素的全排列把 k個元排在一起的排法有An k 1 Ak種.注：此類問題常用捆綁法;插空：兩組元素分別有 k、h個（k h 1），把它們合在一起來作全排列,k個的一組互不能挨近的所有排列數(shù)有A尺1種.（3 ）兩組元素各相同的插空m個大球n個小球排成一列，小球必分開，問有多少種排法?n當(dāng)n m 1時，無解；當(dāng)n m 1時，有An(4 )兩組相同元素的排列：Cn兩組元素有m個和n個，各組元素

4、分別相冋的排列數(shù)為Cm n種排法.10.分配問題n個物件等分給m個人，各得n件，其分配方N法數(shù)共有CnmnCn Cnmn n mn 2nC2n cn(mn)!m(n!)(2)(平均分組無歸屬問題分配方法數(shù)共有)將相異的m n個物體等分為無記號或無順序的m堆，其Cncncncn cnCmn Cmn n Cmn 2n c2n Cnm!(mn)!m!(n!)m(3)(非平均分組有歸屬問題)將相異的P(P=n1+n2+L + nm)個物體分給m個人，物件必須被分完，分別得到n1 , n2 ,nm件且n1n2nm這m個數(shù)彼此不相等，則其分配方法數(shù)共有(4)(非完全平均分組有歸屬問題n1Pn2Pn1Cnm

5、nmm!p!m!nn2L.nm!)將相異的P(P二n1+n2 + L +nm)個物體分給m個人，物件必須被分完，分別得到n1, n2，nm件，且n1, n2,nm這m個數(shù)中分別Nc、個相等，則其分配方法數(shù)有n1Pn2Pn1.Ca!b!c!.nm nmm!(1)(平均分組有歸屬問題)將相異的m、p! m!n1!n2!.nm !(a !b!c!.)(5)(非平均分組無歸屬問題)將相異的P(P = n1+n2+L +nm)個物體分為任意的nn2nm件無記號的m堆，且n1 ,山,nm這m個數(shù)彼此不相等，則其分N配方法數(shù)有(6)(非完全平均分組無歸屬問題)將相異的P(P =n1+n2 + L + nm)

6、個物體分為任意的n1 ,n2nm件無記號的m堆，且n1 ,匕,nm這m個數(shù)中分別有a、b、c、11.12.13.N個相等，則其分配方法數(shù)有(7)(限定分組有歸屬問題)將相異的P!n1! n2! .n m!(a!b!c!.)p( p n1+ n2 + L +nm)個物體分給甲、乙、丙,等m個人，物體必須被分完，如果指定甲得則無論n1 ,匕，,N CP1 CPU：n1件，乙得n2件，丙得n3件，時,nm等m個數(shù)是否全相異或不全相異其分配方法數(shù)恒有P!njn 2!. nm!錯位問題”及其推廣貝努利裝錯箋問題：信n封信與n個信封全部錯位的組合數(shù)為f(n) n !丄-2!3!推廣：n個元素與f(n, m

7、) n!C1n!1 誥1 l4!n個位置1(Jn!，其中至少有cm(n 1)!(1燉(門 p)! LCm(n 2)!C2 C3 C4mmm 224 L代代A不定方程X1+x2 + L %(1)方程 X1+X2 + L +Xnm個元素錯位的不同組合總數(shù)為cm(n 3)! cm(n 4)!(1)mcm(nm)!1)PCj lC m(噲m的解的個數(shù)m( n, m的正整數(shù)解有方程 X1+X2 + L +Xn方程X1+X2 + L +焉整數(shù)解有C方程 X1+x2 + LC n 1數(shù)解有n m 1m( n, mm( n, m(n 2)( k 1)個.+Xn m( n,mC1 Cn 1n 2 m n k 2C2n 2)的非負(fù)整數(shù)解有)滿足條件)滿足條件Cn 1m n 2k