昨天无意间，做了一道算法题，优雅的解法又需要用到组合这种数学知识！
这次，我要狠狠攻克它！
既然如此，那就将排列与组合一块打包学习吧。
注意，这里主要是讲解相关思想，具体算法大家可以到 leetcode、牛客、洛谷等算法平台上搜索。
目录
一、先说说什么是排列 
？
举一个生活中，常见的例子。
现在，有3名学生(A、B、C)排队，要站成一排，请问有几种排法？
编辑
所以答案就是 
，这不就是3的阶乘(3！)吗？
还不理解的，可以看一看图：
编辑
在深入探究一点，如果有10名学生，从中选取3名学生，排成一排，请问有几种排法？
编辑
所以答案就是 
，这不就是10的阶乘除以7的阶乘吗( 
)吗？
总结一下，于是假设总人数是n人，挑选m人，不就变成了 
也就是 
。
所以可以总结出来 
= 
。
小结一下：
为了更严谨，咱们正式一些。
排列：一般的，从n个不同的元素中取出m(m<=n)个元素，按一定顺序排成一排，叫做从n个元素中取出m个元素的一种排列。
排列数：一般的，从n个元素中取出m个元素的所有的排列个数，叫做从n个元素中取出m个元素的排列个数。用符合
表示。且
=
。
二、那什么又是组合数 
呢？
就还是那个例子。
现在，有10名学生(A、B、C...)，从中选取3名学生，请问有几种选法？
画重点了！本选择方法，不要求有序！
而上方咱们计算时，为 
，也就是 
而其中一共有 
种排序方法（ 
）
这一相除，不就变成了 
这个公式吗，也就是720/6=120种。
排列以后，不就变成了 
编辑这个公式吗！
小结一下：
组合：从n个不同的元素中任意挑选m(m<=n)个元素，组成一组，他就是从n个元素中挑选m个元素的一个组合。
组合数：从n个不同的元素中任意挑选m(m<=n)个元素，所有的组合个数，就是从n个元素中挑选m个元素的所有组合数
。
三、应用举例：
只懂概念，是肯定不行的。来！上题！巩固！
从4名男生、3名女生中，挑选3名代表，求：
- 至少有一名女生的不同选法共有多少种?
- 代表中男、女都要有的不同的选法多少种？
没算错吧！哈哈，思路可是这样的
要选取至少一名女生，不就是如下思路
直接法
- 1女2男
- 2女1男
- 3女0男
间接法
- 所有可能 ：0女3男
那有没有小可爱的思路是这样的呢？
哪为什么不能这样呢，即先选取1个女生，有3种可能，随后在剩下的6个人中，在选取2个人，这种思想错误吗，还是少判断哪里了？
这种思想是错误的，原因在于存在重复计数的情况。
按照你所说的思路，先从3名女生中选1名女生，有C31=3种选法；然后从剩下的6个人（4名男生和2名女生）中选2个人，有C62=2!(6−2)!6!=2×16×5=15种选法。根据分步乘法计数原理，这样得到的选法总数是3×15=45种。
下面举例说明重复计数的情况：
假设3名女生分别为A、B、C，4名男生分别为a、b、c、d。
情况一：先选女生A，然后从剩下6人中选B和a，得到组合{A,B,a}。
情况二：先选女生B，然后从剩下6人中选A和a，得到组合{B,A,a}。
这两种情况实际上是同一个组合{A,B,a}，但按照你的方法却被当作两种不同的选法进行了计数。
对于每一个包含2名女生的组合都会出现这样的重复情况，对于包含3名女生的组合，重复的情况会更复杂。所以这种先选1名女生再从剩下6人中选2人的方法不能正确计算至少有一名女生的选法数量。
OK啦，本题的正确答案是， 
而第二问方法是同样的，切记，不要将组合&排列搞混喽！
借鉴博客：
1、排列&组合
