组合数学专题教案及习题详解

组合数学专题教案及习题详解一、教学目标1.知识目标：掌握组合数学核心概念（排列、组合、容斥原理、生成函数、递推关系）及基本公式；理解各概念间内在联系（如生成函数与递推关系的转化、容斥原理与排列的结合）。2.能力目标：能运用组合方法解决实际问题（计数、排列限制、递推求解）；培养逻辑推理能力（容斥的正向逆向应用、生成函数的构造与展开）。3.情感目标：体会组合数学的简洁性与实用性，激发对离散数学的兴趣；培养严谨的数学思维习惯。二、教学重难点1.重点：排列组合计算（不全相异元素、圆排列）；容斥原理应用（错排、禁止位置排列）；生成函数构造（普通/指数生成函数）；线性递推关系求解（特征方程法、生成函数法）。2.难点：容斥原理复杂应用（多集合交集计数）；生成函数灵活运用（组合数求和、递推转化）；非线性递推关系求解（如Catalan数）。三、教学内容设计第一章排列与组合1.1基本概念排列：从\(n\)个不同元素中取\(k\)个的有序排列数，记为\(P(n,k)\)：\[P(n,k)=\frac{n!}{(n-k)!}\]全排列数为\(n!\)（\(k=n\)时）。组合：从\(n\)个不同元素中取\(k\)个的无序组合数，记为\(C(n,k)\)或\(\binom{n}{k}\)：\[C(n,k)=\frac{n!}{k!(n-k)!}\]性质：对称性\(C(n,k)=C(n,n-k)\)；Pascal公式\(C(n,k)+C(n,k-1)=C(n+1,k)\)。1.2经典问题不全相异元素排列：若\(n\)个元素中有\(k_1,k_2,\dots,k_m\)个重复元素（\(\sumk_i=n\)），排列数为：\[\frac{n!}{k_1!k_2!\cdotsk_m!}\]圆排列：\(n\)个元素排列在圆周上（不考虑旋转等价），排列数为\((n-1)!\)；若考虑翻转等价（如项链问题），排列数为\((n-1)!/2\)（\(n\geq3\)）。多重组合：从\(n\)个元素中可重复取\(k\)个的组合数，记为\(C(n+k-1,k)\)（推导：星与条模型）。第二章容斥原理2.1基本公式并集公式：设\(A_1,A_2,\dots,A_n\)为有限集合，则：\[A_1\cup\cdots\cupA_n=\sumA_i-\sumA_i\capA_j+\sumA_i\capA_j\capA_k-\cdots+(-1)^{m+1}\sumA_{i_1}\cap\cdots\capA_{i_m}+\cdots+(-1)^{n+1}A_1\cap\cdots\capA_nA_1^c\cap\cdots\capA_n^c=U-\sumA_i+\sumA_i\capA_j-\cdots+(-1)^nA_1\cap\cdots\capA_n\]补集公式（逆向应用）：设\(U\)为全集，\(A_i\subseteqU\)，则：\[\]其中\(A_i^c=U\setminusA_i\)为补集。2.2应用举例错排问题（Derangement）：\(n\)个元素均不在原始位置的排列数，记为\(D(n)\)。设\(U\)为所有排列（\(|U|=n!\)），\(A_i\)为第\(i\)个元素在原位的排列集合，则\(D(n)=|A_1^c\cap\cdots\capA_n^c|\)。代入补集公式得：\[D(n)=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\]递推关系：\(D(n)=(n-1)(D(n-1)+D(n-2))\)（初始条件\(D(1)=0\)，\(D(2)=1\)）。禁止位置排列：计算元素不允许出现在特定位置的排列数（如错排是其特例）。第三章生成函数3.1定义与运算普通生成函数（OGF）：序列\(\{a_n\}\)的OGF为：\[G(x)=\sum_{n=0}^\inftya_nx^n\]指数生成函数（EGF）：序列\(\{a_n\}\)的EGF为：\[E(x)=\sum_{n=0}^\inftya_n\frac{x^n}{n!}\]基本运算：加法：\(G(x)+H(x)\)对应序列和；乘法：\(G(x)H(x)\)对应序列卷积（\(c_n=\sum_{k=0}^na_kb_{n-k}\)）；移位：\(x^kG(x)\)对应序列前\(k\)项补0。3.2应用举例组合数生成函数：二项式定理：\((1+x)^n=\sum_{k=0}^nC(n,k)x^k\)（\(C(n,k)\)的OGF）；多重组合数：\(\frac{1}{(1-x)^n}=\sum_{k=0}^\inftyC(n+k-1,k)x^k\)（可重复组合数的OGF）。组合数求和：如\(\sum_{k=0}^nC(n,k)^2=C(2n,n)\)（利用\((1+x)^n(1+x)^n=(1+x)^{2n}\)的卷积性质）。递推关系求解：如斐波那契数列的生成函数（见第四章习题）。第四章递推关系4.1基本概念线性递推关系：设\(\{a_n\}\)为序列，若存在常数\(c_1,\dots,c_k\)（\(c_k\neq0\)），使得：\[a_n=c_1a_{n-1}+\cdots+c_ka_{n-k}+f(n)\quad(n\geqk)\]则称其为\(k\)阶线性递推关系。\(f(n)=0\)时为齐次，否则为非齐次。特征方程法：齐次线性递推关系的特征方程为\(r^k-c_1r^{k-1}-\cdots-c_k=0\)。若有\(k\)个不同根\(r_1,\dots,r_k\)，通解为\(a_n=A_1r_1^n+\cdots+A_kr_k^n\)；若有\(m\)重根\(r\)，对应项为\((A_1+A_2n+\cdots+A_mn^{m-1})r^n\)。4.2应用举例斐波那契数列：\(F(n)=F(n-1)+F(n-2)\)（\(n\geq2\)），特征方程为\(r^2-r-1=0\)，根为\(r_1=\frac{1+\sqrt{5}}{2}\)，\(r_2=\frac{1-\sqrt{5}}{2}\)，通解为\(F(n)=Ar_1^n+Br_2^n\)。代入初始条件\(F(0)=0\)，\(F(1)=1\)，得通项：\[F(n)=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right)\]Catalan数：\(C(n)=\sum_{k=0}^{n-1}C(k)C(n-k-1)\)（\(n\geq1\)），初始条件\(C(0)=1\)。生成函数\(G(x)=\sum_{n=0}^\inftyC(n)x^n\)满足\(G(x)=1+xG(x)^2\)，解得\(G(x)=\frac{1-\sqrt{1-4x}}{2x}\)，展开得：\[C(n)=\frac{1}{n+1}C(2n,n)\]四、习题详解第一章排列与组合习题1.1不全相异元素排列题目：求单词“Mississippi”的字母排列数。解答：单词含1个M、4个I、4个S、2个P，共11个字母。排列数为：\[\frac{11!}{1!\times4!\times4!\times2!}\]思路：用不全相异元素排列公式，消除重复计数。习题1.2圆排列题目：6人围坐圆桌，有多少种不同坐法？若考虑翻转对称，有多少种？解答：不考虑翻转时，圆排列数为\((6-1)!=120\)；考虑翻转时，排列数为\(120/2=60\)。思路：圆排列固定一个位置，其余排列；翻转等价时除以2。第二章容斥原理习题2.1错排问题题目：求5个元素的错排数\(D(5)\)。解答：用错排公式\(D(n)=n!\sum_{k=0}^n\frac{(-1)^k}{k!}\)，计算得：\[D(5)=120\left(1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}-\frac{1}{120}\right)=44\]思路：直接代入公式，或用递推式\(D(5)=4(D(4)+D(3))=4\times(9+2)=44\)。习题2.2禁止位置计数题目：求1到1000中不能被2、3、5整除的数的个数。解答：设\(U=\{1,\dots,1000\}\)，\(A\)（能被2整除）、\(B\)（能被3整除）、\(C\)（能被5整除），求\(|A^c\capB^c\capC^c|\)。计算各集合大小：\(|A|=500\)，\(|B|=333\)，\(|C|=200\)；\(|A\capB|=166\)，\(|A\capC|=100\)，\(|B\capC|=66\)；\(|A\capB\capC|=33\)。代入补集公式：\[A^c\capB^c\capC^c\]思路：用容斥原理的补集公式，计算能被2、3、5整除的数的并集大小，再用全集减去并集大小。第三章生成函数习题3.1组合数求和题目：求\(\sum_{k=0}^nC(n,k)C(m,k)\)（\(m\leqn\)）。解答：考虑生成函数\((1+x)^n\)（\(C(n,k)\)的OGF）和\((1+\frac{1}{x})^m\)（\(C(m,k)\)的OGF），乘积的常数项为\(\sum_{k=0}^mC(n,k)C(m,k)\)。乘积化简为\(\frac{(1+x)^{n+m}}{x^m}\)，常数项为\(C(n+m,m)\)，故：\[\sum_{k=0}^nC(n,k)C(m,k)=C(n+m,m)\]思路：利用生成函数的乘积性质，将组合数求和转化为常数项问题。习题3.2递推关系求解题目：用生成函数求序列\(\{a_n\}\)的通项，其中\(a_0=1\)，\(a_1=3\)，\(a_n=3a_{n-1}-2a_{n-2}\)（\(n\geq2\)）。解答：设生成函数\(G(x)=\sum_{n=0}^\inftya_nx^n\)，则：\[G(x)=1+3x+\sum_{n=2}^\infty(3a_{n-1}-2a_{n-2})x^n=1+3x+3x(G(x)-1)-2x^2G(x)\]整理得\(G(x)=\frac{1}{(1-x)(1-2x)}\)，部分分式分解为\(\frac{2}{1-2x}-\frac{1}{1-x}\)，展开得：\[G(x)=\sum_{n=0}^\infty(2^{n+1}-1)x^n\impliesa_n=2^{n+1}-1\]思路：构造生成函数，建立方程，解出生成函数后展开为幂级数。第四章递推关系习题4.1特征方程法题目：求序列\(\{a_n\}\)的通项，其中\(a_0=2\)，\(a_1=5\)，\(a_n=4a_{n-1}-4a_{n-2}\)（\(n\geq2\)）。解答：特征方程为\(r^2-4r+4=0\)，重根\(r=2\)，通解为\(a_n=(A+Bn)2^n\)。代入初始条件得：\(a_0=A=2\)；\(a_1=(2+B)\times2=5\impliesB=\frac{1}{2}\)。故通项为\(a_n=(2+\frac{1}{2}n)2^n=(n+4)2^{n-1}\)。思路：重根的线性齐次递推关系，通解为多项式乘以根的幂次，用初始条件确定常数。习题4.2Catalan数递推题目：求Catalan数\(C(3)\)，其中\(C(0)=1\)，\(C(n)=\sum_{k=0}^{n-1}C(k)C(n-k-1)\)（\(n\geq1\)）。解答：用递推式计算：\(C(1)=C(0)C(0)=1\)；\(C(2)=C(0)C(1)+C(1)C(0)=2\)；\(C(3)=C(0)C(2)+C(1)C(1