一道⁺ / edao.plus

#10067

装信错排·欧拉问题

杂题六年级 #递推法 #容斥原理 #枚举法

题目

有 4 封信分别写给 4 位不同的收信人，对应有 4 个编号的信封（第 i 封信的"正确信封"就是编号为 i 的那个）。

现在把这 4 封信装进 4 个信封里，每个信封恰好装 1 封。要求每封信都装错——即 4 封信全部都没有装进自己的正确信封。

一共有多少种装法？

解法

按信封1装的信号分类，每类剩余3信全错位各有3种，合计求和。
信封 1 装信 2
=3 种
信封 1 装信 3
=3 种
信封 1 装信 4
=3 种
合计
=3 + 3 + 3 = 9

方法

递推法用“上一步怎么办”写出公式，把未知规模的问题一层层推回已知的小规模。容斥原理两圈相交要减重合；三圈相交要“加单、减双、加三”。枚举法按某个顺序把所有可能性“走一遍”，保证不重不漏。

练一练

5 封信分别对应 5 个信封，要求每封信都装错（没有任何一封放入自己的信封），共有多少种装法？

相关题目

#10078 生产利润最大化·资源分配

杂题六年级

#10074 车站选址·总距离最短

枚举法 / 加权中位数

杂题五年级