math-ai/BlueMO

1{2    "source_file": "./raw_volume-zh/volume11/chapter1.tex",3    "problem_type": "calculation",4    "problem": "例10. 有 $n$ 封不同的信和 $n$ 个配套的写有收信人地址的信封, 现将 $n$ 封信一对一地套人到 $n$ 个信封中去, 结果发现没有一封信套对 (即每封信都没有按地址套人其应套人的信封), 问有多少种不同的套法?",5    "solution": "解:设 $S$ 是所有套法组成的集合,则显然有 $|S|=n$ !. 我们把每封信和对应的信封都分别用 $1,2,3, \\cdots, n$ 进行编号, 并记 $A_i(i=1,2, \\cdots, n)$ 为第 $i$ 封信恰套人第 $i$ 个信封 (即套正确) 的所有套法构成的集合, 故所求的方法数即为 $\\left|\\complement_S A_1 \\cap \\complement_S A_2 \\cap \\cdots \\cap \\complement_S A_\\eta\\right|$, 而易知\n$$\n\\begin{aligned}\n& \\left|A_i\\right|=(n-1) !(1 \\leqslant i \\leqslant n), \\\\\n& \\left|A_i \\cap A_j\\right|=(n-2) !(1 \\leqslant i<j \\leqslant n), \\\\\n& \\cdots \\cdots . \\\\\n& \\left|A_{i_1} \\cap A_{i_2} \\cap \\cdots \\cap A_{i_k}\\right|=(n-k) !\\left(1 \\leqslant i_1<i_2<\\cdots<i_k \\leqslant n\\right), \\\\\n& \\left|A_1 \\cap A_2 \\cap \\cdots \\cap A_n\\right|=0 !=1 .\n\\end{aligned}\n$$\n于是由篮法公式有\n$$\n\\begin{aligned}\n& \\left|\\complement_S A_1 \\cap \\complement_S A_2 \\cap \\cdots \\cap \\complement_S A_n\\right| \\\\\n= & n !-\\mathrm{C}_n^1(n-1) !+\\mathrm{C}_n^2(n-2) !-\\mathrm{C}_n^3(n-3) !+\\cdots+(-1)^n \\mathrm{C}_n^n \\cdot 0 ! \\\\\n= & n !-\\frac{n !}{1 !}+\\frac{n !}{2 !}-\\frac{n !}{3 !}+\\cdots+(-1)^n \\frac{n !}{n !} \\\\\n= & n !\\left(1-\\frac{1}{1 !}+\\frac{1}{2 !}-\\frac{1}{3 !}+\\cdots+(-1)^n \\frac{1}{n !}\\right) .\n\\end{aligned}\n$$",6    "remark": "注:本例通常又称为乱序排列问题.\n所谓乱序排列指的是: 将 $n$ 个不同元素重新排列, 使每个元素都不在原来位置上.\n置换及其不动点给定集合 $X=\\{1,2,3, \\cdots, n\\}, \\varphi$ 是从 $X$ 到 $X$ 上的一一映射,通常记为\n$$\n\\varphi=\\left\\{\\begin{array}{cccc}\n1 & 2 & \\cdots & n \\\\\n\\varphi(1) & \\varphi(2) & \\cdots & \\varphi(n)\n\\end{array}\\right\\},\n$$\n则称 $\\varphi$ 是 $X$ 上的置换, 其中 $\\varphi(i)$ 是元素 $i$ 在映射 $\\varphi$ 下的象.\n因为是一一映射, 所以 $\\varphi(1), \\varphi(2), \\cdots, \\varphi(n)$ 实际上是 $1,2, \\cdots, n$ 的一个排列.\n满足 $\\varphi(i)=i$ 的数 $i$ 称为 $\\varphi$ 的一个不动点.\n由上例立即可得下列结论:\n推论集合 $X=\\{1,2, \\cdots, n\\}$ 上没有任何不动点的置换 $\\varphi$ 的个数是\n$$\nD_n=n !\\left(1-\\frac{1}{1 !}+\\frac{1}{2 !}-\\frac{1}{3 !}+\\cdots+\\frac{(-1)^n}{n !}\\right) .\n$$",7    "figures": []8}