排列组合.doc

排列组合排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。 排列组合与古典概率论关系密切。排列分类：选排列和全排列，可重复排列，不尽相异元素的全排列，环状排列组合分类：通常意义的组合，可重复排列排列的定义及其计算公式：从n个不同元素中，任取m(mn,m与n均为自然数,下同）个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(mn）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号A(n,m）表示。A(n,m)=n(n-1)(n-2）（n-m+1）= n!/(n-m)! 此外规定0!=1组合的定义及其计算公式：从n个不同元素中，任取m(mn）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(mn）个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号 C(n,m) 表示。C(n,m)=A(n,m）2/m!=A(n,m)/m！； C(n,m)=C(n,n-m）。（其中nm)其他排列与组合公式，从n个元素中取出m个元素的循环排列数=A(n,m)/m=n!/m(n-m)!. n个元素被分成k类，每类的个数分别是n1,n2,.nk这n个元素的全排列数为 n!/(n1！n2！.nk!). k类元素，每类的个数无限，从中取出m个元素的组合数为C(m+k-1,m）。加法原理和分类计数法加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，在第n类办法中有mn种不同的方法，那么完成这件事共有N=m1+m2+m3+mn种不同方法。第一类办法的方法属于集合A1，第二类办法的方法属于集合A2，第n类办法的方法属于集合An，那么完成这件事的方法属于集合A1UA2UUAn。分类的要求 ：每一类中的每一种方法都可以独立地完成此任务；两类不同办法中的具体方法，互不相同（即分类不重）；完成此任务的任何一种方法，都属于某一类（即分类不漏）。乘法原理和分步计数法 乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，做第n步有mn种不同的方法，那么完成这件事共有N=m1m2m3mn种不同的方法。合理分步的要求任何一步的一种方法都不能完成此任务，必须且只须连续完成这n步才能完成此任务；各步计数相互独立；只要有一步中所采取的方法不同，则对应的完成此事的方法也不同。折叠二项式定理(a+b)n=（0-n)C(in)a(n-i)bi通项公式：a_(i+1）=C(in)a(n-i)bi二项式系数：C(i，n)杨辉三角：两端是1，除1外的每个数是肩上两数之和。系数性质：和首末两端等距离的系数相等；杨辉三角当幂指数是奇数时，中间两项最大且相等；当幂指数是偶数时，中间一项最大。奇数项和偶数项总和相同，都是2(n-1）；所有系数总和是2n例1. 从1、2、3、20这二十个数中任取三个不同的数组成等差数列，这样的不同等差数列有多少个？解：设a,b,c成等差， 2b=a+c，可知b由a,c决定，又 2b是偶数， a,c同奇或同偶，即：分别从1，3，5，19或2，4，6，8，20这十个数中选出两 个数进行排列，由此就可确定等差数列，A（10,2）*2=90*2，因而本题为180。例2. 某城市有4条东西街道和6条南北的街道，街道之间的间距相同，若规定只能向东或向北两个方向沿图中路线前进，则从M到N有多少种不同的走法?解：对实际背景的分析可以逐层深入：（一）从M到N必须向上走三步，向右走五步，共走八步；（二）每一步是向上还是向右，决定了不同的走法；（三）事实上，当把向上的步骤决定后，剩下的步骤只能向右；从而，任务可叙述为：从八个步骤中选出哪三步是向上走，就可以确定走法数。 本题答案为：C（8,3）=56。例3在一块并排的10垄田地中，选择二垄分别种植A，B两种作物，每种种植一垄，为有利于作物生长，要求A，B两种作物的间隔不少于6垄，不同的选法共有多少种？解：条件中“要求A、B两种作物的间隔不少于6垄”这个条件不容易用一个包含排列数，组合数的式子表示，因而采取分类的方法。第一类：A在第一垄，B有3种选择；第二类：A在第二垄，B有2种选择；第三类：A在第三垄，B有1种选择，同理A、B位置互换 ，共12种。例4从6双不同颜色的手套中任取4只，其中恰好有一双同色的取法有多少种？（A)240 (B)180 (C)120 (D)