第7讲加法原理与乘法原理知识网络排列与组合问题是围绕计数问题展开的一类问题。解决此类问题，一般要用到两个常用的原理，即加法原理和乘法原理。要完成一个任务，如果能分成r类彼此独立的不同方式，第一类方式有种不同的方法可以完成任务，第二类方式有种不同的方法可以完成任务，⋯⋯，第r方式有种不同的方法完成任务。那么完成这个任务就有种不同的方法，这种分类计数的方法就称为加法原理。如果完成某项任务要分r个不同的步骤，第一步有种不同的方法完成任务，第二步有种不同的方法完成任务，⋯⋯，第r步有种不同的方法完成任务。那么完成这个任务就有种不同的方法，这种步骤完成任务的计数方法称为乘法原理。重点·难点加法原理、乘法原理以及上一讲的容斥原理是解决计数问题的三个基本原理。应用加法原理和乘法原理，关键是弄清两者之间的本质区别：如果属于分类考虑，则应用加法原理解题，如果属于分步考虑，则应用乘法原理解题。如何根据题意分清究竟是分类还是分步，是本讲的难点。学法指导在应用这两个原理解计数问题时必须紧紧抓住“分类还是分步”来区分两种原理。除此以外，解决问题常用的方法还有枚举法、对应法、归纳法等，应根据具体问题灵活采用适当的方法。经典例题[例1]如图1所示，在10×10个边长为1的小正方形拼成的棋盘中，求由若干个小方块能拼成的所有正方形的数目。思路剖析由小方块所拼成的正方形边长可以取1，2，⋯，10。这样有十类不同的方式拼出正方形。下面再计算出每类方式有多少种方法拼出正方形。边长为1的正方形显然有10×10个；边长为2的正方形，横边有9种选择：AC，BD，CE，DF，⋯，IK。类似的，纵边也有9种选择，横边和纵边都选定后正方形就确定了。因此经过两个独立步骤就可以完成拼正方形的任务，由乘法原理可知拼出边长为2的小正方形有9×9个。边长为其他数时可以类似推出。解答由乘法原理可得：边长为1的小正方形有10×10个；边长为2的小正方形有9×9个；边长为3的小正方形有8×8个；⋯⋯边长为9的小正方形有2×2个；边长为10的小正方形有1×1个。由加法原理，共有10×10+9×9+⋯2×2+1×1=100+81+64+49+36+25+16+9+4+1=385（个）答：共有385个正方形。[例2]用红、黄、蓝、绿四种颜色给一个五边形（图2）着色，要求：相邻两边的颜色不同。那么共有多少种不同的着色方法？思路剖析为了方便我们给五边形的各个顶点编上字母。给五边形着色是一边一边地着色，因此完成这个任务要分步进行。第一步先涂AB边，有四种颜色可供选择，所以第一步有4种方法；第二步再涂BC边，有除AC边颜色以外的三种颜色可供选择，所以第二步有3种方法；第三步涂CD边，可以选择与BC边颜色不同的另外三种颜色，所以这一步也有3种方法，同理，DE边也有三种颜色可供选择；在涂AE边时，它不但要与DE边不同，还要与AB边不同，所以要分DE边与AB边颜色相同和相异两种不同情况讨论。解答AB边有红、黄、蓝、绿4种不同的涂法；BC边有涂AB边外的3种不同的涂法；CD边有涂BC边外的3种不同的涂法；DE边有涂CD边外的3种不同的涂法。此时，如果DE边和AB边外的两种不同涂法；如果DE边和AB边颜色一样，则AE边有有除AB、DE边外的两种不同涂法；如果DE边和AB边颜色一样，AE边有3种不同的涂法；DE边和AB边颜色不一样时，由乘法原理有4×3×3×3×2=216（种）不同的涂法；DE边和AB边颜色一样时，由乘法原理有4×3×3×3×3=324（种）不同的涂法；最后由加法原理，共有216+324=540（种）。[例3]求由1、2、3、4、5五个数字组成的没有重复数字的五位数的个数。如果将它们从小到大排列起来，则21345位于第几个数？思路剖析要得到由1、2、3、4、5组成的五位数，只需用五个步骤。第一步从五个数字中选一个放在个位上，有5种选法；第二步从剩下的四个数中选一个放在十位上，有4种选法；依次类推，最后一个数放在万位上。解答所求五位数的个数有5×4×3×2×1=120（个）以1、2、3、4、5作万位数的应该一样多，有24个，而21345是以2为万位数的五位数中最小的一个，所以它应该是第25个数。[例4]求5040共有多少个约数？思路剖析首先将5040分解质因数因此5040的约数都可以表示成为其中a的取值为0，1，2...
