从来没学过这么通透的 - 排列&组合

从来没学过这么通透的 - 排列&组合

引用

CSDN

1.

https://blog.csdn.net/2302_80067378/article/details/146222028

排列与组合是算法和数学中的重要概念，它们在实际问题中有着广泛的应用。本文通过具体的生活实例，如学生排队问题，逐步引出排列和组合的定义，并通过对比分析帮助读者理解两者的区别。此外，文章还通过一道具体的题目，展示了排列与组合在实际问题中的应用，并指出了常见的错误解题思路。

昨天无意间，做了一道算法题，优雅的解法又需要用到组合这种数学知识！
这次，我要狠狠攻克它！
既然如此，那就将排列与组合一块打包学习吧。
注意，这里主要是讲解相关思想，具体算法大家可以到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. 代表中男、女都要有的不同的选法多少种？
   没算错吧！哈哈，思路可是这样的
   要选取至少一名女生，不就是如下思路
   直接法

• 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、排列&组合