高中數(shù)學(xué)競(jìng)賽專題輔導(dǎo)：容斥原理與組合計(jì)數(shù)一、引言在高中數(shù)學(xué)競(jìng)賽的組合計(jì)數(shù)問題中，容斥原理（Inclusion-ExclusionPrinciple）是解決“重疊計(jì)數(shù)”問題的核心工具。當(dāng)直接計(jì)算滿足條件的元素個(gè)數(shù)較為困難時(shí)，容斥原理通過“先包容、后排斥”的策略，將復(fù)雜的計(jì)數(shù)問題轉(zhuǎn)化為對(duì)多個(gè)集合交集的交替運(yùn)算，從而避免重復(fù)或遺漏。容斥原理的應(yīng)用場(chǎng)景極為廣泛，涵蓋元素限制問題（如“不被某幾個(gè)數(shù)整除的數(shù)的個(gè)數(shù)”）、錯(cuò)位排列（如“信裝錯(cuò)信封”問題）、至多/至少問題（如“至少滿足一個(gè)條件的元素個(gè)數(shù)”）等。掌握容斥原理的推導(dǎo)邏輯與應(yīng)用技巧，能有效提升競(jìng)賽中的計(jì)數(shù)問題解決能力。二、容斥原理的基本概念與定理（一）集合的并集計(jì)數(shù)：從簡(jiǎn)單到一般設(shè)\(U\)為全集，\(A_1,A_2,\dots,A_n\subseteqU\)為\(U\)的子集。我們需要計(jì)算\(|A_1\cupA_2\cup\dots\cupA_n|\)（即至少屬于一個(gè)\(A_i\)的元素個(gè)數(shù)）。1.兩個(gè)集合的并：對(duì)于任意兩個(gè)集合\(A,B\)，有\(zhòng)[A\cupB=A+B-A\capB\]解釋：先將\(A,B\)的元素個(gè)數(shù)相加（包容），再減去同時(shí)屬于\(A,B\)的元素（排斥重復(fù)計(jì)算的部分）。2.三個(gè)集合的并：推廣到三個(gè)集合\(A,B,C\)，有\(zhòng)[A\cupB\cupC=A+B+C-A\capB-A\capC-B\capC+A\capB\capC\]解釋：先包容三個(gè)集合的元素，再排斥兩兩交集的重復(fù)，最后包容三個(gè)集合的交集（因之前被排斥了三次，需補(bǔ)回一次）。3.n個(gè)集合的并（容斥原理一般形式）：對(duì)于\(n\)個(gè)集合\(A_1,A_2,\dots,A_n\)，其并集的元素個(gè)數(shù)為\[A_1\cupA_2\cup\dots\cupA_n=\sum_{k=1}^n(-1)^{k+1}\sum_{1\leqi_1<i_2<\dots<i_k\leqn}A_{i_1}\capA_{i_2}\cap\dots\capA_{i_k}\]其中，\(\sum_{1\leqi_1<\dots<i_k\leqn}|A_{i_1}\cap\dots\capA_{i_k}|\)表示所有\(zhòng)(k\)元子集交集的元素個(gè)數(shù)之和，符號(hào)由\((-1)^{k+1}\)決定（\(k\)為奇數(shù)時(shí)加，偶數(shù)時(shí)減）。（二）容斥原理的逆用：計(jì)算補(bǔ)集在競(jìng)賽中，間接計(jì)數(shù)（計(jì)算補(bǔ)集）往往比直接計(jì)數(shù)更簡(jiǎn)便。設(shè)\(\overline{A_i}\)為\(A_i\)在\(U\)中的補(bǔ)集（即不屬于\(A_i\)的元素），則\[\overline{A_1}\cap\overline{A_2}\cap\dots\cap\overline{A_n}=U-A_1\cupA_2\cup\dots\cupA_n\overline{A_1}\cap\dots\cap\overline{A_n}=\sum_{k=0}^n(-1)^k\sum_{1\leqi_1<\dots<i_k\leqn}A_{i_1}\cap\dots\capA_{i_k}\]結(jié)合容斥原理的一般形式，可得\[\]（注：當(dāng)\(k=0\)時(shí)，空交集對(duì)應(yīng)全集\(U\)，故\(|\emptyset|=|U|\)）。三、容斥原理的典型應(yīng)用（一）元素限制問題：排除不符合條件的元素例1：計(jì)算1到100中，不被2、3、5整除的數(shù)的個(gè)數(shù)。思路分析：設(shè)全集\(U=\{1,2,\dots,100\}\)，定義：\(A=\{x\inU\midx\text{被2整除}\}\)，\(B=\{x\inU\midx\text{被3整除}\}\)，\(C=\{x\inU\midx\text{被5整除}\}\)。要求的是\(|\overline{A}\cap\overline{B}\cap\overline{C}|\)，即不被2、3、5中任何一個(gè)整除的數(shù)的個(gè)數(shù)。解答：1.計(jì)算各集合元素個(gè)數(shù)：\(|A|=\left\lfloor\frac{100}{2}\right\rfloor=50\)，\(|B|=\left\lfloor\frac{100}{3}\right\rfloor=33\)，\(|C|=\left\lfloor\frac{100}{5}\right\rfloor=20\)；2.計(jì)算兩兩交集：\(|A\capB|=\left\lfloor\frac{100}{2\times3}\right\rfloor=16\)，\(|A\capC|=\left\lfloor\frac{100}{2\times5}\right\rfloor=10\)，\(|B\capC|=\left\lfloor\frac{100}{3\times5}\right\rfloor=6\)；3.計(jì)算三個(gè)交集：\(|A\capB\capC|=\left\lfloor\frac{100}{2\times3\times5}\right\rfloor=3\)；4.代入補(bǔ)集公式：\[\overline{A}\cap\overline{B}\cap\overline{C}=U-(A+B+C)+(A\capB+A\capC+B\capC)-A\capB\capC\]代入數(shù)值得：\[100-(50+33+20)+(16+10+6)-3=100-103+32-3=26\]結(jié)論：1到100中不被2、3、5整除的數(shù)有26個(gè)。（二）錯(cuò)位排列（Derangement）：無固定點(diǎn)的排列例2：將n封信裝入n個(gè)信封，要求每封信都不裝入對(duì)應(yīng)的信封（即“錯(cuò)排”），求錯(cuò)排數(shù)\(D(n)\)。思路分析：設(shè)全集\(U\)為n封信的所有排列（共\(n!\)種），定義\(A_i=\{第i封信裝入第i個(gè)信封的排列\(zhòng)}\)（\(i=1,2,\dots,n\)）。要求的是\(|\overline{A_1}\cap\overline{A_2}\cap\dots\cap\overline{A_n}|\)，即無任何一封信裝入對(duì)應(yīng)信封的排列數(shù)。解答：1.計(jì)算各集合元素個(gè)數(shù)：\(|A_i|=(n-1)!\)（固定第i封信，其余n-1封任意排列），共有\(zhòng)(\binom{n}{1}\)個(gè)這樣的集合；2.計(jì)算兩兩交集：\(|A_i\capA_j|=(n-2)!\)（固定第i、j封信，其余n-2封任意排列），共有\(zhòng)(\binom{n}{2}\)個(gè)這樣的交集；3.推廣到k元交集：\(|A_{i_1}\cap\dots\capA_{i_k}|=(n-k)!\)，共有\(zhòng)(\binom{n}{k}\)個(gè)這樣的交集；4.代入補(bǔ)集公式：\[D(n)=|\overline{A_1}\cap\dots\cap\overline{A_n}|=\sum_{k=0}^n(-1)^k\binom{n}{k}(n-k)!\]化簡(jiǎn)得：\[D(n)=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\]結(jié)論：錯(cuò)排數(shù)的公式為\(D(n)=n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\dots+(-1)^n\frac{1}{n!}\right)\)。示例：當(dāng)n=3時(shí)，\(D(3)=3!\left(1-1+\frac{1}{2}-\frac{1}{6}\right)=2\)，對(duì)應(yīng)排列(2,3,1)和(3,1,2)，正確。（三）至多/至少問題：轉(zhuǎn)化為并集計(jì)數(shù)例3：有5個(gè)學(xué)生，每人至少選1門課，最多選3門課（課程為數(shù)學(xué)、物理、化學(xué)）。求至少有2個(gè)學(xué)生選相同課程組合的概率（假設(shè)選法均勻隨機(jī)）。思路分析：首先計(jì)算總選法數(shù)：每個(gè)學(xué)生的選法為\(\binom{3}{1}+\binom{3}{2}+\binom{3}{3}=7\)種，故總選法為\(7^5\)；要求“至少2個(gè)學(xué)生選相同組合”的概率，可先計(jì)算其補(bǔ)集“所有學(xué)生選法都不同”的概率，再用1減去補(bǔ)集概率。解答：1.計(jì)算補(bǔ)集（所有學(xué)生選法不同）的選法數(shù)：第一個(gè)學(xué)生有7種選法，第二個(gè)有6種，…，第五個(gè)有3種（因\(7-5+1=3\)），故為\(P(7,5)=7\times6\times5\times4\times3=2520\)；2.補(bǔ)集概率為\(\frac{2520}{7^5}=\frac{2520}{____}\approx0.15\)；3.所求概率為\(1-\frac{2520}{____}=\frac{____}{____}\approx0.85\)。注：此處“所有學(xué)生選法不同”的計(jì)數(shù)用到了排列數(shù)，而容斥原理隱含在“無重復(fù)”的條件中（即每個(gè)學(xué)生的選法屬于不同的集合）。四、容斥原理的應(yīng)用技巧總結(jié)（一）關(guān)鍵步驟：定義集合容斥原理的核心是合理定義集合，使得問題轉(zhuǎn)化為對(duì)這些集合的并集或補(bǔ)集的計(jì)數(shù)。定義集合的原則：若求“至少滿足一個(gè)條件”的元素個(gè)數(shù)，直接定義每個(gè)條件對(duì)應(yīng)的集合，計(jì)算其并集；若求“不滿足任何條件”或“滿足所有條件”的元素個(gè)數(shù)，定義每個(gè)條件的補(bǔ)集，計(jì)算其交集（通過補(bǔ)集公式轉(zhuǎn)化為并集）。（二）注意事項(xiàng)：避免重復(fù)與遺漏1.交集的計(jì)算：對(duì)于k元交集\(|A_{i_1}\cap\dots\capA_{i_k}|\)，需確保其含義明確（如例1中“被2和3整除”即“被6整除”）；2.符號(hào)的交替：容斥原理的符號(hào)由\((-1)^{k+1}\)（并集）或\((-1)^k\)（補(bǔ)集）決定，需牢記“奇加偶減”的規(guī)律；3.全集的選擇：全集應(yīng)包含所有可能的元素，且易于計(jì)算其大?。ㄈ缋?中的1到100，例2中的所有排列）。（三）拓展：容斥與生成函數(shù)的聯(lián)系容斥原理的一般形式可通過生成函數(shù)表示。對(duì)于集合\(A_1,\dots,A_n\)，其并集的生成函數(shù)為：\[\prod_{i=1}^n(1+x|A_i|)-1\]展開后，x的系數(shù)即為并集的元素個(gè)數(shù)。這種方法常用于處理復(fù)雜的重疊計(jì)數(shù)問題（如多重集合的計(jì)數(shù)），但競(jìng)賽中更多使用容斥的直接形式。五、鞏固練習(xí)（一）基礎(chǔ)題1.計(jì)算1到50中，被2或3整除的數(shù)的個(gè)數(shù)。2.求4個(gè)元素的錯(cuò)排數(shù)\(D(4)\)。（二）提高題3.有5個(gè)不同的球，放入3個(gè)不同的盒子，每個(gè)盒子至少放1個(gè)球，求有多少種放法（用容斥原理解答）。4.計(jì)算1到100中，不被2、3、7整除的數(shù)的個(gè)數(shù)。（三）競(jìng)賽題5.設(shè)n為正整數(shù)，求1到n中，與n互質(zhì)的數(shù)的個(gè)數(shù)（即歐拉函數(shù)\(\phi(n)\)，用容斥原理推導(dǎo)）。答案提示：1.\(|A\cupB|=25+16-8=33\)（\(A\)被2整除，\(B\)被3整除）；2.\(D(4)=4!\left(1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}\right)=9\)；3.總放法\(3^5=243\)，減去空盒情況：\(\binom{3}{1}2^5-\binom{3}{2}1^5+\binom{3}{3}0^5=243-96+3=150\)；4.類似例1，結(jié)果為\(100-(50+33+14)+(16+7+4)-2=28\)；5.設(shè)n的質(zhì)因數(shù)分解為\(n=p_1^{k_1}p_2^{k_2}\dots