求$n$张编号卡牌洗牌后至少1张在正确位置的方式数

嘿，这个问题用容斥原理就能轻松搞定，我来给你一步步拆解：

首先，我们可以换个思路切入：「至少有1张卡牌在正确位置」的排列数，等于所有可能的全排列数减去「所有卡牌都不在正确位置」的排列数（后者也叫「错排数」，通常记作!n）。不过直接用容斥原理推导目标结果会更直观：

容斥原理推导过程 #

假设我们定义集合A_i为「第i张卡牌固定在正确位置」的所有排列，我们要求的就是这些集合的并集大小：|A₁ ∪ A₂ ∪ ... ∪ Aₙ|。根据容斥原理：

|A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ|A_i| - Σ|A_i ∩ A_j| + Σ|A_i ∩ A_j ∩ A_k| - ... + (-1)^(m+1) Σ|A_i₁ ∩ ... ∩ A_im| + ... + (-1)^(n+1)|A₁ ∩ ... ∩ Aₙ|

我们逐个计算每一项的具体数值：

• 单个集合|A_i|：固定第i张牌在正确位置，剩下n-1张牌可以任意排列，数量是(n-1)!。总共有C(n,1)个这样的集合，所以第一项总和是 C(n,1)*(n-1)! = n!
• 两个集合的交集|A_i ∩ A_j|：固定第i和j张牌在正确位置，剩下n-2张牌任意排列，数量是(n-2)!。总共有C(n,2)个这样的交集，第二项总和是 C(n,2)*(n-2)! = n!/2!
• 以此类推，m个集合的交集总和是 C(n,m)*(n-m)! = n!/m!

把这些项代入容斥公式，最终可以整理出简洁的表达式：

|A₁ ∪ ... ∪ Aₙ| = n! * (1 - 1/2! + 1/3! - 1/4! + ... + (-1)^(n+1)/n!)

或者展开写成：

n! - n!/2! + n!/3! - n!/4! + ... + (-1)^(n+1)*n!/n!

举个例子验证 #

比如当n=3时：

• 全排列共3! = 6种
• 用公式计算：6*(1 - 1/2 + 1/6) = 6*(2/3) = 4
• 实际枚举符合条件的排列：(1,2,3)、(1,3,2)、(3,2,1)、(2,1,3)，正好4种，完全匹配。

再比如n=2时：

• 公式计算：2*(1 - 1/2) = 1
• 实际符合条件的只有(1,2)，结果正确。

内容的提问来源于stack exchange，提问作者AFC