排列组合经典例题解析及训练教程

排列组合经典例题解析及训练教程一、排列组合基础概念回顾排列组合是组合数学的核心内容，研究从有限集合中选取元素的方式数，广泛应用于概率统计、计算机算法、组合设计等领域。其核心区别在于：排列关注顺序，组合不关注顺序。1.排列数（Permutation）从\(n\)个不同元素中选取\(k\)个（\(k\leqn\)），并按一定顺序排列的方式数，记为\(P(n,k)\)或\(A(n,k)\)，公式为：\[P(n,k)=n\times(n-1)\times(n-2)\times\cdots\times(n-k+1)=\frac{n!}{(n-k)!}\]例：从5人中选2人担任正、副班长，排列数为\(P(5,2)=5\times4=20\)（正班长有5种选法，副班长有4种选法）。从\(n\)个不同元素中选取\(k\)个（\(k\leqn\)），不考虑顺序的方式数，记为\(C(n,k)\)或\(\binom{n}{k}\)，公式为：\[C(n,k)=\frac{P(n,k)}{k!}=\frac{n!}{k!(n-k)!}\]例：从5人中选2人参加会议，组合数为\(C(5,2)=\frac{5\times4}{2\times1}=10\)（不关心两人的顺序）。3.核心性质组合数对称性：\(C(n,k)=C(n,n-k)\)（选\(k\)个等价于不选\(n-k\)个）；排列与组合关系：\(P(n,k)=C(n,k)\timesk!\)（组合后再排列）。二、经典例题分类解析排列组合问题的关键是识别问题类型，选择对应方法。以下是六大经典类型及解法：1.相邻问题——捆绑法问题特征：要求某些元素必须相邻。解法步骤：（1）将相邻元素“捆绑”为一个整体元素，减少元素数量；（2）计算整体元素与其他元素的排列数；（3）计算捆绑内部元素的排列数；（4）两者相乘得总排列数。例1：5人排成一排，甲、乙必须相邻，有多少种排法？解析：捆绑甲、乙为一个整体，此时相当于4个元素（整体+丙+丁+戊）排列，排列数为\(P(4,4)=4!\)；甲、乙内部有\(2!\)种排列方式；总排法：\(4!\times2!=24\times2=48\)种。2.不相邻问题——插空法问题特征：要求某些元素不能相邻。解法步骤：（1）先排列无限制条件的元素，形成“空位”；（2）将不相邻元素插入空位中（空位数量=无限制元素数+1）；（3）两者相乘得总排列数。例2：7人排成一排，丙、丁不能相邻，有多少种排法？解析：先排其他5人（甲、乙、戊、己、庚），排列数为\(P(5,5)=5!\)；5人排好后，有6个空位（如\_甲\_乙\_戊\_己\_庚\_），插入丙、丁，排列数为\(P(6,2)=6\times5\)；总排法：\(5!\times6\times5=120\times30=3600\)种。3.分组与分配问题问题特征：将元素分成若干组，或分配给不同对象。核心区别：分组：组与组之间无区别（如“分成3组”），需避免重复计数；分配：组与组之间有区别（如“分给3个人”），无需去重。例3：将6本不同的书分成3组，每组2本，有多少种分法？解析（均匀分组，去重）：第一步选2本：\(C(6,2)\)；第二步选2本：\(C(4,2)\)；第三步选2本：\(C(2,2)\)；由于三组无顺序，需除以\(3!\)（避免重复计数，如{AB,CD,EF}与{CD,AB,EF}视为同一分组）；总分组数：\(\frac{C(6,2)\timesC(4,2)\timesC(2,2)}{3!}=\frac{15\times6\times1}{6}=15\)种。例4：将6本不同的书分给3人，每人2本，有多少种分法？解析（分配问题，无需去重）：直接分组后分配给3人，每组对应不同的人，无需除以\(3!\)；总分配数：\(C(6,2)\timesC(4,2)\timesC(2,2)=15\times6\times1=90\)种。4.错位排列（Derangement）问题特征：所有元素都不排在原来的位置（如“信装错信封”“钥匙开错锁”）。公式：设\(D(n)\)为\(n\)个元素的错位排列数，则：\[D(n)=(n-1)\times[D(n-1)+D(n-2)]\]初始条件：\(D(1)=0\)（1个元素无法错位），\(D(2)=1\)（2个元素交换位置）。常用值：\(D(3)=2\)，\(D(4)=9\)，\(D(5)=44\)。例5：4封信投入4个信封，全部装错的情况有多少种？解析：直接用错位排列数\(D(4)=9\)种。5.容斥原理应用——“至少/至多”问题问题特征：求“至少有一个满足条件”或“至多有\(k\)个满足条件”的情况数。解法：利用容斥原理计算并集或补集（“至少一个”=总数-“都不满足”）。例6：5个元素排列，至少有一个元素在原来位置的排列数？解析（补集法）：总排列数：\(5!=120\)；都不在原来位置的错位排列数：\(D(5)=44\)；至少一个在原位的排列数：\(120-44=76\)种。例7：从1到10的整数中选5个数，至少有一个偶数的选法有多少种？解析（补集法）：总选法：\(C(10,5)=252\)；都不选偶数（即选5个奇数）的选法：\(C(5,5)=1\)；至少一个偶数的选法：\(252-1=251\)种。6.相同元素分配——隔板法问题特征：将\(n\)个相同元素分给\(k\)个不同对象，每个对象至少1个（或允许0个）。公式：每个对象至少1个：\(C(n-1,k-1)\)（\(n-1\)个间隙插\(k-1\)个隔板）；每个对象允许0个：\(C(n+k-1,k-1)\)（先给每个对象补1个，转化为至少1个的情况）。例8：将5个相同的苹果分给3个小朋友，每个小朋友至少1个，有多少种分法？解析：5个苹果有4个间隙，插2个隔板，分法为\(C(4,2)=6\)种（如“||”表示第一个小朋友1个，第二个2个，第三个2个）。三、专项训练题集以下训练题按基础-中等-进阶梯度设计，覆盖上述所有类型。1.基础题（巩固概念）（1）从8人中选3人排列，有多少种排法？（答案：\(P(8,3)=336\)）（2）从10个元素中选4个组合，有多少种选法？（答案：\(C(10,4)=210\)）（3）3个相同的球放进2个不同的盒子，每个盒子至少1个，有多少种分法？（答案：\(C(2,1)=2\)）2.中等题（应用方法）（4）6人排成一排，甲必须在第一个位置，有多少种排法？（提示：固定甲的位置，排剩余5人，答案：\(5!=120\)）（5）7人排成一排，甲、乙不相邻，丙、丁必须相邻，有多少种排法？（提示：先捆绑丙、丁，再用插空法排甲、乙，答案：\(2!\times5!\timesP(6,2)=2\times120\times30=7200\)）（6）将8本不同的书分给2人，每人4本，有多少种分法？（提示：分配问题，无需去重，答案：\(C(8,4)=70\)）3.进阶题（综合能力）（7）5个元素排列，恰好有2个元素在原来位置的排列数？（提示：先选2个元素固定，剩余3个错位排列，答案：\(C(5,2)\timesD(3)=10\times2=20\)）（8）从1到9的整数中选5个数，至少有一个奇数和一个偶数的选法有多少种？（提示：补集法，总选法-全奇数-全偶数，答案：\(C(9,5)-C(5,5)-C(4,5)=____=125\)）（9）将7个相同的玩具分给4个小朋友，每个小朋友至少1个，有多少种分法？（提示：隔板法，答案：\(C(6,3)=20\)）四、总结与方法提炼排列组合问题的解决关键是“识别类型+选择方法”，以下是核心方法的总结：问题类型核心方法注意事项相邻问题捆绑法捆绑后内部需排列不相邻问题插空法先排无限制元素均匀分组组合数÷组数!组无区别