排列组合公式

1、排列组合公式1分类计数原理（加法原理）N m m2 L mn2 分步计数原理（乘法原理）N m m2 L mn3.排列数公式A： _ n(n1)(n m 1) = (nm).(n , m n*，且 m n )注:规定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 组合数公式Amn(n1)(n m 1)n!Cn = Am =1 2 m =m! (nm)!(n n* , m N，且 mn)6 组合数的两个性质(1)Cmnn _ Cn

2、Cmm 1n + Cn注:规定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&排列数与组合数的关系Ammi cm.9 单条件排列以下各条的大前提是从（1）在位”与不在位”n个元素中取m个元素的排列Am 1某（特）元必在某位有n 1种;某（特）元不在某位有A aS1 （补集

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个的一组互不能挨近的所有排列数有A尺1种.（3 ）两组元素各相同的插空m个大球n个小球排成一列，小球必分开，问有多少种排法?n当n m 1时，无解；当n m 1时，有An(4 )两组相同元素的排列：Cn两组元素有m个和n个，各组元素

4、分别相冋的排列数为Cm n种排法.10.分配问题n个物件等分给m个人，各得n件，其分配方N法数共有CnmnCn Cnmn n mn 2nC2n cn(mn)!m(n!)(2)(平均分组无归属问题分配方法数共有)将相异的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个数彼此不相等，则其分配方法数共有(4)(非完全平均分组有归属问题n1Pn2Pn1Cnm

5、nmm!p!m!nn2L.nm!)将相异的P(P二n1+n2 + L +nm)个物体分给m个人，物件必须被分完，分别得到n1, n2，nm件，且n1, n2,nm这m个数中分别Nc、个相等，则其分配方法数有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个数彼此不相等，则其分N配方法数有(6)(非完全平均分组无归属问题)将相异的P(P =n1+n2 + L + nm)

6、个物体分为任意的n1 ,n2nm件无记号的m堆，且n1 ,匕,nm这m个数中分别有a、b、c、11.12.13.N个相等，则其分配方法数有(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个数是否全相异或不全相异其分配方法数恒有P!njn 2!. nm!错位问题”及其推广贝努利装错笺问题：信n封信与n个信封全部错位的组合数为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个元素错位的不同组合总数为cm(n 3)! cm(n 4)!(1)mcm(nm)!1)PCj lC m(哙m的解的个数m( n, m的正整数解有方程 X1+X2 + L +Xn方程X1+X2 + L +焉整数解有C方程 X1+x2 + LC n 1数解有n m 1m( n, mm( n, m(n 2)( k 1)个.+Xn m( n,mC1 Cn 1n 2 m n k 2C2n 2)的非负整数解有)满足条件)满足条件Cn 1m n 2k