排列组合中的加法和乘法原理

编辑：小文

近3年CSPJ初赛考察：

是计算排列组合的基础，可以认为近3年所有组合数学题目都和它有关。

难度：简单

排列组合是组合数学的基础。历年来，CSP初赛考题中会适当的出现1-3道排列组合的选择题，虽然分值不多，但是大纲中涉及到了，需要认真学习下这部分内容。而学习排列组合，理解分类加法和分步乘法原理是基础。

分类加法和分步乘法原理

先来看这道例题！从甲地到乙地有两条路可走，从乙到丙地有三条路可走，从甲地不经乙地直达丙地有三条路可走，问从甲地到丙地的不同走法有几种？

答案是多少我们先留个悬念。但是在这道题目中，实际上已经使用到了分类加法和分步乘法原理。

1. 分类加法计数原理

做一件事，完成它可以有n类办法，在第一类办法法中有m1m_1m1​种方法，在第二类办法中有m2m_2m2​种不同的方法，……，在第nnn类办法中有mnm_nmn​种不同的方法，不同类别的方法累加起来就是完成这件事的总方法数。即N\=m1+m2+…+mnN = m_1 + m_2 + … + m_nN\=m1​+m2​+…+mn​种不同的方法。要做到不重不漏。

2. 分步乘法计数原理

做一件事，完成它需要分成n个步骤，做第一步有m1m_1m1​种方法，做第二步有m2m_2m2​种不同的方法，……，做第nnn步有mnm_nmn​种不同的方法，不同步骤的方法数相乘就是完成这件事的总方法数。即N\=m1×m2×…×mnN = m_1 \times m_2 \times … \times m_nN\=m1​×m2​×…×mn​种不同的方法。要做到步骤完整。

3. 例题讲解

从甲地到丙地有两类方法，由加法原理可知，将两类方法的数量加起来就是答案：

第一类方法：从甲直接到丙，共333种方法

第二类方法：从甲到乙，间接再到丙，共666种方法

该方法需要有两个步骤，所以需要用到乘法原理，从甲到乙2种方法，从乙到丙3种方法，所以一共有2×3\=62\times 3=62×3\=6种方法

因此，从甲到丙有3+6\=93+6=93+6\=9种方法。

理解了加法和乘法原理，接下来认识排列组合会更加轻松。

⚡快问快答 题目数量 共3题

排列组合

近3年CSPJ初赛考察：

难度：困难

什么是排列？

从nnn个不同元素中，任取m(m≤n,mm(m≤n,mm(m≤n,m与nnn均为自然数,下同）个不同的元素按照一定的顺序排成一列，叫做从nnn个不同元素中取出mmm个元素的一个排列。

如果两个排列相同，不仅这两个排列的元素必须完全相同，而且排列的顺序必须完全相同。比如，4个数字1、2、3、4，选出3个数字，123是一个排列，321是一个排列，二者是两个不同的排列。

排列数

从nnn个不同元素中取出m(m≤n)m(m≤n)m(m≤n)个元素的所有排列的个数，叫做从nnn个不同元素中取出mmm个元素的排列数，用符号A(n,m)A(n,m)A(n,m)表示，也可以表示为AnmA_n^mAnm​(其中n!n!n!表示nnn的阶乘，注意0!\=10! = 10!\=1)。以下为排列数计算公式：

Anm\=n(n−1)(n−2)…(n−m+1)\=n!(n−m)!A_n^m=n(n-1)(n-2)…(n-m+1)=\frac{n!}{(n-m)!}Anm​\=n(n−1)(n−2)…(n−m+1)\=(n−m)!n!​

🌰思考：从1、2、3、41、2、3、41、2、3、4这4个数字中，取333个数字共有多少排列数呢？

想象333个数字，一个数字一个位置，333个位置上填写数字的种类分别是4、3、24、3、24、3、2种可能，把它们乘起来就是答案。所以A43\=4×3×2\=4!1!A_4^3=4 \times 3 \times 2=\frac{4!}{1!}A43​\=4×3×2\=1!4!​，这里用阶乘表示会比较方便。

请你尝试写出这道思考题所有的排列数。

什么是组合？

从nnn个不同元素中，任取m(m≤n)m(m≤n)m(m≤n)个元素并成一组，叫做从nnn个不同元素中取出mmm个元素的一个组合。

如果两个组合中的元素完全相同，不管元素的顺序如何，都是相同的组合；只有当两个组合中的元素不完全相同的时候，才是不同的组合。比如，4个数字1、2、3、4，选出3个数字，123是一个组合，321与123是相同的组合，因为二者包含的数字一样。

组合数

从nnn个不同元素中取出m(m≤n)m(m≤n)m(m≤n)个元素的所有组合的个数，叫做从nnn个不同元素中取出mmm个元素的组合数。用符号C(n,m)C(n,m)C(n,m)表示，也可以表示为CnmC_n^mCnm​。以下为组合数计算公式：

Cnm\=Anmm!\=n!m!(n−m)!;C(n,m)\=C(n,n−m)C_n^m=\frac{A_n^m}{m!}=\frac{n!}{m!(n-m)!};C(n,m)=C(n,n-m)Cnm​\=m!Anm​​\=m!(n−m)!n!​;C(n,m)\=C(n,n−m)，其中n≥m.n \geq m.n≥m.

观察公式大家可以发现，Cnm与AnmC_n^m与A_n^mCnm​与Anm​的关系仅相差一个m!m!m!。这里是为什么呢？

因为每一组相同元素的组合，在排列数中都重复出现了m!m!m!次。比如，1、2、3这一种组合，有3!\=63!=63!\=6种不同的排列，因此可以对排列数做除法去重得到组合数。

🌰思考：从1、2、3、4这4个数字中，取3个数字共有多少组合数呢？

排列数为A43\=4×3×2\=4!1!\=24A_4^3=4 \times 3 \times 2=\frac{4!}{1!}=24A43​\=4×3×2\=1!4!​\=24种，组合数有C43\=A433!\=8C_4^3 = \frac{A_4^3}{3!}=8C43​\=3!A43​​\=8种。

请你尝试写出这道思考题所有的组合数。

⚡快问快答 题目数量 共3题

计数模型总结

排列组合的本质是计数，计数的本质是枚举。问题简单时，可以直接枚举，问题复杂时，首先对问题归类，采用不同策略。下面就来介绍一些经典的计数模型。

不同元素之间的模型

特元特位

特征：有特殊要求得元素或者位置，即特元特位。 方法：特殊的需要优先计算，再去考虑其他元素、位置；如果多个特殊有冲突，特殊位可以直接枚举。

元素相邻

特征：要求n个元素必须相邻 方法：可采取捆绑法。将这n个元素捆绑后视为1个“新元素”，与剩余元素进行操作，最后捆绑内部在进行全排列。

元素不相邻

特征：要求n个元素不相邻 方法：可采用插空法。有(m+n)(m+n)(m+n)个元素，其中(m+1)≥n(m+1) \geq n(m+1)≥n，要求nnn个元素互不相邻，则先安排mmm个元素，形成(m+1)(m+1)(m+1)个空，再将nnn个元素安排到(m+1)(m+1)(m+1)个空位上。

分组与分配

特征：将不同元素分配给不同对象 方法：按照先分组，再分配的原则进行。其中分组有：平均分组，不平均分组，部分平均分组；分配有定向分配和不定向分配。

相同元素之间的模型

特征：将相同元素分配给不同对象 方法：采用隔板法。n个相同元素放入m个不同盒子，要求每个盒子至少有一个元素。

隔板法

隔板法也称插板法，可用来处理n个无差别的球放进m个不同的盒子等类似形式的问题。

假设现在有10个球，要放进4个盒子里，盒子不允许为空。可以在10个小球的9个空隙中，选择3个位置放入隔板。例如●●|●●●|●●●|●●，方案数为C93C_9^3C93​。

那么n个球放入m个不同盒子，盒子不为空的方案数则为Cn−1m−1C_{n-1}^{m-1}Cn−1m−1​。

小球问题也可以进一步引申为，求解m个正整数加和为n的方案数这一类数学问题，即∑i\=1mxi\=n\sum_{i=1}^mx_i = n∑i\=1m​xi​\=n的答案的个数，其中∑\sum∑为求和符号。

🌰 进一步思考，如果允许盒子为空如何计算？

答案是Cn+m−1m−1C_{n+m-1}^{m-1}Cn+m−1m−1​。有两种理解方法：

方法1，此时可以假设当前4个盒子初始已经放进了4个小球，那么剩下的10个小球就可以随意放置，问题转化为14个小球放进4个盒子里的问题，即C133C_{13}^3C133​;

方法2，当盒子允许为空，存在几个板子可以放在同一个空隙里的可能，此时板子和小球地位一样，相当于把14个板子和小球划分成4个部分，即C133C_{13}^3C133​；如图示●●/||/●●●●●/●|●●，这里的”|”表示板子，”/“表示新的划分间隔。

📜历年真题