1#组合数学初步——排列与组合之加法原理、乘法原理

青旅半醒 2022-11-11 10:51 138阅读 0赞

# 0\# “绪论” #

去年的CSP没有考过，经过总结发现，分数很多失在了排列组合上，如果对一道我就能进入复赛。经受惨痛教训，痛心疾首，决定重整旗鼓再出发，第一步就是**排列组合！**

我新开的这个专栏，几乎90%的文字来自《信息学奥赛一本通：初赛篇》，很少的部分为我的注解。借助CSDN作为笔记罢了。

在此做引，意为始励志。     ——2021/3/19

# 1\# 排列与组合 #

## 1.1\# 历史 ##

**起源**  
  1772年，旺德蒙德以`[n]p`表示由n个不同的元素中每次取p个的排列数。而欧拉则与1771年以及于1778年以表示由n个不同元素中每次取出p个元素的组合数。至1872年，埃汀肖森引入了以表相同之意，这组合符号（Signs of Combinations）一直沿用至今。

## 1.2\# 两个基本原理是排列和组合的基础 ##

（1）**加法原理**：做一件事，完成它可以有 n n n**类**办法，在第一类办法中有 m 1 m\_1 m1种不同的方法，在第二类办法中有 m 2 m\_2 m2种不同的方法，……，在第n类办法中有 m n m\_n mn种不同的方法，那么完成这件事共有 N = m 1 + m 2 + m 3 + ⋅ ⋅ ⋅ + m n N=m\_1+m\_2+m\_3+···+m\_n N=m1\+m2\+m3\+⋅⋅⋅\+mn种不同方法。  
（2）**乘法原理**：做一件事，完成它需要分成 n n n个**步骤**，做第一步有 m 1 m\_1 m1种**不同的方法**，做第二步有 m 2 m\_2 m2种不同的方法，……，做第 n n n步有 m n mn mn种不同的方法，那么完成这件事共有 N = m 1 × m 2 × m 3 × ⋅ ⋅ ⋅ × m n N=m\_1 \\times m\_2 \\times m\_3 \\times···\\times m\_n N=m1×m2×m3×⋅⋅⋅×mn种不同的方法。

这样完成一件事的分“类”和“步”是有本质区别的，因此也将两个原理区分开来。

疏：  
例如：  
（1）从甲城市到乙城市一共有几条路？5+3+7=15条【加法原理】  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]

（2）甲城市到丙城市有几条走法？3*2=6条【乘法原理】  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]  
（3）甲城市到丙城市有几条走法？2+3+2*3条【乘法原理】&【加法原理】  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]

好了，算是彻底通透了，对于加法、乘法原理理解清晰之后。就可以踏踏实实的学习排列组合了。

**换句话说，加法、乘法原理就是排列组合的垫脚石。**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/3cf2fa58b93d4e33afe46dbd6d21d54e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210320211806311.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/2021032021192436.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Nvb2w5OTc4MQ==,size_16,color_FFFFFF,t_70#pic_center