排列组合（组合学最基本的概念）

排列组合

组合学最基本的概念

排列组合是组合学最基本的概念。所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。排列组合与古典概率论关系密切,是进一步学习的基础。

发展历程

虽然数数始于结绳计数的远古时代，由于那时人的智力的发展尚处于低级阶段，谈不上有什么技巧。随着人们对于数的了解和研究，在形成与数密切相关的数学分支的过程中，如数论、代数、函数论以至泛函的形成与发展，逐步地从数的多样性发现数数的多样性，产生了各种数数的技巧。

由此观之，组合学与其他数学分支有着必然的密切联系。它的一些研究内容与方法来自各个分支也应用于各个分支。当然，组合学与其他数学分支一样也有其独特的研究问题与方法，它源于人们对于客观世界中存在的数与形及其关系的发现和认识。例如，中国古代的《易经》中用十个天干和十二个地支以六十为周期来记载月和年，以及在洛书河图中关于幻方的记载，是人们至今所了解的最早发现的组合问题甚或是架构语境学。

基本简介

排列分类：选排列和全排列，可重复排列，不尽相异元素的全排列，环状排列

组合分类：通常意义的组合，可重复排列

公式

排列的定义及其计算公式：从n个不同元素中，任取m(m≤n,m与n均为自然数,下同）个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号A(n,m）表示。A(n,m)=n(n-1）（n-2）……（n-m+1）=n!/(n-m)!此外规定0!=1

组合的定义及其计算公式：从n个不同元素中，任取m(m≤n）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n）个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号C(n,m)表示。C(n,m)=A(n,m）∧2/m!=A(n,m)/m！；C(n,m)=C(n,n-m）。（其中n≥m)

其他排列与组合公式从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）。

符号

C-Combination组合数

A-Arrangement排列数（在旧教材为P-Permutation）

N-元素的总个数

M-参与选择的元素个数

！-阶乘

基本计数原理

⑴加法原理和分类计数法

⒈加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，……，在第n类办法中有mn种不同的方法，那么完成这件事共有N=m1+m2+m3+…+mn种不同方法。

⒉第一类办法的方法属于集合A1，第二类办法的方法属于集合A2，……，第n类办法的方法属于集合An，那么完成这件事的方法属于集合A1UA2U…UAn。

⒊分类的要求：每一类中的每一种方法都可以独立地完成此任务；两类不同办法中的具体方法，互不相同（即分类不重）；完成此任务的任何一种方法，都属于某一类（即分类不漏）。

⑵乘法原理和分步计数法

⒈乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事共有N=m1×m2×m3×…×mn种不同的方法。

⒉合理分步的要求

任何一步的一种方法都不能完成此任务，必须且只须连续完成这n步才能完成此任务；各步计数相互独立；只要有一步中所采取的方法不同，则对应的完成此事的方法也不同。

二项式定理

(a+b)^n=Σ（0->n)C(in)a^(n-i)b^i

通项公式：a_(i+1）=C(in)a^(n-i)b^i

二项式系数：C(in)

杨辉三角：右图。两端是1，除1外的每个数是肩上两数之和。

系数性质：⑴和首末两端等距离的系数相等。

⑵当幂指数是奇数时，中间两项最大且相等。

⑶当幂指数是偶数时，中间一项最大。

⑷奇数项和偶数项总和相同，都是2^(n-1）。

⑸所有系数总和是2^n。

著名问题

计算一些物品在特定条件下分组的方法数目。这些是关于排列、组合和整数分拆的。

地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题。

船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？这是线性规划的问题。

中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。这也是图论的问题。

任务分配问题（也称婚配问题）：有一些员工要完成一些任务。各个员工完成不同任务所花费的时间都不同。每个员工只分配一项任务。每项任务只被分配给一个员工。怎样分配员工与任务以使所花费的时间最少？这是线性规划的问题。

如何构作幻方。

大乐透

概述

定义

公式P是指排列，从N个元素取R个进行排列(即排序)。

公式C是指组合，从N个元素取R个，不进行排列（即不排序）。

排列：从N个不同元素中，任取M（M<=N）个元素，按照一定的顺序排成一列，叫做从N个不同元素中取出M个元素的一个排列。

排列数：从N个不同元素中取出M（M<=N）个元素的所有排列的个数，叫做从N个不同元素中取出M个元素的排列数。记作：Pmn

排列数公式：Pmn=n(n-1)(n-2)...(n-m1)

全排列：N个不同元素全部取出的一个排列，叫做N个不同元素的一个全排列。

自然数1到N的连乘积，叫做N的阶乘。记作：n!（0!=1）

全排列公式：PNN=n!

排列数公式还可写成：Pmn=n!/(n-m)!

加法原理：做一件事，完成它可以有N类加法，在第一类办法中有M1种不同的方法，在第二类办法中有M2种不同的方法，...，在第N类办法中有MN种不同的方法。那么完成这件事共有N=M1M2...MN种不同的方法。

乘法原理：做一件事，完成它需要分成N个步骤，做第一步有M1种不同的方法，做第二步有M2种不同的方法，...，做第N步有MN种不同的方法，那么完成这件事共有N=M1×M2×...×MN种不同的方法。

C-组合数

P-排列数

N-元素的总个数

R参与选择的元素个数

！-阶乘，如5！=5*4*3*2*1=120

组合：从N个不同元素中，任取M（M<=N）个元素并成一组，叫做从N个不同元素中取出M个元素的一个组合。

排列与元素的顺序有关，组合与元素的顺序无关。

组合数：从N个不同元素中取出M（M<=N）个元素的所有组合的个数，叫做从N个不同元素中取出M个元素的组合数。记作：Cmn

组合数公式：Cmn=Pmn/Pmm=n(n-1)(n-2)...(n-m1)/m!=n!/m!/(n-m)!

组合性质1：Cmn=Cn-mn(C0n=1)

组合性质2：Cmn1=CmnCm-1n

C-Combination组合

P-Permutation排列

排列的变化

排列的变化，排列数“P”现在已成了“A”，P是旧用法，现在教材上多用A，即Arrangement也就是说，“P33”已成了“A33”.高考、中考也是这样，希望大家改过来！

小学排列组合公式

1、“Cmn”=“Cm（m-n）”

2、“Cm0（m大于0）”=1

3、“Cm0”“Cm1”......“Cm10”=2的m次方

举例分析

排列、组合的概念具有广泛的实际意义，解决排列、组合问题，关键要搞清楚是否与元素的顺序有关。复杂的排列、组合问题往往是对元素或位置进行限制，因此掌握一些基本的排列、组合问题的类型与解法对学好这部分知识很重要。

排列与组合的区别与联系：与顺序有关的为排列问题，与顺序无关的为组合问题。

解决排列组合问题要讲究策略，首先要认真审题，弄清楚是排列(有序)还是组合(无序)，还是排列与组合混合问题。其次，要抓住问题的本质特征，准确合理地利用两个基本原则进行“分类与分步”。

加法原理的特征是分类解决问题，分类必须满足两个条件：①类与类必须互斥(不相容)，②总类必须完备(不遗漏)；乘法原理的特征是分步解决问题，分步必须做到步与步互相独立，互不干扰并确保连续性。分类与分步是解决排列组合问题的最基本的思想策略，在实际操作中往往是“步”与“类”交叉，有机结合，可以是类中有步，也可以是步中有类。

参考资料

1.排列组合公式a和c计算方法·高三网