noip初赛中组合数学(共11页).doc

noip初赛中的组合数学排列和组合：怎么排，怎么组合？研究的意义在于统计排列和组合的个数。四个基本的计数原理：加法原理、乘法原理、减法原理、除法原理。排列：全排列P(n,n)=n!部分排列P(n,r)=n*(n-1)*(n-2)*(n-r+1)= n！/ (n-r)!圆排列: Q(n,n)= P(n,n)/n= (n-1)!组合: C(n,r)= n!/ ( (n-r)! * r! ) 学习提示：每条公式都要给出它的物理意义。第一章 加法原理与乘法原理1.加法原理:完成一个工程可以有n类办法，ai(1=i=n) 代表第i类方法的数目。那么完成这件事共有 S = a1+a2+.+an 种不同的方法。 2.乘法原理: 完成一个工程需要分n个步骤，ai(1=i=n) 代表第i个步骤的不同方法数目。那么完成这件事共有 S = a1*a2*.*an 种不同的方法。 3.两个原理的区别:一个与分类有关 ， 一个与分步有关；加法原理是“分类完