排列组合

• 排列的定义

从n个不同元素中,任取m个元素,按照一定的顺序排成一列， 叫做从n个不同元素中取出m个元素的一个排列。

• 组合的定义

从n个不同元素中，选出m个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合。

• 常用等式

理解: 从n中选m个 剩余n-m个, 和 选n-m个剩余n个的方法相同.

理解:

选中的m个数中分两种情况, 包含 1 和 不包含 1.

包含1的情况: 先选取1, 然后从剩下的数 n-1 中选择 m-1 个 .

不包含1的情况: 从n中排除掉 1, 从剩下的 n-1个中选择 m个

理解:

左边: 是从 n 个数中, 选任意多个数的方案.

右边: n 个数中每个有2个选择, 选和不选, 方案数是2ⁿ

• 排列&组合的区别

通俗地说，组合不分顺序，而排列分顺序，也就是说，对于数列 1,2，有以下两种排列：1, 2 和 2, 1，但是仅有一种组合 1, 2.

插入法

学校师生合影，共 8 个学生，4 个老师，要求老师在学生中间，且老师互不相邻，共有多少种不同的合影方式 ？

解：先排学生共有A⁸₈种排法, 然后把老师插入学生之间的空档，共有 7 个空档可插, 选其中的 4 个空档, 共有A⁴₇种选法.根据乘法原理,共有的不同 A⁸₈ A⁴₇种.

「插入法」：对于某两个元素或者几个元素要求不相邻的问题, 可以用插入法. 即先排好没有限制条件的元素, 然后将有限制条件的元素按要求插入排好元素的空档之中即可.

捆绑法

5个男生3个女生排成一排, 3个女生要排在一起, 有多少种不同的排法?

解: 因为女生要排在一起, 所以可以将3个女生看成是一个人, 与5个男生作全排列,有A⁶₆ 种排法, 其中女生内部也有 A³₃ 种排法,根据乘法原理, 共有A⁶₆A³₃  种不同的排法.

「捆绑法:」 要求某几个元素必须排在一起的问题, 可以用捆绑法来解决问题. 即将需要相邻的元素合并为一个元素, 再与其它元素一起作排列, 同时要注意合并元素内部也可以作排列.

剩余法

袋中有不同年份生产的5分硬币23个, 不同年份生产的1角硬币10个, 如果从袋中取出2元钱,有多少种取法?

分析 此题是一个组合问题,若是直接考虑取钱的问题的话,情况比较多,也显得比较凌乱，难以理出头绪来。但是如果根据组合数性质考虑剩余问题的话,就会很容易解决问题.

解：把所有的硬币全部取出来, 将得到 0.05×23+0.10×10=2.15元,所以比2元多0.15元, 所以剩下0.15元即剩下3个5分或1个5分与1个1角,所以共有A³₂₃+A¹₂₃A¹₁₀种取法.

「剩余法:」 在组合问题中,有多少取法,就有多少种剩法, 他们是一一对应的,因此,当求取法困难时,可转化为求剩法.

对等法

学校安排考试科目9门, 语文要在数学之前考, 有多少种不同的安排顺序?

分析：对于任何一个排列问题，就其中的两个元素来讲的话, 他们的排列顺序只有两种情况，并且在整个排列中, 他们出现的机会是均等的,因此要求其中的某一种情况，能够得到全体, 那么问题就可以解决了。并且也避免了问题的复杂性。

解：不加任何限制条件, 整个排法有A⁹₉种，“语文安排在数学之前考” 与 “数学安排在语文之前考”的排法是相等的, 所以语文安排在数学之前考的排法共有A⁹₉ ÷2种。

「对等法:」 在有些题目中，它的限制条件的肯定与否定是对等的，各占全体的二分之一。在求解中只要求出全体, 就可以得到所求。

排异法

某个班级共有43位同学，从中任抽5人，正、副班长、团支部书记至少有一人在内的抽法有多少种?

分析 此题若是直接去考虑的话,就要将问题分成好几种情况,这样解题的话,容易造成各种情况遗漏或者重复的情况. 而如果从此问题相反的方面去考虑的话,不但容易理解,而且在计算中也是非常的简便.这样就可以简化计算过程.

解：43人中任抽5人的方法有A⁵₄₃种, 正副班长, 团支部书记都不在内的抽法有 A⁵₄₀种, 所以正副班长,团支部书记至少有1人在内的抽法有A⁵₄₃ ^– A⁵₄₀种。

「排异法:」 有些问题, 正面直接考虑比较复杂, 而它的反面往往比较简捷,可以先求出它的反面, 再从整体中排除.

圆周排列

圆周排列与直线排列最大的区别是圆排列没有首尾之分

N个元素的圆周排列：8人围桌而坐，共有8!/8=7!种坐法

Aⁿ_n÷n=(n-1)!

从n个不同的元素中取r个沿一圆周排列，排列的方案：

A^r_n÷n

重复元素的排列

如:  n₁个 a,  n₂个 b,   n₃个C, 排成一排, 有多少种排列方法?

(n₁+n₂+n₃)!÷(n₁!n₂!n₃!)

重复元素的组合

从n种不同元素中取r个元素的组合. 允许有重复元素的组合:

例题: 平面上有3条平行直线, 每条直线分别上有 5, 6, 7个点, 且不同直线上3个点都不在同一条直线上. 问用这些点作为顶点, 能组成多少个不同的四边形().

解:

两种情况:

4个点, 在两条直线上, A上2个点, B上2个点 C²₅×C²₆=10×15=150

同理 AC上四边形个数: C²₅×C²₇=10×21=210

BC上: C²₅×C²₆=10×15=150

在一直线上有2点, 另外2点分别在另外两条直线上

A上2个点, BC上各1个: C²₅×C¹₆×C¹₇=10×6×7=420

B上2个点: AC上各1个 C²₆×C¹₅×C¹₇=15×6×7=525

C上2个点 AB各1个 C²₇×C¹₅×C¹₆=21×5×7=630

共有 150 + 210 + 315 + 420 + 525 + 630 = 2250.

例题: 由3个 a, 5 个 b, 2 个 c 组成的所字串中包含子串”abc”的共有多少个()

题解: “abc”看作一个整体, 剩下了2个a, 4个b, 1个c. 一共 8个含有相同元素的全排列. 所以有:

球盒问题

「n」 个球 放入 「m」 个盒子里的方案数