【算法•日更•第四十一期】组合与排列

小灰灰 2023-06-03 02:52 58阅读 0赞

▎排列

☞『引入』

思考一个问题：

> 你的眼前现在有三个人：gzr、lsh、hza，如何排列他们的位置呢？

显然，有这样的排法：

> gzr、lsh、hza
> 
> gzr、hza、lsh
> 
> hza、lsh、gzr
> 
> hza、gzr、lsh
> 
> lsh、gzr、hza
> 
> lsh、hza、gzr

一共是六种。

☞『定义』

这不就是排个顺序吗？相信定义就不需要拿出来讲了。

但是唯一要注意一点：排列是关心顺序的。

☞『n中选n个求解』

那么我们在n个人中进行排列的方案数有多少种呢？

显然，第一个人有n种方案;

第二个人有n-1种方案;

第三个人有n-2种方案;

……

第n个人有1种方案;

按照乘法原理，总的方案数就是n\*(n-1)\*(n-2)\*…\*2\*1。

发现了什么？这岂不是 n！ 。

☞『n中选m个求解』

依旧是上面的思路，只不过不是n！了。

现在我们来思考：n！在这种情况下，被多乘了多少次？

当然有（n-m）！次都是多乘的，所以有n！/（n-m）！个方案。

▎排列数

当n个中取m个的时候，我们可以用![1551435-20190812134559379-1147097195.png][]来表示。

比如说5个数排列三个位置就有![1551435-20190812134736824-581898725.png][]个方案。

▎组合

☞『引入』

来思考下面的问题：

> 有三只小狗，分别是中华田园犬、柴犬、拉布拉多。
> 
> 但是现在只有两块狗狗零食，那么为了公平起见，一只狗最多只能吃一个，所以只能给两只狗狗吃，剩下的那一只只能下次了。
> 
> 所以，问题是：分配的方案数有多少种？

这就是组合的问题。

☞『定义』

在刚才的问题中，仍然是上面的选择方案数问题，但是却不太一样了。

由于狗狗吃了就是吃了，不会在意顺序，而刚才的排列是在意顺序的。

所以，组合和排列不同的地方就是是否关心顺序是怎样的。

☞『求解』

对比刚才的排列，如何快速求出组合的方案数呢？

不难发现同一种组合方式被当作排列一定会算![1551435-20190812135946390-1955199729.png][]，所以就只要在排列的结果上除以![1551435-20190812140012621-819321932.png][]就可以了。

所以公式就是：![1551435-20190812140058157-1392771838.png][]。

▎组合数

☞『表示』

刚才的那个C的符号就是组合的符号，和排列的用法一样。

也就是说将n中选m个的排列方案数记做![1551435-20190812140237833-444632688.png][]。

☞『通项公式』

现在不思考前n-1个数是怎么选的，只关心第n个数。

显然，情况就两种，要么被选，要么不被选。

被选上一定是从![1551435-20190812140455613-828797199.png][]转移来的，不被选上一定是从![1551435-20190812140540907-1165190792.png][]转移来的。

所以按照加法原理，通项公式就是这样的：![1551435-20190812140608498-1517850126.png][]。

转载于:https://www.cnblogs.com/TFLS-gzr/p/11336424.html

[1551435-20190812134559379-1147097195.png]: /images/20230601/7241fad254ce40b5abf110580336a8f7.png
[1551435-20190812134736824-581898725.png]: /images/20230601/5142f3e6e2334456aac5a5abec8ec24e.png
[1551435-20190812135946390-1955199729.png]: https://img2018.cnblogs.com/blog/1551435/201908/1551435-20190812135946390-1955199729.png
[1551435-20190812140012621-819321932.png]: /images/20230601/02efb55805c5478fa939b4bf09cb7fa3.png
[1551435-20190812140058157-1392771838.png]: /images/20230601/1b44ebc0cf484ed6b1032332b5cd87ad.png
[1551435-20190812140237833-444632688.png]: /images/20230601/8983f1b538f548b0ad589282bc947b1f.png
[1551435-20190812140455613-828797199.png]: https://img2018.cnblogs.com/blog/1551435/201908/1551435-20190812140455613-828797199.png
[1551435-20190812140540907-1165190792.png]: /images/20230601/0d717473bdcd4815b7c77794c6b8b33c.png
[1551435-20190812140608498-1517850126.png]: /images/20230601/292b988683b242ed865012591075ced9.png